View Submission | Gradescope 2021/4/29, 3:13 PM
Q1 Dynamic programming 35 Points
Recall that whenever you’re asked to state an answer, you don’t need to explain.
Q1.1 — Longest Common Subsequence (LCS)
(1) When X[i] = Y[j], we use c(i, j) = 1 + c(i−1, j−1).
Why is this correct?
Note that simply translating the formula into English is not a full justification.
When i and j are both larger than zero and xi = yi, this formula is correct. When we increment I and j and find out Xi = Yj, we add one new element to the new tablet c. For what was in c(I-1, j-1), c(I,j) has one more element because X[I]=Y[j].
(2) When X[i] = Y[j], why is it correct to recurse on max{c(i, j−1), c(i−1, j)}?
It is correct to do so because when X[I] is not equal to Y[j], we do not have a new element to add to the new tablet c. We will have the larger LCS from the previous c tablet element since there is no new common subsequence.
(3) State one situation where you would rather be using top- down dynamic programming instead of bottom-up.
In one sentence, why would top-down be preferred?
Top down with memoization follows natural recursion and saves the answer to all subproblems in its process. So when we need an answer to a subproblem we can see if we already have the answer to save time. For example, counting paths can be better found with top down. We are
https://www.gradescope.com/courses/227622/assignments/1203208/submissions/76812433 Page 1 of 8
View Submission | Gradescope 2021/4/29, 3:13 PM
Q1.2 — Practice problem 5 extension
Suppose there is a grid of buckets, with k rows and n columns, enumerated 1…k top-down, and 1…n left-to-right. Don’t assume k