Assignment: Dynamic Programming & Backtracking
1. Solve Dynamic Programming Problem and find its optimal solution.
Given a set of numbers, return a subset of non-consecutive numbers that would have the
maximum sum.
For example: Input: [7,2,5,8,6]
Output: [7,5,6] (This will have sum of 18)
Note: The numbers can include negative numbers as well.
a. Write the recurrence formula to solve this problem using dynamic programming
b. Write the pseudocode to solve the problem using dynamic Programming technique.
c. Implement the solution of this problem using dynamic Programming. Name your
function max_independent_set(nums). Name your file MaxSet.py
d. What is the time complexity of your implementation?
2. Implement a backtracking algorithm
a. Write the implementation to solve the powerset problem. Name your function
powerset.py. Name your file PowerSet.py
b. What is the time complexity of your implementation?
Debriefing (required!): --------------------------
Report:
1. Approximately how many hours did you spend on this assignment?
2. Would you rate it as easy, moderate, or difficult?
3. How deeply do you feel you understand the material it covers (0%–100%)?
4. Any other comments?
Note: ‘Debriefing’ section is intended to help us calibrate the assignments.
