Advanced · Module 16 · Lesson 1 of 4
When greedy works
A greedy algorithm makes the locally best choice at each step and never reconsiders it. It is fast and simple, and it is correct only when the problem has a specific structure, which you must prove or disprove.
By the end you can
- Describe a greedy algorithm and contrast it with dynamic programming
- State the greedy-choice property, and test a greedy rule with small counterexamples
- Solve reachability and circuit problems with a single greedy pass
Builds on Knapsack and subsets.
01 · A question first
A cashier gives change with the largest coin first, and with US coins that always uses the fewest coins. With coins of 1, 3 and 4 cents, the same rule makes 6 cents as 4 + 1 + 1, when 3 + 3 uses only two coins. What property of the coins decides whether the greedy rule is safe?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Choose the best now, and never look back
- When greedy is correct
- Disproving greedy
- Reachability in one pass
- Circuits in one pass
- Recognizing greedy problems
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Something wrong with this lesson? Report a problem