Due: Saturday, February 29, 2020, at 5pm

You may work alone or with a partner, but you must type up the code yourself. You may also discuss the assignment at a high level with other students. You should list any student with whom you discussed the assignment, and the manner of discussion (high-level, partner, etc.) in a readme.txt file that you include with your submission.

You should submit your assignment as a .zip file on Moodle.

You will work in two different files for this assignment. Additionally, you will need a data file. All of the code is available in a single .zip file.

Parts of this assignment:

• Problem 1: Representing a course
• Problem 2: Greedy course selection
• Problem 3: Different greedy sort orders

Note on style:

The following style guidelines are expected moving forward, and will typically constitute 5-10 points of each assignment (out of 100 points).

• Variable names should be clear and easy to understand, should not start with a capital letter, and should only be a single letter when appropriate (usually for i, j, and k as indices, potentially for x and y as coordinates, and maybe p as a point, c for a circle, r for a rectangle, etc.).
• It’s good to use empty lines to break code into logical chunks.
• Comments should be used for anything complex, and typically for chunks of 3-5 lines of code, but not every line.
• Don’t leave extra print statements in the code, even if you left them commented out.
• Make sure not to have code that computes the right answer by doing extra work (e.g., leaving a computation in a for loop when it could have occurred after the for loop, only once).
• Use lowercase first letters for variables and methods, and uppercase first letters for classes.

Note: The example triangle-drawing program on page 108 of the textbook demonstrates a great use of empty lines and comments, and has very clear variable names. It is a good model to follow for style.

Problem 1: Representing a course

# You should be fully equipped to complete this problem after lesson 19 (Wednesday Feb. 19).

In this problem, you will complete the implementation of the Course class to represent courses. Each course has a name, an amount of effort required, and a value due to taking the course.

Here is the specification of the Course class:

• The constructor takes in three parameters: the name, the effort, and the value.
• Each of the three instance variables has an accessor method: getName(), getEffort(), and getValue().
• There should be a __str__() method that is used to generate a string representation of a Course instance.

Fill in the class definition for Course in course.py. As an exercise in test-driven developent, there is testing code provided for you in an if __name__ == "__main__": block at the bottom of this file. Once your implementation is complete, the tests should all pass:

Testing Course.getName(): pass
Testing Course.getEffort(): pass
Testing Course.getValue(): pass
Testing Course.__str__(): pass

Problem 2: Greedy course selection

# You should be mostly equipped to complete this problem after lesson 21 (Monday Feb. 24).

To actually choose our courses, we will use a greedy approach, selecting courses until the maximumEffort is succeeded, or all courses have been considered. In Problem 3, you will implement three different greedy orderings for the courses.

Take a look at the provided code in courseSelector.py. The file is broken into a series of classes, which can be depicted as something of a tree. CourseSelector is the parent class. It includes three methods: the constructor, a method to add a course to the set, and the chooseCourses method. The chooseCourses method is not implemented; it raises an error saying the method isn’t implemented, as any subclasses should provide an implementation for this. CourseSelector is what might be called an “abstract class” in other programming languages. You should not make any objects that are just instances of CourseSelector; instead, you’ll make instances of its subclasses.

GreedyCourseSelector (as opposed to an optimal solution, which takes much longer but gives the best possible result) is a subclass of CourseSelector. As such, it has access to any methods or instance variables defined in its parent class, including self.courses. For this problem, you will implement the chooseCourses of the GreedyCourseSelector class.

class GreedyCourseSelector(CourseSelector):
    def __init__(self, courses = []):
        # Don't do anything special, just call the parent constructor
        # to initialize the courses
        CourseSelector.__init__(self, courses)

        # This should be overridden in subclasses
        self.greedyFunc = lambda x: None

    def chooseCourses(self, maxEffort):
        """
        Choose courses greedily, using a pre-determined greedy
        evaluation function, without going over maxEffort.

        returns: value, effort, and list of courses
        """
        # Sort the courses based on the greedy evaluation function
        # (this must be defined in subclasses)

        # Choose courses as long as the total effort isn't more
        # than maxEffort

        # Return the value effort, and the chosen courses
        return 0, 0, [] # TODO: replace with your code

Note that we will not actually create any instances of GreedyCourseSelector, either. It will have three child classes, each setting a different self.greedyFunc that should be used as a key when sorting the list of courses. For now, each child class simply returns 0 each time it is called, so the list is not reordered.

This is the expected output once you’ve completed this function, given the test code in courseSelector.py:

Maximum effort: 12

Value greedy result:
  value: 8
  effort: 12
  A (10 effort, 4 value)
  C (2 effort, 4 value)

Effort greedy result:
  value: 8
  effort: 12
  A (10 effort, 4 value)
  C (2 effort, 4 value)

Value-to-effort ratio greedy result:
  value: 8
  effort: 12
  A (10 effort, 4 value)
  C (2 effort, 4 value)

Problem 3: Different greedy sort orders

For this final problem, you will make changes in the three child classes of GreedyCourseSelector to choose the key function for sorting the list of courses.

class ValueGreedyCourseSelector(GreedyCourseSelector):
    """
    A greedy course selector that favors courses with high value,
    regardless of effort.
    """
    
    def __init__(self, courses = []):
        # Don't do anything special, just call the parent constructor
        # to initialize the courses
        GreedyCourseSelector.__init__(self, courses)

        # Favor courses with high value, regardless of effort
        self.greedyFunc = lambda x: 0 # TODO

class EffortGreedyCourseSelector(GreedyCourseSelector):
    """
    A greedy course selector that favors courses with low effort,
    regardless of value.
    """
    
    def __init__(self, courses = []):
        # Don't do anything special, just call the parent constructor
        # to initialize the courses
        GreedyCourseSelector.__init__(self, courses)

        # Favor courses with low effort, regardless of value
        self.greedyFunc = lambda x: 0 # TODO

class ValuePerEffortGreedyCourseSelector(GreedyCourseSelector):
    """
    A greedy course selector that favors courses with high
    value-to-effort ratio.
    """
    
    def __init__(self, courses = []):
        # Don't do anything special, just call the parent constructor
        # to initialize the courses
        GreedyCourseSelector.__init__(self, courses)

        # Favor courses with high value-to-effort ratio
        self.greedyFunc = lambda x: 0 # TODO

Your code for this problem will likely be three lines of code, or slightly more if you choose not to use lambda functions.

Once you’ve set these functions appropriately, you should get the following output when running courseSelector.py:

Maximum effort: 12

Value greedy result:
  value: 18
  effort: 11
  B (5 effort, 10 value)
  D (6 effort, 8 value)

Effort greedy result:
  value: 14
  effort: 9
  C (2 effort, 4 value)
  E (3 effort, 3 value)
  G (4 effort, 7 value)

Value-to-effort ratio greedy result:
  value: 21
  effort: 11
  B (5 effort, 10 value)
  C (2 effort, 4 value)
  G (4 effort, 7 value)

Note that depending on whether you copy the list of courses before sorting it, you might get different output than I provided above. This happens in particular because there is no tie breaker specified. Here is an alternative, where some values are swapped if the key-value is the same:

Maximum effort: 12

Value greedy result:
  value: 18
  effort: 11
  B (5 effort, 10 value)
  D (6 effort, 8 value)

Effort greedy result:
  value: 14
  effort: 9
  C (2 effort, 4 value)
  E (3 effort, 3 value)
  G (4 effort, 7 value)

Value-to-effort ratio greedy result:
  value: 21
  effort: 11
  C (2 effort, 4 value)
  B (5 effort, 10 value)
  G (4 effort, 7 value)

You can then run with a slightly larger set of data, roughly corresponding to Carleton’s CS course offerings. Note: these are entirely made up randomly, except for CS 111 which has suspiciously high value for the amount of effort…

CS 111,2,10
CS 201,7,4
CS 202,3,5
CS 208,4,1
CS 231,4,10
CS 232,9,1

You don’t have to parse the file, as that code is provided for you in chooseCourses.py. There is some test code inside an if __name__ == "__main__": block at the bottom of the file. When you run chooseCourses.py, you should get the following output:

Maximum effort: 14

Value greedy result:
  value: 40
  effort: 14
  CS 111 (2 effort, 10 value)
  CS 231 (4 effort, 10 value)
  CS 252 (3 effort, 10 value)
  CS 330 (5 effort, 10 value)

Effort greedy result:
  value: 52
  effort: 13
  CS 332 (1 effort, 10 value)
  CS 352 (1 effort, 10 value)
  CS 111 (2 effort, 10 value)
  CS 251 (2 effort, 5 value)
  CS 348 (2 effort, 3 value)
  CS 362 (2 effort, 9 value)
  CS 202 (3 effort, 5 value)

Value-to-effort ratio greedy result:
  value: 63
  effort: 14
  CS 332 (1 effort, 10 value)
  CS 352 (1 effort, 10 value)
  CS 111 (2 effort, 10 value)
  CS 362 (2 effort, 9 value)
  CS 252 (3 effort, 10 value)
  CS 324 (3 effort, 9 value)
  CS 251 (2 effort, 5 value)

An alternative result, with a different final choice for effort, resulting in higher value:

Maximum effort: 14

Value greedy result:
  value: 40
  effort: 14
  CS 111 (2 effort, 10 value)
  CS 231 (4 effort, 10 value)
  CS 252 (3 effort, 10 value)
  CS 330 (5 effort, 10 value)

Effort greedy result:
  value: 57
  effort: 13
  CS 332 (1 effort, 10 value)
  CS 352 (1 effort, 10 value)
  CS 111 (2 effort, 10 value)
  CS 362 (2 effort, 9 value)
  CS 251 (2 effort, 5 value)
  CS 348 (2 effort, 3 value)
  CS 252 (3 effort, 10 value)

Value-to-effort ratio greedy result:
  value: 63
  effort: 14
  CS 332 (1 effort, 10 value)
  CS 352 (1 effort, 10 value)
  CS 111 (2 effort, 10 value)
  CS 362 (2 effort, 9 value)
  CS 252 (3 effort, 10 value)
  CS 324 (3 effort, 9 value)
  CS 251 (2 effort, 5 value)

Play around with different values of maxEffort to see which courses are chosen, and which greedy solution typically gives the highest value.

What you should submit

You should submit a single .zip file on Moodle. It should contain the following files:

• readme.txt (collaboration statement listing collaborators and form of collaboration)
  
• course.py (Problem 1)
• courseSelector.py (Problems 2+3)