A First Taste of Algorithms

Lab 2: The Cost of Confidence

✦ ✦ ✦

Accompanies Chapter 2. The chapter introduced a strategy — at every step, take the option that looks best right now — and claimed it is sometimes perfect and sometimes confidently wrong. In this lab you build both outcomes with your own hands.

1. The cashier’s algorithm

Chapter 2 opened behind a cash register: owe someone 63 cents, and your hands know the algorithm — give a quarter, another quarter, a dime, three pennies. Take the biggest coin that fits; repeat. Here it is in Python:

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

print(greedy_change([25, 10, 5, 1], 63))

One new tool: used.append(coin) adds an item to the end of the list used — the program is keeping a record of its decisions, which is what used = [] (an empty list, a blank ledger) is for. Everything else you own already: the for walks the coin types from largest down; the while spends each coin type as long as it still fits.

Run it on a few amounts. Six coins for 63. Count by hand and check: can you beat six?

You can’t — with these coins, the greedy answer is the best answer, for 63 and for every other amount. (That this is true is believable; why it’s true is genuinely subtle, and the chapter was honest that we are not proving it. We are about to see why such a proof would have to exist: because the same instinct, on different coins, fails.)

2. The kingdom of Sevenia

Chapter 2’s kingdom mints three coins: 1, 7, and 10. You owe 14. Before running anything, do it greedily in your head — and then do it well in your head.

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

Five coins, says your program, with complete confidence. The right answer is two: 7 + 7. The code is not buggy. It did exactly what greedy means — and greedy is wrong here. The grab-the-biggest instinct took the 10 because the 10 looked best at that moment, and taking it destroyed the 7 + 7 future that was quietly available. Greedy never looks back, and never apologizes.

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