Dynamic Programming: Optimal Substructure and Overlapping Subproblems · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Remember each small answer once

Computing · Algorithms & Data Structures · ages 20-21
Name ______________________   Date ____________

  1. Naive fib(20) makes over 20,000 calls because it recomputes the same small values again and again.

    Circle one:   True   False

  2. In this method, what is the recurrence?

    • The smallest version you answer directly
    • The rule that builds a big answer from smaller answers
    • A stored copy of a past answer

  3. What should you write down before any code for such a problem?

    • The subproblem and the recurrence
    • The fastest computer available
    • The final answer from memory

  4. The memoised version computes each of fib(0) through fib(20) exactly once. How many values is that?

    Answer: ______________

  5. Why does storing answers save nothing when moving a stack of rings?

    • The moves are too small to be worth storing
    • Rings cannot be counted by a program
    • Each smaller move happens only once

  6. Mergesort splits data into pieces that are all distinct. Which condition for the method fails?

    • Overlapping subproblems
    • A known base case
    • A written recurrence

  7. A friend says storing answers speeds up every recursion. What is the best reply?

    • True, storage always helps any recursion
    • True, but only for tiny inputs
    • Only when the answer builds from smaller ones that repeat

  8. On the longest simple path, reusing vertices breaks building big answers from smaller ones. Which condition fails?

    • Storing too many answers at once
    • Optimal substructure
    • A small base case
LightMySky · lightmysky.comW1-mt__hWkCDnzNY-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Remember each small answer once W1-mt__hWkCDnzNY-s1

  1. True · The same values reappear constantly, and the naive version solves each from scratch.
  2. The rule that builds a big answer from smaller answers · The recurrence says how a bigger problem breaks into smaller ones plus a little extra work.
  3. The subproblem and the recurrence · State the subproblem and the recurrence before writing any code.
  4. 21 · Counting 0 through 20 inclusive gives 21 values, each done in constant extra work.
  5. Each smaller move happens only once · Nothing repeats, so there is never a stored answer to reuse.
  6. Overlapping subproblems · Its pieces never repeat, so the overlap condition fails and storing saves nothing.
  7. Only when the answer builds from smaller ones that repeat · Both conditions must hold: buildup from smaller answers plus repeats worth storing.
  8. Optimal substructure · The best whole answer is not built from best smaller answers here, so buildup fails.
Worksheet · LightMySky