A First Taste of Algorithms · Problem Set 2

Concept & Counterexample

3.1 Claim: “for scheduling, longest-first can’t be optimal, but it’s a decent rule.” Refute it with the smallest counterexample you can build, and explain in one sentence what longest-first ignores. (You are re-running the chapter’s hunt with a new wrong rule.)

3.2 Claim: “earliest-finish-first works only because the events have different lengths; if all events were exactly one hour long, earliest-start-first would tie it.” Decide, then prove or refute. (If you believe it, find the exchange argument; if not, the counterexample needs care precisely because all bars are equal length.)

3.3 Fewest-conflicts, refuted. The rule “attend the event that conflicts with the fewest others, then repeat” feels wise. Verify it fails on this exact instance — events (start, finish): chain (1,3), (3,5), (5,7), (7,9); blockers (2,4), (2,4), (2,4), (6,8), (6,8), (6,8). Count each event’s conflicts, run fewest-conflicts-first, run earliest-finish-first, and report both scores. Then say in one sentence why “fewest conflicts” was the wrong measure of trouble.

3.4 Claim: “greedy change fails on {1, 7, 10} because 7 doesn’t divide 10.” Test the divisibility theory: find a coin system where no coin divides the next yet greedy still succeeds on every amount (audit it!), or a system with clean divisibility that fails. Then state carefully what divisibility actually guarantees — show that when each coin divides the next ({1, 5, 25}, say), greedy is optimal, and find where your argument uses the divisibility.

3.5 The finite certificate. Run your audit loop on US coins {1, 5, 10, 25} for every amount from 1 to 34. Combined with the Kozen–Zaks theorem (deep water; quote it, don’t prove it), write a five-sentence proof that American greedy change is optimal for every amount, forever. Be precise about what the computation established and what the theorem added — neither alone suffices.

Diamond

4.1 Greedy stays ahead, completed. Starting from the deep-water lemma finish(gᵢ) ≤ finish(sᵢ): (a) Prove the lemma’s base case and inductive step in your own words, drawing the timeline picture that makes the step obvious. (b) Derive the conclusion: greedy’s schedule is at least as large as any valid schedule. (Suppose the rival has m > k events; apply the lemma at position k and contradict greedy’s stopping rule — what exactly does greedy’s having stopped after g_k assert about the events that remain?) (c) The boundary audit: our convention says finishing at 1:00 and starting at 1:00 don’t conflict. Locate every place in (a) and (b) where ≤ versus < matters, and state whether the theorem survives if back-to-back events are counted as conflicts. (d) One sentence: where would this proof break if you tried to run it on the {1, 7, 10} coins instead of on intervals?

Computational Lab

5.1 Lab 2 in full, predictions written before runs. The {1,7,10} failure pattern you conjecture in Break-it 2 should be stated as a precise sentence and tested on the range 100–130 before running it.

Teach It

6.1 Give someone the overbooked-Saturday table and ask them to attend as many things as possible, watching what rule they use. They will almost certainly reach for “earliest start” or “the ones I like most.” Let them commit to an answer, then reveal earliest-finish-first and have them check it beats their rule. Three sentences: what was their first instinct, and what convinced them it was wrong?

6.2 Teach the {1,7,10} disaster with actual objects — coins, beans, Lego of two sizes. Rules: they must make the greedy mistake themselves first (set up the 14 so their hands grab the 10), and you may not say “greedy” or “algorithm” until after the 7 + 7 reveal. Write three sentences: what did their face do, and what explanation finally landed?

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