Due: Friday, February 23, 2024, at 10pm

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 each part, and the manner of discussion (high-level, partner, etc.) in a comment at the top of each file. You should only have one partner for an entire assignment.

You should submit your assignment as an a8.zip file on Moodle.

Parts of this assignment:

• Part 1: Greedy course selection
• Part 2: Different greedy sort orders

You will extend your work from Assignment #7 to choose a set of courses optimizing for some goal. There is skeleton code available to you; you should save the code file as courseSelector.py.

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.

Part 1: Greedy course selection

# You should be mostly equipped to complete this problem after Lesson 20 (Monday Feb. 19). (Understanding about greedy algorithms will come Wednesday in Lesson 21, but it isn’t necessary to complete this part.)

Imagine you live in a fictional world where one can take any number of credits, and you are limited only by how much effort you want to expend.

To choose our courses, we will use a “greedy” approach, selecting courses until the maximumEffort is succeeded, or all courses have been considered. In Part 2, 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.

class CourseSelector:
    def __init__(self, courses = []):
        self.courses = courses[:] # copy the courses

    def addCourse(self, course):
        self.courses.append(course)

    def chooseCourses(self, maxEffort):
        raise NotImplementedError # implement in subclasses

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 part, you will implement the chooseCourses method 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)

    def greedyChoice(self, course):
        raise NotImplementedError # implement in subclasses

    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
        # greedyChoice (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 with a different implementation of a greedyChoice method 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 (6 credits, 10 effort, 4 value)
  C (6 credits, 2 effort, 4 value)

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

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

Part 2: Different greedy sort orders

# You should be mostly equipped to complete this problem after Lesson 20 (Monday Feb. 19).

For this part, you will make changes in the three child classes of GreedyCourseSelector to implement 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)

    def greedyChoice(self, course):
        # Favor courses with high value, regardless of effort
        return 0 # TODO: replace with your code

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)

    def greedyChoice(self, course):
        # Favor courses with low effort, regardless of value
        return 0 # TODO: replace with your code

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)

    def greedyChoice(self, course):
        # Favor courses with high value-to-effort ratio
        return 0 # TODO: replace with your code

The amount of code you write for this part will probably be really small. Think carefully before attempting to code, and ask questions if you get stuck!

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

Maximum effort: 12

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

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

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

Testing your code

This part isn’t graded, but can help you understand if your code is working as expected.

You can test your code using the same courseData.csv file from Assignment #7. Remember: these are entirely made up randomly, except for CS 111 which has suspiciously high value for the amount of effort…

CS 100,6,5,4
CS 111,6,2,10
CS 200,6,5,9
CS 201,6,8,8
CS 202,6,2,3
CS 208,6,10,6

Download this helper program and save it as chooseCourses.py in the same folder as the rest of your Assignment #8 files.

Copy over your function readScheduleFromCSV from Assignment #7 and put it in chooseCourses.py, then change it to return a list of Course objects instead of a CourseSchedule. 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: 37
  effort: 14
  CS 111 (6 credits, 2 effort, 10 value)
  CS 294 (6 credits, 4 effort, 10 value)
  CS 362 (6 credits, 6 effort, 10 value)
  CS 341 (6 credits, 1 effort, 6 value) 
  CS 232 (6 credits, 1 effort, 1 value) 

Effort greedy result:
  value: 36
  effort: 12
  CS 232 (6 credits, 1 effort, 1 value) 
  CS 341 (6 credits, 1 effort, 6 value) 
  CS 111 (6 credits, 2 effort, 10 value)
  CS 202 (6 credits, 2 effort, 3 value) 
  CS 301 (6 credits, 3 effort, 7 value) 
  CS 332 (6 credits, 3 effort, 9 value) 

Value-to-effort ratio greedy result:    
  value: 43
  effort: 14
  CS 341 (6 credits, 1 effort, 6 value) 
  CS 111 (6 credits, 2 effort, 10 value)
  CS 332 (6 credits, 3 effort, 9 value) 
  CS 294 (6 credits, 4 effort, 10 value)
  CS 301 (6 credits, 3 effort, 7 value) 
  CS 232 (6 credits, 1 effort, 1 value)

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

Grading

This assignment will be graded out of 100 points, as follows:

• 5 points - submit a valid a8.zip file with all files correctly named

• 5 points - your courseSelector.py code file contains top-level comments with file name, purpose, and author names

• 5 points - your courseSelector.py code file’s top-level comments contain collaboration statement

• 10 points - code style enables readable programs

• 34 points - GreedyCourseSelector.chooseCourses method chooses courses using the greedyChoice method (10 pts), without going over maxEffort (10 pts), and returns the total value, effort, and list of the chosen courses (14 pts)

• 36 points - greedyChoice methods correctly provide a value for a given course (12 pts each)

• 5 points - readme.txt file contains reflection

What you should submit

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

• readme.txt (reflection)
• courseSelector.py (Parts 1+2)
• course.py (yours from Assignment #7)
• courseData.csv (to make testing easier)