A First Taste of Algorithms · Lab 4: The Notebook

5. The same table, bottom-up

The chapter promised the notebook can be filled by a plain loop, floor upward, no recursion at all:

def fewest_coins_table(coins, amount):
    best = [0]                          # best[0] = 0; the table grows rightward
    for a in range(1, amount + 1):
        options = []
        for c in coins:
            if c <= a:
                options.append(best[a - c])
        best.append(1 + min(options))
    return best

table = fewest_coins_table([10, 7, 1], 14)
print(table)
print("best(14) =", table[14])

Read the printed list against the chapter’s hand-built table — entry by entry, they must agree (the table is the method; the two routes merely fill it in different orders). This version climbs to any height without a call stack: try amount 5,000, then try the same in §4’s recursive version and witness which one meets Lab 3’s old enemy.

Break it

Predict first. Run second. Explain any gap third.

1. In §2’s ways_memo, delete only the line memo[n] = answer (keep everything else). Predict: still correct? still fast? one or the other? Run §3’s count with the line gone. Which single line of this lab was the entire chapter?

2. Sabotage by sharing: move §4’s memo = {0: 0} outside the function (one notebook for all trials), then run fewest_coins([10, 7, 1], 14) followed by fewest_coins([25, 10, 5, 1], 14). Predict both outputs first. The second answer is wrong — wrong how, and in whose favor? State the moral as one sentence about what a notebook entry silently assumes. (This bug, in grown-up systems, is called cache poisoning, and it has caused real outages; you have now caused one in eleven lines.)

3. Hops of {2, 3} only: adapt ways_memo for a staircase where you may hop 2 or 3 steps. The floor needs care — decide what ways(0) and ways(1) should be (is “do nothing” a way to climb zero steps? is 1 climbable at all?), write your floor, and test against hand counts for n = 2, 3, 4, 5. Then break a classmate’s floor: find the n where a plausible-but-wrong floor (say, ways(0) = 0) first gives a wrong count. Floors are where recursions are won and lost.

4. In §5’s bottom-up changer, feed it a kingdom without the 1-coin: fewest_coins_table([10, 7], 11). Predict the failure mode precisely — wrong answer, error, or silence? — and read what actually happens to its last line. Then repair the design: unpayable amounts need an answer that survives min and + 1 honestly (the chapter’s Problem 3.5 is circling this same hole). Propose a fix, implement it, and verify amount 11 reports “impossible” while 17 reports 2.

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