Greedy Choice and the Exchange Argument · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.
به انگلیسی

Grabbing the best seat first, with proof

Computing · Algorithms & Data Structures · ages 19-21
Name ______________________   Date ____________

  1. What does a greedy method never do?

    • Take the locally best option
    • Reconsider an old pick
    • Run fast

  2. One room holds four activities, each worth the same, and no two picked activities can overlap. Starting exactly when another ends still fits. A runs 9 to 10, B runs 10 to 11, C runs 11 to 12, and D runs 9 to 12. How many activities does the earliest-finish rule book?

    • 3 activities
    • 2 activities
    • 1 activity

  3. A greedy rule is safe to use without any proof.

    Circle one:   True   False

  4. Coins 1, 2, 5. Largest-first for 9 uses how many coins? Type the count.

    Answer: ______________

  5. Take any best schedule and swap its first pick for the earliest-finishing activity. The swap ends no later. What does the full argument show?

    • Later activities still fit, the count stays the same, and the swap repeats on the rest, so greedy matches a best one.
    • The first pick is safe, but the rest needs a different proof
    • Later activities no longer fit, so the count drops

  6. What must hold before a greedy rule can be correct?

    • The first grab is the largest input
    • The first grab sits in some best answer and the rest keeps its shape
    • The problem has many possible answers

  7. With coins of 1, 4, and 6, for 8, largest-first is wrong for that coin set.

    Circle one:   True   False

  8. A student shows greedy winning on three room sets and claims proof. What is the flaw?

    • The student picked the wrong rooms
    • The sets were not sorted by start time
    • Examples do not replace proof
LightMySky · lightmysky.comW1-mt_9Fj28VDAV--s1

Answer key

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

Grabbing the best seat first, with proof W1-mt_9Fj28VDAV--s1

  1. Reconsider an old pick · Greedy takes and never looks back.
  2. 3 activities · Earliest finish picks A, then B starts at 10 when A ends, so B fits, then C starts at 11 when B ends, so C fits. That is three activities. D runs 9 to 12 and blocks the others.
  3. False · Only a proof licenses the rule.
  4. 3 · It takes 5, then 2, then 2, which is three coins.
  5. Later activities still fit, the count stays the same, and the swap repeats on the rest, so greedy matches a best one. · The swap keeps every later fit and the count, and the rest is the same problem, so repeating the swap shows greedy matches a best schedule.
  6. The first grab sits in some best answer and the rest keeps its shape · A safe first pick plus same-shaped rest licenses greedy.
  7. True · Largest-first takes three coins for 8, while 4 plus 4 takes two, so one failure ends the rule for that set.
  8. Examples do not replace proof · Proof must cover every set, not sample a few.
Worksheet · LightMySky