Question

Give a decision problem corresponding to each of the search problems given below. (a) • Input: A set of classes to be scheduled. A list of pairs of the classes which can not be scheduled during the same period. • Output: The largest set of classes that can all be scheduled during the same period. Solution A • Input: A set of classes to be scheduled. A list of pairs of the classes which can not be scheduled during the same period. An integer k. • Output: "Yes" if there is a set of k classes that can be all scheduled during the same period. "No" if there is no set of k classes that can all be scheduled at the same time. • Input: A set of classes to be scheduled. A list of pairs of the classes which can not be scheduled during the same period. • Output: A schedule for the classes that uses the smallest number of periods. (c) • Input: A list of items, each with a value and a weight. The values and weights of the items are positive integers. A positive integer W. • Output: A subset of the items whose total weight is at most W and whose total value is as large as possible. Solution • Input: A list of items, each with a value and a weight. The values and weights of the items are positive integers. A positive integer W. A positive integer V. • Output: "Yes" if there is a subset of the items whose total value is at least V and whose total weight is at most W. Output "No", otherwise.

Answer 1

The program below depicts your requirements and for any Query post in comment section and do rate my answer.

The code and output screenshots will be attatched in case of indentation errors.

"""

1.) Input: List of classes to be scheduled , List of tuples (class,class) cannot be scheduled together. Integer k

OUTPUT: Yes --> k classes scheduled together

No --> k classes cannot be scheduled together

"""

def isKschedulePossible(list_classes,tuple_pair,k):

schedule_list = []

# schedule all classes at first

schedule_list.extend(list_classes)

for x in tuple_pair:

# either 1 of the pair of classes can be present

if x[0] in schedule_list:

# removing its pair class from schedule list will give us one from each tuple

schedule_list.remove(x[1])

if len(schedule_list) is k:

return "Yes"

else:

return "No"

"""

2.) Input: Set of classes to be scheduled, List of tuples(class,class) cannot be scheduled together

Output: Schedule of classes with minimum period.

"""

# let a period where classes are scheduled be unit period.

def minSchedulePeriod(list_classes,tuple_pair):

schedule_list = []

# this will contain classes scheduled over a period together

schedule_list.append([])

for x in list_classes:

schedule_list[0].append(x)

# all classes are added in schedule at first.__build_class__

for item in tuple_pair:

# first lets remove one item out of the pair from schedule list

if item[0] in schedule_list[0]:

try:

schedule_list[0].remove(item[1])

schedule_list.append(item[1])

except ValueError:

pass

print("Schedule with minimum period needed is printed as list of list as schedules for classes at same time and a list member if its scheduled after a certain schedule.")

print(schedule_list)

"""

3.) Input: Tuple of items (Item no,Item Weight,Item Value). A Total Weight W. Min Value V.

Output: Yes if V reached with at max weight W or No.

This problem resembles a knapsack problem but is not a knapsack problem

"""

def knapSack(tuple_list, W, V):

# the tuple has all the list for item no. its weight and value

prof_val = 0 # profit or Value

init_weight = 0 # weight of knapsack

for item in tuple_list:

if init_weight<W and prof_val<V:

init_weight += item[1]

prof_val += item[2]

# if both exceed at a given item

if init_weight > W and prof_val >= V:

return "No"

if init_weight <= W and prof_val >=V:

return "Yes"

if init_weight == W and prof_val <V:

return "No"

##### DRIVER PROGRAM#########

list_classes = [1,2,3,4,5,6]

tuple_pair = [(1,6),(2,5)]

k = 5

print(isKschedulePossible(list_classes,tuple_pair,k))

minSchedulePeriod(list_classes,tuple_pair)

item_list = [(1,5,10),(2,6,12),(3,9,25)]

print(knapSack(item_list,11,22))

print(knapSack(item_list,11,45))

####### Screenshot ############

main.py E saved No Schedule with minimum period needed is printed as list of list as schedules for classes at sa me time and a list member if its scheduled after a certain schedule. [[1, 2, 3, 4], 6, 5] Yes 2 1.) Input: List of classes to be scheduled , List of tuples (class, class) cannot be scheduled together. Integer k OUTPUT: Yes --> k classes scheduled together No --> k classes cannot be scheduled together 3 NO def iskschedulePossible(list_classes, tuple_pair,k): schedule_list = [] # schedule all classes at first schedule_list.extend(list_classes) for x in tuple_pair: # either 1 of the pair of classes can be present if x[0] in schedule_list: # removing its pair class from schedule list will give us one from each tuple schedule_list.remove(x[1]) if len(schedule_list) is k: return "Yes" else: return "No" 2.) Input: Set of classes to be scheduled, List of tuples (class, class) cannot be scheduled together Output: Schedule of classes with minimum period. # let a period where classes are scheduled be unit period. def minScheduleperiod (list_classes, tuple_pair): schedule_list = [] # this will contain classes scheduled over a period together schedule_list.append([]) for x in list_classes: schedule_list[@].append(x) # all classes are added in schedule at first. _build_class_ for item in tuple_pair: # first lets remove one item out of the pair from schedule list if item[@] in schedule_list[@]: try: schedule_list[@].remove(item[1]) schedule_list.append(item[1]) except ValueError: pass print("Schedule with minimum period needed is printed as list of list as schedules for classes at same time and a list member if its scheduled after a certain schedule.") print(schedule_list) rac 110cn

main.py saved 45 3.) Input: Tuple of items (Item no, Item Weight, Item Value). A Total Weight W. Min Value V. Output: Yes if V reached with at max weight W or No. No Schedule with minimum period needed is printed as list of list as schedules for classes at sa me time and a list member if its scheduled after a certain schedule. [[1, 2, 3, 4], 6, 5] Yes No This problem resembles a knapsack problem but is not a knapsack problem def knapsack(tuple_list, W, V): # the tuple has all the list for item no. its weight and value prof_val = # profit or Value init_weight = # weight of knapsack for item in tuple_list: if init_weight<w and prof_val<v: init_weight += item[1] prof_val += item[2] # if both exceed at a given item if init_weight > W and prof_val >= V: return "No" if init_weight <= W and prof_val >=V: return "Yes" if init_weight == W and prof_val <v: return "No" list_classes = [1,2,3,4,5,6] tuple_pair = [(1,6),(2,5)] k = 5 print(iskschedulepossible(list_classes, tuple_pair,k)) 75 minScheduleperiod(list_classes, tuple_pair) item_list = [(1,5,10),(2,6,12), (3,9,25)] print(knapsack(item_list, 11,22)) print(knapsack(item_list, 11,45))