blog-static/code/cs325-langs/hws/hw6.txt

CS 325-001, Algorithms, Fall 2019
HW6 - DP (part 2)

Due on Monday Nov 4, 11:59pm.
No late submission will be accepted.

Need to submit: report.txt, knapsack_unbounded.py, knapsack_bounded.py.
knapsack_bounded.py will be graded for correctness (1%).

To submit:
flip $ /nfs/farm/classes/eecs/fall2019/cs325-001/submit hw6 report.txt knapsack*.py
(You can submit each file separately, or submit them together.)

To see your best results so far:
flip $ /nfs/farm/classes/eecs/fall2019/cs325-001/query hw6

Textbooks for References:
[1] KT Ch. 6.4
    or Ch. 5.3 in a previous version:
    http://cs.furman.edu/~chealy/cs361/kleinbergbook.pdf   
[2] KT slides for DP (pages 1-37):
    https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/06DynamicProgrammingI.pdf
[3] Wikipedia: Knapsack (unbounded and 0/1)
[4] CLRS Ch. 15

Please answer time/space complexities for each problem in report.txt.

0. For each of the coding problems below:
   (a) Describe a greedy solution.
   (b) Show a counterexample to the greedy solution.
   (c) Define the DP subproblem 
   (d) Write the recurrence relations
   (e) Do not forget base cases
   (f) Analyze the space and time complexities

1. Unbounded Knapsack

   You have n items, each with weight w_i and value v_i, and each has infinite copies.
   **All numbers are positive integers.**
   What's the best value for a bag of W?

   >>> best(3, [(2, 4), (3, 5)])
   (5, [0, 1])

   the input to the best() function is W and a list of pairs (w_i, v_i).
   this output means to take 0 copies of item 1 and 1 copy of item 2.

   tie-breaking: *reverse* lexicographical: i.e., [1, 0] is better than [0, 1]:
   (i.e., take as many copies from the first item as possible, etc.)

   >>> best(3, [(1, 5), (1, 5)])
   (15, [3, 0])

   >>> best(3, [(1, 2), (1, 5)])
   (15, [0, 3])

   >>> best(3, [(1, 2), (2, 5)])
   (7, [1, 1])

   >>> best(58, [(5, 9), (9, 18), (6, 12)])
   (114, [2, 4, 2])

   >>> best(92, [(8, 9), (9, 10), (10, 12), (5, 6)])
   (109, [1, 1, 7, 1])

   Q: What are the time and space complexities?

   filename: knapsack_unbounded.py

2. [WILL BE GRADED] 
   Bounded Knapsack

   You have n items, each with weight w_i and value v_i, and has c_i copies.
   **All numbers are positive integers.**
   What's the best value for a bag of W?

   >>> best(3, [(2, 4, 2), (3, 5, 3)])
   (5, [0, 1])

   the input to the best() function is W and a list of triples (w_i, v_i, c_i).

   tie-breaking: same as in p1:

   >>> best(3, [(1, 5, 2), (1, 5, 3)])
   (15, [2, 1])

   >>> best(3, [(1, 5, 1), (1, 5, 3)])
   (15, [1, 2])

   >>> best(20, [(1, 10, 6), (3, 15, 4), (2, 10, 3)])
   (130, [6, 4, 1])

   >>> best(92, [(1, 6, 6), (6, 15, 7), (8, 9, 8), (2, 4, 7), (2, 20, 2)])
   (236, [6, 7, 3, 7, 2])

   Q: What are the time and space complexities?

   filename: knapsack_bounded.py

   You are encouraged to come up with a few other testcases yourself to test your code!
   
Debriefing (required!): --------------------------

0. What's your name?
1. Approximately how many hours did you spend on this assignment?
2. Would you rate it as easy, moderate, or difficult?
3. Did you work on it mostly alone, or mostly with other people?
4. How deeply do you feel you understand the material it covers (0%-100%)? 
5. Which part(s) of the course you like the most so far?
6. Which part(s) of the course you dislike the most so far?

This section is intended to help us calibrate the homework assignments. 
Your answers to this section will *not* affect your grade; however, skipping it
will certainly do.