A First Taste of Algorithms · Problem Set 4

Concept & Counterexample

3.1 Claim: “memoization speeds up any recursion.” Use merge sort to refute it precisely: say what the memo’s keys would be, why almost no key is ever asked twice, and what the notebook costs while earning nothing. State the missing ingredient by name.

3.2 Claim: “the table method always beats greedy.” Cheap shot, but make it precise: on US coins both are optimal — so compare their costs (table entries built vs. greedy’s steps) for amount 10,000. When greedy is right, what is it, in the table method’s terms? (Look at what greedy refuses to price, and what that refusal saves.)

3.3 Claim: “ways(n) counts climbs, so by symmetry, climbs that start with a 1-hop and climbs that end with a 1-hop are equally numerous.” Decide by computing both counts for n = 5 from the table and an argument, not enumeration. Then give the one-sentence reason (a staircase climbed backward is…).

3.4 The coupled trip, uncoupled. You have 7 days and $400. Each city i offers joy(i) but costs days d(i) and dollars m(i), and no city twice. “Best trip = best 3-day trip + best 4-day trip” fails — exhibit a tiny 3-city instance where it fails. Then design the state that restores substructure (what two quantities must a subproblem’s question carry?) and write the recurrence. Do not fill the table; designing it is the problem.

3.5 Claim: “bottom-up and top-down always do the same work.” Find the crack: design a coin system and amount where top-down never asks about most amounts (which ones can it skip and why?), while bottom-up dutifully fills every entry. (Hint: coins {1000, 2000}, amount 10,000 — wait, where did the 1 go? What does best(a) even mean for unpayable a, and how must the recurrence’s min handle it? Two design decisions hide in this innocent claim.)

Diamond

4.1 The recurrence is a theorem. Prove: for any coin system C containing 1 and any amount a ≥ 1, best(a) = 1 + min over c in C, c ≤ a, of best(a − c). Two inequalities, two cut-and-paste arguments: (a) ≤ (the recurrence can be achieved): for the minimizing coin c, take any optimal payment of a − c and add one c. Verify this pays a legally and count it. (b) ≥ (nothing beats the recurrence): take any optimal payment of a; it contains some first coin c. Remove it. Prove what remains must be an optimal payment of a − c — suppose it weren’t, paste in a better one, and exhibit the contradiction with the optimality you started from. (This paste is the heart; write it slowly.) (c) One sentence each: where exactly does (b)’s paste fail for the two-week-trip problem of the deep water, and where does the greedy argument — which also picks “some first coin” — part ways with yours?

Computational Lab

5.1 Lab 4 in full, predictions before runs. The shared-notebook Break-it (one memo, two coin systems) is required preparation for Teach It 6.2 — bring the wrong answer it produced.

Teach It

6.1 Teach someone the staircase count with real stairs or taped floor squares, in this order: have them enumerate 3 and 4 steps by walking; show them the first-hop argument; then ask them to predict 5 steps before enumerating, and let the staircase grade them. Three sentences on what convinced them — the walking or the argument.

6.2 Tell the two-disguise story — Lucas’s Siamese professor, Bellman’s bureaucrat-proof name — to someone, and then explain what the method behind the boring name actually does, using Sevenia’s 14 with coins on the table: greedy’s grab, then the notebook’s trial of every branch. End with the lab’s shared-notebook bug and ask them: whose fault was the wrong answer — the method’s, or the notebook-keeper’s? Report their verdict.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses