Standard 17: Dynamic Programming 2: Fill in

Short description: Given portions of a DP solution, complete the algorithm; justify correctness.

Relevant notes: Topic F: Dynamic Programming.

Full description

Given a dynamic programming problem and parts of the algorithm, fill in the missing parts. Justify correctness. The missing parts may be parts of the recurrence or computing the final solution.

Example problem

Consider the problem of knapsack with no duplicates:

Input: value v[i] and weight w[i] of each item i=1,...,n. Weight limit W.
Output: the largest possible value obtained by a subset of the items with total weight at most W.

Consider this dynamic programming partial solution:

Subproblem definition: C[i,x] = maximum value of a subset of 1,...,i with total weight at most x.
Final answer: return C[n,W].
Recurrence, base cases: C[0,x] = 0 for all x, and C[i,0] = 0 for all i.

Part a. What mandatory component is missing? Fill it in and prove correctness.

Part b. What optional component is missing? Briefly explain how to obtain that component.

Sample solution

Sample solution.

Part a.

The recurrence, inductive case: C[i,x] = max(C[i-1,x], v[i] + C[i-1, x-w[i]]) where the second case is only considered if w[i] <= x.

Proof: to fill a knapsack of weight limit x with items 1,...,i, the optimal solution either has item i or doesn't. If it doesn't, then it has a subset of items 1,...,i-1, so its value is equal to C[i-1,x]. If it does, then the remaining space is x - w[i] and it must be used optimally, so its value is C[x - w[i]], so the total value is v[i] + C[i-1, x-w[i]].

We take the maximum over these two possibilities, so C[i,x] is the optimal solution.

Part b. Reconstructing the solution.

We can create an array D[i,x] = False if C[i,x] == C[i-1,x], and otherwise D[i,x] = True, meaning that C[i,x] == v[i] + C[i-1,w-w[i]] and we used item i at this stage.

We then start with D[n,W]. If False, we go to D[n-1, W]. If True, we add item n to the knapsack and go to D[n-1, W - w[n]]. We continue in this way until we get to D[0,x] for any x.

Rubric

Rubric.

To pass, a solution must follow the course requirements for writing and proofs.

To pass Part a, the solution must identify that the recurrence inductive case is needed, give the correct recurrence, and give a correct justification. The justification can be brief, but must still give a correct, useful justification.

To pass Part b, the solution must identify reconstructing the solution. It should give a correct, clearly understandable method for reconstruction.

The numerical rubric for this problem is:

4 (Pass, Near-Perfect): correct answers, clear, brief.
3 (Pass, Proficient): correct answers. In Part a, the proof sketch is easily understandable and follows guidelines for writing and proofs. The sketch may omit some justifications if it is otherwise excellent. In Part b, may use a different strategy than the sample solution if it is otherwise excellent: easy to follow, clear, no missing steps, very little unncessary writing or irrelevant material. Small changes in naming are allowed if the solution is otherwise correct, e.g. "recursive case" instead of "inductive case" or "producing the object" instead of "reconstructing the solution".
2 (Fail, Progress): one or more incorrect answers. May not identify the components correctly. In Part a, may give an incorrect recurrence or a justification that does not pass the course requirements for writing and proofs. In Part b, may give an incorrect strategy or fail to clearly explain the strategy.
1 (Fail, Wrong Track): May incorrectly identify the missing components. May mis-use terms or appear to address the wrong problem.