# CS 180 Final Q3 Regrade Request

## 1. Clear definition of DP

DP defintion: stores the maximum reward, given the number of courses taken and the list of courses that need to be taken to receive that reward

## 2. How do to the DP using previously solved

It adds the course that will give the largest reward. If it is a course with no prereqs or a prereq that has already been taken, it will compare it to other courses and add the largest one. If it is a course with a prereq that has not been taken, it will try adding both the prereq and then course and compare it to the “m-2” solution (since two new courses are added).

**Previous regrade requests also explain it:**

“This should be a valid DP solution, since I consider possibilities of classes. In my correctness explanation, I explain how each optimal solution is the maximum reward given a certain number of classes. The first case is a course with no prerequisite, where the course with the largest reward that has not been taken yet is chosen. The next case is a course with a prerequisite that has already been satisfied, and there it adds the course with the largest reward that has not been taken yet. The final case is a course with prerequisite that has not been satisfied, and there it checks whether or not removing the previously added course and adding the two new ones would be better.”

“Based on the given solution, I think mine should also work. Instead of storing courses in a tree, I stored it in a set. Lines 8 and 9 of your solution correspond with my first for loop, where only one course is allowed to be taken (iterate through all courses with no prereqs, find course with largest reward). Line 20 of your solution corresponds with my case where there exists a prereq for a course so it cannot be taken (can only select from 0th child subtree = can only choose courses that have no prereq or has prereq already satisfied). Lines 29-31 correspond with being able to choose a class where a prerequisite has already been satisfied (choosing from children of tree = choosing from courses with satisfied prerequisites).”

## 3. Code w/ comments

Note: this is pseudocode, but using Python syntax highlighting

Opt(m, C) stores the max reward from m courses stored in set C
# C stores all the courses taken to get that reward

# Case where only one course is taken
For every course n with no prerequisite:
    Opt(1, C) = max( Opt(1, c), r_n) (update C accordingly)

# Case where m > 1 courses are taken
For k from 2 to m:
    For every course i not yet taken:
        # No prerequisite: can add the course with the largest reward
        If course i has no prerequisite:
            New_course = Opt(k-1, C) + r_i # reward with new course
            Opt(k, C) = max( Opt(k, C), New_course) # store larger reward
        
	# Has prerequisite: must check whether prereq has been taken
	# or if it must also be taken
        If course i has a prerequisite:
            # Check if prerequisite has been taken
            If prerequisite is in set C from Opt(k-1, C) (already taken):
                New_course = Opt(k-1, C) + r_i # reward with new course
                Opt(k, C) = max( Opt(k, C), New_course) # store larger reward
            
            # Prerequisite has not been taken, will have to add both courses
            If prerequisite j is not in set C (has not taken yet):
                New_courses = Opt(k-2, C) + r_i + r_j # reward with two new courses
                Opt(k, C) = max( Opt(k, C), New_courses) # store larger reward
    
	# Keep track of all courses that have been taken (for checking prereqs)
        Update C to be the set of all courses taken

# Return reward with m courses taken
Return Opt(m, C)

## 4. Knapsack example

The knapsack problem chooses between the maximum value with item T, or the maximum value without item T. My solution chooses between the maximum reward with a course i, or the maximum value with course i and its prerequisite. By going down each branch in picture 1, it explores the options for choosing courses, ending at a point where the maximum number of courses has been taken. Mine also does this but with a set, where it explores options for choosing courses (taking the one with the largest reward), ending at a point where the maximum number of courses has been taken. The maximum number of courses is equivalent to the weight of going down each branch, and the maximum reward is equivalent to the reward on the leaf nodes (courses).