http://www.codesend.com/view/499640e2a69f9d18b8873c1b8796f3f9/ def greedyAdvisor(subjects, maxWork, comparator): """ Returns a dictionary mapping subject name to (value, work) which includes subjects selected by the algorithm, such that the total work of subjects in the dictionary is not greater than maxWork. The subjects are chosen using a greedy algorithm. The subjects dictionary should not be mutated.

subjects: dictionary mapping subject name to (value, work) maxWork: int >= 0 comparator: function taking two tuples and returning a bool returns: dictionary mapping subject name to (value, work) """ subjectsCopy = subjects.copy() result = {} totalWork = 0 WORK = 1 while totalWork < maxWork and len(subjectsCopy) > 0: bestSubName = None for subName in subjectsCopy.keys(): if bestSubName is None or comparator(subjects[subName], subjects[bestSubName]): bestSubName = subName bestSubject = subjectsCopy.pop(bestSubName) if totalWork + bestSubject[WORK] <= maxWork: result[bestSubName] = bestSubject totalWork += bestSubject[WORK] return result

##SHORT_SUBJECT_FILENAME = "shortened_subjects.txt" ##print("Greedy approach") ##subjects = loadSubjects(SHORT_SUBJECT_FILENAME) ##print(greedyAdvisor(subjects, 5, cmpRatio))

# # Problem 3: Subject Selection By Brute Force # def bruteForceAdvisor(subjects, maxWork): """ Returns a dictionary mapping subject name to (value, work), which represents the globally optimal selection of subjects using a brute force algorithm.

subjects: dictionary mapping subject name to (value, work) maxWork: int >= 0 returns: dictionary mapping subject name to (value, work) """ subjects = subjects.items() options = [] best = [] VALUE = 0 WORK = 1 for i in range(1, len(subjects)+1): options.append(itertools.combinations(subjects, i)) #comp for schedules in options: for courses in schedules: work = 0 val = 0 bestVal = 0 for i in courses: work += i[1][WORK] if work <= maxWork: for i in courses: val += i[1][VALUE] for i in best: bestVal += i[1][VALUE] if val > bestVal: best = courses return best

a. What is the algorithmic complexity of greedyAdvisor?

b. What is the algorithmic complexity of bruteForceAdvisor?

c. Assuming 1 microsecond (1 microsecond = 1 10-6 seconds) to compute the value of a solution in bruteForceAdvisor, how much time in years (365 days per year) would it take for bruteForceAdvisor to find an optimal solution for the following number of subjects:

d. 8 subjects?

16 subjects?

32 subjects?

320 subjects (the number of courses in the problem set)?