Python

Project Statement: At an institute of higher education that shall be nameless, it used to be the case that a human advisor would help each student formulate a list of subjects that would meet the students objectives. However, because of financial troubles, the Institute has decided to replace human advisors with software. Given the amount of work a student wants to do, the program returns a list of subjects that maximizes the amount of value. The goal of this problem set is to implement a dynamic programming algorithm

Step 1:

The first step is to implement loadSubjects in (file named )project1.py, which loads a list of subjects from a file. Each line of the file contains a string of the form name, value, work, where the name is a string, the value is an integer indicating how much a student learns by taking the subject, and the work is an integer indicating the number of hours a student must spend to pass the subject. loadSubjects should return a dictionary mapping subject names to tuples, where the tuples are pairs of (learning value, work hours) integers.

def loadSubjects(filename):

""" Returns a dictionary mapping subject name to (value, work), where the name is a string and the value and work are integers. The subject information is read from the file named by the string filename. Each line of the file contains a string of the form "name, value, work".

returns: dictionary mapping subject name to (value, work) """

# The following sample code reads lines from the specified file and print each one.

inputFile = open(filename)

For line in inputFile:

print line

# TODO: Instead of printing each line, modify the above to parse the name,

# value, and work of each subject and create a dictionary mapping the name

# to the (value, work).

Hint:

You may find split () and strip () methods of strings useful when implementing this. See their documentation at the online Python Library Reference. In particular, you may want to use split() to split at commas and strip() to remove the line break at the end of each line.

You can think of the dictionary returned by loadSubjects as a representation of the full subject catalog. In subsequent problems, we will use dictionaries of the same structure to represent subject selections (subsets of the full subject catalog).

Step2 :

This step is to implement the Greedy optimization:

The Institute hired you to implement the program. They asked you to implement a greedy method (greedyAdvisor) to formulate a list of subjects that satisfies each students constraint (the amount of work student is willing to do).

The algorithm should pick the best subjects first. The notion of best is determined by the use of the comparator. The comparator is a function that takes two argumentseach of which is a (value, work) tupleand returns a boolean indicating whether the first argument is better than the second. Here, the definition of better can be altered by passing in different comparators.

Weve provided three comparators for you to pass in:

cmpValue, which compares the values of the subjects

cmpWork, which compares the workload of the subjects,

cmpRatio, which compares the value/work ratios of the subjects.

Implement greedyAdvisor in project1.py:

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 Boolean

returns: dictionary mapping subject name to (value, work)

"""

Step 3 :

This step is to implement the brute force algorithm: As we learned in lecture, a greedy algorithm does not always lead to the globally optimal solution. One approach to finding the globally optimal solution is to use brute force to enumerate all possible solutions and choose the one yielding the best value while satisfying the given constraints. We have provided an implementation of the brute force algorithm in the function bruteForceAdvisor in project1.py. This function returns a dictionary mapping subject name to (value, work), which represents the globally optimal selection of subjects using a brute force algorithm.

def bruteForceTime():

"""

Runs tests on bruteForceAdvisor and measures the time required to compute

an answer.

Step 4 :

This step is to implement the Dynamic Programming algorithm: We saw in lecture that dynamic programming can be used to reduce an exponential-time optimization algorithm to a pseudo polynomial-time algorithm. This is done by breaking up the original problem into sub-problems and memoizing the intermediate solutions to the sub-problems. This results in a speed-up because the solutions to sub-problems are used multiple times, and memoization avoids re-computing these solutions. In this project, you will use dynamic programming to find the globally optimal subject selection.

Implement dpAdvisor in project1.py, which returns a dictionary mapping subject name to (value, work) found by the dynamic programming method.

def dpAdvisor (subjects, maxWork):

"""

Returns a dictionary mapping subject name to (value, work) that contains a

set of subjects that provides the maximum value without exceeding maxWork.

subjects: dictionary mapping subject name to (value, work)

maxWork: int >= 0

returns: dictionary mapping subject name to (value, work)

""".

Step 5 : Performance Comparison

Measure the performance of dpAdvisor . How does the performance of the dynamic programming algorithm compare to that of the brute force algorithm? Place your timing code in dpTime and your observations in comments below dpTime.

def dpTime():

"""

Runs tests on dpAdvisor and measures the time required to compute an

answer.

"""