A First Taste of Algorithms · Lab 2: The Cost of Confidence

3. Catching every failure

One failure could be a fluke. Let’s audit Sevenia completely. For three-coin systems we can find the true best answer by sheer brute force — trying every possible combination. This is “doing all the work,” the thing algorithms exist to avoid, and we do it here deliberately, as a measuring stick:

def best_change_3(c1, c2, c3, amount):    # c3 must be 1
    best = amount                          # amount pennies always works
    for a in range(amount // c1 + 1):
        for b in range(amount // c2 + 1):
            for c in range(amount // c3 + 1):
                if a*c1 + b*c2 + c*c3 == amount:
                    if a + b + c < best:
                        best = a + b + c
    return best

print(best_change_3(10, 7, 1, 14))

Three loops, one inside another: every count of 10s, against every count of 7s, against every count of 1s. Nothing escapes. Now the audit — every amount from 1 to 30, greedy versus truth:

for amount in range(1, 31):
    g = len(greedy_change([10, 7, 1], amount))
    b = best_change_3(10, 7, 1, amount)
    if g != b:
        print(amount, "greedy:", g, "best:", b)

Run it and read the list of amounts where greedy loses. Look for a pattern in them before the Break-it section asks you about it. This little audit loop — confident method versus exhaustive truth on every small case — is a tool you will use for the rest of your life, and not only on coins.

A note for later: the brute force was affordable here because the kingdom was small. Watch what best_change_3 costs as amounts grow — three nested loops multiply. Chapter 4 will find the best answer without trying everything, and will do it using the failure you just catalogued. The wound stays open until then.

4. Scheduling a day

The chapter’s second arena: from a pile of events that may overlap, attend as many as possible. The winning rule was earliest finish first — always take the event that ends soonest among those you can still attend. To build it we store each event as a two-item list [finish, start], finish first, for one sneaky reason: Python’s .sort() arranges a list of pairs by their first entries, so putting the finish time first makes plain sorting line the events up exactly the way the rule wants. (.sort() itself is a sealed instrument for now — Chapter 6 opens the box and asks what it costs.)

def schedule(events):                  # each event is [finish, start]
    events.sort()                      # earliest finish now comes first
    chosen = []
    free_at = 0
    for e in events:
        finish = e[0]
        start = e[1]
        if start >= free_at:           # does it begin after I'm free?
            chosen.append([start, finish])
            free_at = finish
    return chosen

Try it on the chapter’s example day — times are hours on a 24-hour clock, and each event is [finish, start]:

day = [[10, 9], [11, 9], [12, 11], [13, 10], [14, 12], [16, 13], [15, 14]]
print(schedule(day))

Trace the result against a drawing of the seven events on a timeline (really draw it — the timeline is the proof’s natural habitat, and you’ll want it for the Diamond).

Now the real assignment: write out your own actual week — classes, practices, the things you do — as [finish, start] pairs, and run the scheduler on it. Then deliberately overbook a fantasy Saturday with twelve overlapping events and see what the rule salvages.

Break it

Predict first. Run second. Explain any gap third.

1. In §1, hand greedy_change the coins smallest first: greedy_change([1, 5, 10, 25], 63). Predict the exact output before running. What does the result say about the phrase “take the best-looking option” — best-looking according to whom?

2. From your §3 audit of Sevenia: extend the range to 100 and collect every amount where greedy loses. State a pattern (“greedy fails exactly when the amount looks like ___”) and then test your pattern by predicting the failures between 100 and 130 before running that range.

3. US coins minus the nickel: a country with only [25, 10, 1]. Predict — does greedy stay perfect, or fail somewhere? Commit to an answer and a reason, then audit amounts 1 to 100. (If it fails, find the smallest failure and explain, in the style of Sevenia’s 14, exactly which future the greedy choice destroyed.)

4. In schedule, change start >= free_at to start > free_at and rerun your week. Predict what kind of event pair gets wrongly rejected. One character — what real-world scheduling assumption does it encode?

5. Sabotage the rule itself: store events as [start, finish] so that .sort() lines them up by start time, adjust the two indexing lines to match, and rerun the chapter’s example day. Predict the output first. You have just built, in working code, one of the counterexamples from the chapter — say which one.

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