A First Taste of Algorithms

Problem Set 2

✦ ✦ ✦

Lab 2 (The Cost of Confidence) is the Computational Lab tier. The audit loop you build there is required equipment for problems 3.5 and 2.5.

Fluency

1.1 On the chapter’s Saturday, execute earliest-finish-first by hand, writing at each step which events are still compatible and which gets chosen. Confirm you reach seven.

1.2 Execute earliest-start-first on the same Saturday by hand and confirm it reaches only four. Which specific events did grabbing the robotics build cost you?

1.3 Draw the three-event shortest-first counterexample (A 1–5, B 4–6, C 5–9) as bars on a timeline. Mark which event shortest-first grabs and which two it kills.

1.4 Run greedy change by hand in the country of {1, 7, 10} for the amounts 14, 20, 21, and 13. For each, also find the true minimum by inspection. Where does greedy lose, and by how much?

1.5 Run greedy change for the same amounts using ordinary US-style coins {1, 5, 10, 25}. Does greedy ever lose here? (The chapter’s deep water explains why not.)

Practice

2.1 Design your own overbooked day — at least eight events, at least three genuine conflicts — and find the maximum attendable set by earliest-finish-first. Then verify by hand that no larger set exists. (Trading days with a classmate and checking each other’s answers is the real exercise.)

2.2 A single video-editing computer can render one project at a time; each queued project has a fixed start and end time it’s scheduled for. From ten projects you invent, find the largest number that can run without overlap. Is this the same problem as the Saturday, in disguise? Say exactly what maps to what.

2.3 A streaming service can show one program in its 8 p.m. slot per night, and each pitched show wants a run of consecutive nights. Recast “air the most shows this month” as the Saturday problem (nights instead of hours) and describe the winning rule in one sentence.

2.4 The country of squares mints coins worth 1, 4, and 9. Compute greedy’s answer and the true best for amounts 12 and 13. Then, using your Lab 2 audit loop, list every amount up to 30 where greedy loses.

2.5 Using your Lab 2 audit loop, design a three-coin system {1, a, b} whose smallest greedy failure is as large as you can make it. Report the system and the failure. (Class competition: largest smallest-failure wins.)

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