Skip to main content

Module Quiz

Complete this quiz after finishing all concept and practice pages. Quiz solutions include the recurrence derivation, not just the numeric answer.

Current Module Questions​

Question 1: Licensing DP​

What are the two structural conditions a problem must satisfy for DP to be applicable, and why does each matter?

Answer: Optimal substructure (an optimal solution contains optimal solutions to smaller subproblems) and overlapping subproblems (the same subproblem recurs many times). Optimal substructure lets us combine subproblem answers into a correct whole; overlapping subproblems lets caching turn exponential recursion into polynomial computation.

Question 2: The Cut-and-Paste Argument​

What does the "cut-and-paste" argument show, and on which problem is it classically applied?

Answer: It shows optimal substructure by contradiction: if an optimal solution's restriction to a subproblem were suboptimal, we could "cut" it out and "paste" in a better subproblem solution, strictly improving the whole, contradicting optimality. Classical examples: shortest path (subpath optimality) and rod-cutting.

Question 3: Counting Distinct Subproblems​

The naive Fibonacci recursion F(n) = F(n-1) + F(n-2) makes exponentially many calls. Why does memoization reduce it to linear time?

Answer: There are only n+1 distinct subproblems (F(0), F(1), ..., F(n)). Without caching, the recursion recomputes each one many times along different branches. With memoization, each subproblem is computed once and reused in O(1), so the total work is O(n).

Question 4: Memoization vs Tabulation​

Give one scenario where memoization is strictly preferable and one where tabulation is strictly preferable.

Answer: Memoization is preferable when the state space is large but only a sparse subset is actually reachable (so tabulation would waste work on unreachable states). Tabulation is preferable when every state is visited and the fill order is simple, because it avoids recursion overhead and is amenable to rolling-array space reduction.

Question 5: Edit Distance Recurrence​

Write the edit distance recurrence for strings s[1..m] and t[1..n] with unit cost operations, with base cases.

Answer:

  • Base cases: dp[0][j] = j (insert j chars), dp[i][0] = i (delete i chars).
  • Recurrence:
    dp[i][j] = dp[i-1][j-1] if s[i] == t[j],
    otherwise dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    (corresponding to delete, insert, substitute).

Question 6: 0/1 Knapsack Loop Direction​

For 0/1 knapsack using a 1D rolled array dp[c], why must the capacity loop iterate in descending order?

Answer: Descending order ensures each item is used at most once. When computing dp[c] = max(dp[c], dp[c - w] + v), we need dp[c - w] to still represent the value before this item was considered. Ascending order would let the same item be consumed multiple times, turning the recurrence into unbounded knapsack.

Question 7: LIS in O(n log n)​

Describe what the tails array represents in patience-sorting LIS, and state why binary search inside it is valid.

Answer: tails[k] is the smallest possible tail value among all increasing subsequences of length k+1 seen so far. tails is strictly increasing by construction (a length-k+1 subsequence can be extended to length-k+2 with an element larger than its tail), so binary search correctly finds the leftmost position where the next element would replace or extend it.

Question 8: Reconstruction Necessity​

Why does storing only dp[i][j] values sometimes fail to let you recover the optimal object?

Answer: The value of dp[i][j] tells you the optimum but not which transition achieved it when several predecessors tie or when the recurrence is non-monotonic. You either need a parent/choice array recorded during the forward fill, or you must re-derive the transition by comparing dp[i][j] against its predecessors at reconstruction time.

Question 9: Matrix Chain Recurrence​

For matrices with dimensions p[0..n] so that A_i has shape p[i-1] x p[i], write the matrix-chain recurrence and its fill order.

Answer:

  • Base: dp[i][i] = 0.
  • Recurrence for i < j:
    dp[i][j] = min over k in [i, j-1] of ( dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j] ).
  • Fill order: by increasing interval length L = j - i + 1, from L = 2 up to L = n. Row-major fill is wrong because dp[i][j] depends on dp[i][k] and dp[k+1][j] whose intervals are shorter but can have larger starting indices.

Question 10: Interval DP on Balloon Burst​

In the balloon-burst problem, why is it natural to recurse on the last balloon burst in a range rather than the first?

Answer: If you pick the last balloon k to burst in range (i, j), then when it bursts all other balloons in (i, j) are already gone, so its neighbors are exactly a[i] and a[j] (the fixed boundary balloons). This gives a clean recurrence dp[i][j] = max over k in (i, j) of ( dp[i][k] + dp[k][j] + a[i]*a[k]*a[j] ). Recursing on the first burst makes the neighbor structure depend on subsequent bursts, which breaks optimal substructure.

Question 11: Tree DP​

Write the recurrence for maximum-weight independent set on a tree, using states dp[v][0] (v not chosen) and dp[v][1] (v chosen).

Answer: For a post-order traversal of the tree,

  • dp[v][0] = sum over children c of max(dp[c][0], dp[c][1])
  • dp[v][1] = w[v] + sum over children c of dp[c][0]

Final answer: max(dp[root][0], dp[root][1]).

Question 12: Bitmask TSP​

State the Held-Karp recurrence dp[S][j] for TSP and its complexity.

Answer: Let dp[S][j] be the minimum cost of a path starting at city 0, visiting exactly the cities in S, and ending at j in S. Then

dp[S][j] = min over i in S, i != j, 0 in S of ( dp[S \ {j}][i] + d[i][j] ).

Final answer: min over j of ( dp[full][j] + d[j][0] ). Complexity: O(2^n * n^2) time, O(2^n * n) space.

Question 13: Digit DP State​

For counting integers in [0, N] satisfying a digit-based property, what do the flags tight and leading_zero represent in state dp[pos][...][tight][leading_zero]?

Answer: tight tracks whether the prefix so far equals N's prefix, so the next digit is bounded above by N's digit at pos; otherwise it is free to be 0..9. leading_zero tracks whether the number is still all zeros (so leading zeros should not count as real digits for constraints like "distinct non-zero digits"). When leading_zero ends (first non-zero placed), the real digit constraints take effect.

Question 14: Greedy Failure on 0/1 Knapsack​

Give a small input where "greatest value-per-weight first" fails for 0/1 knapsack, and explain why.

Answer: Items: (w=1, v=2), (w=3, v=5), (w=4, v=6), capacity W = 4. Greedy by ratio picks item 1 (ratio 2.0) then item 2 (ratio 1.67), total weight 4, value 7. But picking item 3 alone gives value 6, and picking items 2 plus 1 gives value 7 = greedy here. Adjust: (w=2, v=3), (w=3, v=4), capacity W=4: greedy picks item 1 (ratio 1.5) leaving W=2 idle, value 3; optimal picks item 2 alone, value 4. Greedy commits to a locally best ratio and cannot backtrack when the remaining capacity is wasted.

Question 15: Paradigm Selection​

Given shortest path with nonnegative edges, longest path on a general graph, and longest path on a DAG, which is polynomial and which is NP-hard? Explain in one sentence each.

Answer: Shortest path with nonnegative edges is polynomial via Dijkstra. Longest path on a general graph is NP-hard (it encodes Hamiltonian path). Longest path on a DAG is polynomial: a topological order gives a natural DP fill order and the acyclic structure prevents cycle-pumping that breaks longest path in general graphs.

Interleaved Review Questions​

Prior Module Question 1​

What is the master theorem, and what kind of recurrences does it solve?

Answer: The master theorem gives closed-form asymptotic solutions to divide-and-conquer recurrences of the form T(n) = a T(n/b) + f(n) by comparing f(n) with n^{log_b a}. It does not apply to DP-style recurrences like T(n) = T(n-1) + T(n-2) + O(1), which are better analyzed directly.

Prior Module Question 2​

What does O(n log n) comparison-sort lower bound tell you about patience-sorting LIS?

Answer: The lower bound is about comparison-based sorting, not LIS. Patience-sorting LIS runs in O(n log n) per-element work via binary search, matching the sorting-like bound but solving a different problem. Its correctness does not rely on the sorting lower bound.

Prior Module Question 3​

State asymptotic growth: is 2^n polynomial, pseudo-polynomial, or exponential? What about n * W for 0/1 knapsack?

Answer: 2^n is exponential in the input size n (number of items). n * W is pseudo-polynomial: polynomial in the numeric value W, but exponential in the bit length of W. That is why 0/1 knapsack is NP-hard despite the O(nW) DP.

Prior Module Question 4​

Why is correctness proof by induction sufficient for a DP?

Answer: Because DP computes answers in an order that respects dependencies (topological over the subproblem DAG). We prove the recurrence correctness for each subproblem assuming all smaller subproblems are correct -- exactly strong induction on the partial order of the subproblem DAG.

Prior Module Question 5​

What does it mean for an algorithm to be greedy?

Answer: A greedy algorithm makes the locally best choice at each step and never revises it. It is correct only if a provable property (greedy-choice property via exchange argument, or the matroid property) guarantees that local choices are consistent with a global optimum.

Self-Assessment and Remediation​

Mastery Level (90-100% correct):

  • Ready to advance. Push on harder DP variants and optimization problems.

Proficient Level (75-89% correct):

  • Review missed concept pages and redo the matching kata until the recurrence comes from memory.

Developing Level (60-74% correct):

  • Rework Clusters 1 and 2 and redo Practice 1 and 2. Prove that you can state the recurrence before any coding.

Insufficient Level (<60% correct):

  • Return to Cluster 1. The substructure and subproblem-overlap arguments are the ceiling for everything else; do not skip them.