Quiz #5: Solutions
1. If a DP algorithm needs to solve Θ(n2) subproblems, like the ones discussed in lectures, then its space complexity is at least Θ(n2) because we need to store the results of all subproblems.
Solution: False. A counterexample is the linear-space alignment. This is pretty common.
2. If a DP formulation consists of 2n2 subproblems, then we need to solve most of them before we can
get the final answer, i.e., Θ(n2) subproblems excluding some trivial boundary cases.
Solution: False. For example, in the edit distance problem, if we are sure the distance won’t exceed k = o(n) (e.g., a constant or Θ(log n)), we can skip subproblems Θ(k)-unit far away from the diagonal line, i.e., OPT(i, j) with roughly |i − j| > k, and only solve the rest O(nk) subproblems. This is not very common, though, because we usually don’t know k in advance, and we have to start over to try a larger k.
In general, if the recurrence is equivalent to that of the shortest distance problem and we believe the ultimate distance is relatively short, we can adopt Dijkstra’s algorithm to solve less subproblems at the cost of extra O(log n) time at every visited subproblem.
3. Assume the recurrence is f (n) = maxi:1≤i