Exercise 1: Hand-Tracing Greedy Coin Change on {1,3,4} for Amount=8 — Possible Solution
====================================================================

THE TRACE
------------------------------
Denominations sorted descending: 4, 3, 1. Starting remaining = 8.

  Step 1: largest denomination that fits is 4 (4 <= 8).
          Choose 4. Remaining: 8 - 4 = 4.
  Step 2: largest denomination that fits is 4 again (4 <= 4).
          Choose 4. Remaining: 4 - 4 = 0.
  Remaining is now 0 - the algorithm stops.

COINS CHOSEN, IN ORDER: 4, 4
FINAL COIN COUNT: 2

WHY THIS RESULT IS ACTUALLY OPTIMAL, UNLIKE THE CHAPTER'S OWN amount=6 CASE
------------------------------
Independently checking against a true optimum (the same dynamic-
programming cross-check this chapter used for amount=6) confirms
[4, 4] with 2 coins genuinely is the best possible answer for
amount=8 with these denominations - there is no way to make 8 using
fewer than 2 of these coins. This is a useful contrast with this
chapter's own amount=6 example: greedy is not ALWAYS wrong for the
{1,3,4} denomination set - it happened to fail specifically for
amount=6, where taking the 4 first left an expensive-to-finish
remainder of 2. For amount=8, taking two 4s in a row happens to align
exactly with the optimal answer, since 8 divides evenly by the
largest available coin with nothing awkward left over.

WHY THIS WORKS AS AN ANSWER
------------------------------
The trace follows the pseudocode's own while-loop logic explicitly
step by step, states both the coins chosen and the count, and adds an
important, chapter-consistent observation: greedy failing on one
amount for a given denomination set doesn't mean it fails on every
amount for that same set - correctness has to be checked per
case, not assumed to be uniformly good or bad for an entire
denomination set.