A First Taste of Algorithms

Lab 4: The Notebook

✦ ✦ ✦

Accompanies Chapter 4. The chapter caught a correct recursion wasting its life on repetition, and tore the exponential down with a notebook. In this lab the waste is counted call by call, the notebook is built, and your own Chapter 2 greedy is put on trial against a changer that cannot lose.

1. The amnesiac, counted

The staircase recursion, plus the counting trick from Lab 3 — each call reports the total number of calls it caused, alongside its answer, as a two-item list [answer, calls]:

def ways_count(n):
    if n <= 2:
        return [n, 1]                     # ways(1)=1, ways(2)=2; one call
    a = ways_count(n - 1)
    b = ways_count(n - 2)
    return [a[0] + b[0], a[1] + b[1] + 1]

print(ways_count(6))
print(ways_count(10))

Check ways(6) against the chapter’s hand count — and check the call count against your drawing of the tree (the chapter said fifteen boxes; does the machine agree?). Now the audit, in the house style:

for n in [10, 15, 20, 25, 30]:
    result = ways_count(n)
    print(n, "ways:", result[0], "  calls:", result[1])

Read the calls column the way you read every table in this book: n goes up by 5 each row — what happens to the calls? This is not Chapter 1’s logarithm and not even Chapter 3’s doubling-per-step; measure its gait (each row is roughly how many times the previous?). Run n = 34 and feel the pause before the answer — the first time in this book the machine has kept you waiting. The answer is a seven-digit number you could extend by hand in seconds. All that waiting was repetition.

2. The notebook

Python’s notebook is the dictionary: like a list, but indexed by question rather than by position. Three moves to learn, all visible here:

memo = {}                 # an empty notebook
memo[7] = 13              # write: next to question 7, answer 13
print(7 in memo)          # ask: is question 7 already answered?
print(memo[7])            # read the answer

Now the chapter’s fix, verbatim — look it up, or compute-and-write:

memo = {1: 1, 2: 2}       # the floor, pre-written

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

print(ways_memo(30))

Same recursion, same floor, same answers — verify a few against §1. The only new behavior: no question is ever computed twice.

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