Standard 18: Dynamic Programming 3: Solve From Scratch

Short description: Solve DP problems without scaffolding; justify correctness.

Relevant notes: Topic F: Dynamic Programming.

Full description

Given a dynamic programming problem, design a full solution and justify correctness. Clearly identify the DP components of the solution.

Example problem

In the longest common subsequence problem, our goal is to compare two sequences to find the longest subsequence that they have in common. Recall that a subsequence does not have to be consecutive.

Input: two sequences A and B (we will suppose the elements are characters or inetegers). Let n = length(A) and m = length(B).
Output: the length of the longest sequence that is a subsequence of both A and B.

Give a dynamic programming algorithm for this problem. To do so, give each component of the DP solution. Briefly justify correctness. Then, briefly give an outline of the whole algorithm.

Note: You only need to output the optimal length, not a subsequence itself.

Sample solution

Sample solution.

Subproblem definition: we let C[i,j] = the length of the longest common subsequence of A[1:i] and B[1:j], where A[1:i] denotes the prefix of A from characters 1 to i and similarly for B[1:j].

Compute the final answer: we just return C[n,m], which is correct because this is the LCS of A and B.

Recurrence base case: C[0,j] = 0 for all j and C[i,0] = 0 for all i. This is correct because if either input has zero characters, then the answer is zero, so

Recurrence inductive case: to set C[i,j] for i,j >= 1, we do:

let a = 1 + C[i-1,j-1] if A[i] == B[j], else let a = 0
let b = C[i-1,j]
let c = C[i,j-1]
and let C[i,j] = max{a, b, c}.

Justification of inductive case: there are two cases: A[i] == B[j] or not. If so, the LCS may include this character. If so, its length is 1 + C[i-1,j-1], because it consists of this final character appended to the LCS of A[1:i-1] and B[1:j-1].

If A[i] != A[j] or the LCS doesnt' include this character, then the LCS is the same as that if we chopped this character off of one of the strings. If we chop it off A, then the LCS equals C[i-1,j], and if we chop it off B, then the LCS equals C[i,j-1].

We have covered all the possibilities for the optimal LCS, and our recurrence takes the best over these possibilities, so it is correct.

Algorithm outline:

We initialize C[i,0] = 0 for all i and C[0,j] = 0 for all j.
For i from 1 to n, for j from 1 to m: we set C[i,j] = max{a, b, c} where a,b,c are defined above.
At the end, we return C[n,m].

Rubric

Rubric.

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

To pass, a solution must identify all of the parts: subproblem definition, compute the final answer, and recurrence base and inductive cases. It must justify the correctness of with a proof or proof sketch. It must give an algorithm outline that describes in what order to solve the subproblem. All of the above must be correct. If there is another correct solution than the sample solution, that will be accepted if all else is correct, but it must be clear and easy to follow.

The numerical rubric for this problem is:

4 (Pass, Near-Perfect): correct answers, clear, brief.
3 (Pass, Proficient): correct answers and justifications. May give brief or high-level justifications as long as they claim correct things and not too many steps are skipped. A minor typo or two can be accepted if the rest of the solution is correct and the intention is correct and clear from context.
2 (Fail, Progress): may have one or more incorrect components or incorrect justifications. May not give an algorithm outline or may not solve the subproblems in the correct order (however, nesting the for loops in either order is correct here). May state incorrect things or excess, unnecessary things.
1 (Fail, Wrong Track): May incorrectly identify the missing components. May mis-use terms or appear to address the wrong problem.