Tech WondersPlay

Algorithms & EmergenceAlgorithms

Greedy Change

Always giving the biggest coin usually works, until it doesn't

A cashier counts out your change biggest coin first. Does that always give you the fewest coins?

You'll find out

  • Coins that fool the cashier's rule
  • A coin trap from real money
  • The way that can't be fooled

Why it matters

Grabbing the best-looking option is a shortcut many programs take: knowing when it fails is what keeps them right.

About 3 min6 interactive slides · 5 questionsLesson 180 · Zone 20

Play this lesson

Free to play in your browser or on iPhone

More in this zone

  1. 172Network MathematicsThe Friendship ParadoxYour friends probably have more friends than you do
  2. 173Electric VehiclesBraking Into the BatteryElectric cars recharge a little every time they slow down
  3. 174Game TheoryWinning at Rock-Paper-ScissorsHumans are bad at being random, and a machine can exploit it
  4. 175Binary ComputingThe Vote From Outer SpaceA cosmic ray may have added 4,096 votes in a Belgian election
  5. 176Network PerformanceFast Internet, Slow PagesBandwidth isn't speed; round trips add up
  6. 177Game PhysicsWhy Characters Fall Through WallsGames check for collisions in snapshots, and fast things slip between them
  7. 178Classical CryptographyThe Enigma Machine158 quintillion settings, changed every single day
  8. 179CodebreakingBreaking EnigmaIt fell to habits, guesses and a room full of machines