A First Taste of Algorithms · Lab 4: The Notebook

3. The collapse, measured

Count the memoized version’s calls (the counter rides along in a one-item list — a small trick: numbers passed to functions don’t come back changed, but a list’s contents do, so we keep the count in a box and pass the box):

memo = {1: 1, 2: 2}
calls = [0]

def ways_memo_count(n):
    calls[0] = calls[0] + 1
    if n in memo:
        return memo[n]
    answer = ways_memo_count(n - 1) + ways_memo_count(n - 2)
    memo[n] = answer
    return answer

ways_memo_count(30)
print("memoized calls for n=30:", calls[0])

Set it beside §1’s number for n = 30. Millions against dozens, identical answers. Now the gait check: reset the notebook (rerun the cell after changing 30 to 40, but reset memo and calls first — why must you reset? predict what the count reports if you don’t) and confirm the memoized call count grows like n itself: the straight line that replaced the explosion.

4. Sevenia on trial

The chapter’s recurrence, as a program — for any coin system. The notebook here must be reset per problem, so we wrap the whole trial in one function that builds a fresh memo, then defines the recursive worker inside (a function defined inside a function: new sight, no new idea — the inner worker simply gets to use the outer function’s memo and coins):

def fewest_coins(coins, amount):
    memo = {0: 0}                       # the floor: no debt, no coins

    def best(a):
        if a in memo:
            return memo[a]
        options = []
        for c in coins:
            if c <= a:
                options.append(best(a - c))
        answer = 1 + min(options)       # min: the cheapest priced future
        memo[a] = answer
        return answer

    return best(amount)

print(fewest_coins([10, 7, 1], 14))

Two. The wound closes on your screen. (min of a list is what it says; it has been waiting in Python all along for this chapter.)

Now the full trial — your Chapter 2 greedy versus the table method, every amount to 100. Retype your greedy from Lab 2 (or paste it from your notebook there):

def greedy_change(coins, amount):
    used = []
    for coin in coins:
        while amount >= coin:
            amount = amount - coin
            used.append(coin)
    return used

for amount in range(1, 101):
    g = len(greedy_change([10, 7, 1], amount))
    d = fewest_coins([10, 7, 1], amount)
    if g != d:
        print(amount, "greedy:", g, "  table:", d)

Compare the verdict list with your Lab 2 audit (which used brute force as the truth). Same failures, same truth — but notice what changed about the truth-machine: Lab 2’s three nested loops tried everything; this one prices each amount once. The notebook replaced the brute force. Confirm the new machine’s reach: fewest_coins([10, 7, 1], 900) — instant, where three nested loops would grind.

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