A First Taste of Algorithms

Problem Set 4

✦ ✦ ✦

Lab 4 (The Notebook) is the Computational Lab tier. Problems 2.5 and 3.2 want your lab code as equipment.

Fluency

1.1 Extend the staircase table by hand to n = 12 using the recurrence. Then answer from the table, no new work: a 12-step staircase where the first hop was a 2 — how many ways remain?

1.2 For ways(7), draw the full amnesiac call tree and count how many times each of ways(1) through ways(6) is computed. Then list, in order, the calls the memoized version actually computes (not looks up) when asked ways(7) cold.

1.3 Build the Sevenia table bottom-up from 15 to 22, continuing the chapter’s table. At which amounts in that range does greedy (from your Chapter 2 audit) disagree, and by how much?

1.4 US coins {1, 5, 10, 25}: build the best(a) table to a = 30 and verify it agrees with greedy at every entry. (Chapter 2’s deep water explains why this agreement, continued to 34, is a certificate.)

1.5 Fill in the complete 4 × 5 edit-distance table for “cap” → “tape” (rows: prefixes of “cap” including empty; columns: prefixes of “tape” including empty). Confirm the corner says 2, and trace one optimal edit sequence back through the table.

1.6 Edit distance of “kitten” → “sitting” is famously 3. Name three edits that achieve it; the table (optional, 7 × 8) certifies nothing beats them.

Practice

2.1 Triple staircase: hops of 1, 2, or 3 allowed. Derive the recurrence and floor, build the table to n = 10, and find how many ways to climb 10 steps.

2.2 City grid: you stand at the corner of 1st & 1st and walk to 5th & 7th moving only north or east one block at a time. Set up ways(street, avenue) as a table-method problem — what is the recurrence, what is the floor (think: edges of the grid), and how many routes exist? Then the variant: the corner at 3rd & 4th is closed. One table entry changes its rule; recount.

2.3 Toll staircase: step k charges a toll t(k), and you pay the toll of every step you land on. For tolls (steps 1 through 8) = 3, 1, 4, 1, 5, 9, 2, 6, find the cheapest climb to the top of step 8 with hops of 1 or 2. State the recurrence (min now, not sum), build the table, and recover which steps the cheapest climb lands on.

2.4 Counting versus optimizing: the Sevenia recurrence used min; the staircase used sum. Write the recurrence for “how many different ways can Sevenia’s coins pay amount a, where order of handing over matters” and compute the table to a = 12. Why does the same skeleton serve both questions?

2.5 Use your lab’s DP changer on the stamp system {1, 4, 9} (Problem 2.3 of Chapter 2) for all amounts to 50: list every amount where greedy overpays and the worst overpayment in the range. Then design a three-coin system (with a 1) where greedy’s worst overpayment on amounts up to 100 is as large as you can make it — beat your Chapter 2 entry now that you own the truth-machine.

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