Grabbing the best seat first, with proof

Computing · Algorithms & Data Structures · ages 19-21

Name ______________________ Date ____________

What does a greedy method never do?
- Take the locally best option
- Reconsider an old pick
- Run fast
Which rule books the most activities?
- Take the one that finishes earliest
- Take the one that starts latest
- Take the longest one first
A greedy rule is safe to use without any proof.
Circle one: True False
Coins 1, 3, 4. Largest-first for 6 uses how many coins? Type the count.
Answer: ______________
Why does swapping in the earliest-finishing pick never hurt?
- It ends no later, so room only grows
- It rewrites the past
- It adds extra rooms
What must hold before a greedy rule can be correct?
- Inputs arrive sorted by color
- The first grab sits in some best answer and the rest keeps its shape
- The programmer feels lucky
Since 3 plus 3 beats 4 plus 1 plus 1, largest-first is wrong for that coin set.
Circle one: True False
A student shows greedy winning on three room sets and claims proof. What is the flaw?
- Three sets are too few to read
- Rooms dislike all examples
- Examples never replace the swap argument

Answer key

For grown-ups. Fold this page away before handing over the rest.

Reconsider an old pick · Greedy takes and never looks back.
Take the one that finishes earliest · Earliest finish leaves the most room behind.
False · Only a proof licenses the rule.
3 · It takes 4, 1, 1, which is three coins.
It ends no later, so room only grows · An earlier end keeps every later fit possible.
The first grab sits in some best answer and the rest keeps its shape · A safe first pick plus same-shaped rest licenses greedy.
True · One failure ends the rule for that set.
Examples never replace the swap argument · Proof must cover every set, not sample a few.