Greedy Algorithms

Locally Optimal Choices

1:00

How greedy algorithms make locally optimal choices to solve problems efficiently — and the two properties that determine when greedy is provably correct versus when it fails.

By the end, you can

Define the greedy-choice property and optimal substructure, and explain why both are required for greedy to be correct.
Trace the greedy activity-selection algorithm and count the selected activities.
Explain the exchange argument that proves earliest-finish greedy is safe.
Trace the greedy coin-change algorithm and identify when and why it gives a sub-optimal result.
Distinguish fractional knapsack (greedy optimal) from 0/1 knapsack (greedy fails, needs DP).
Identify canonical versus non-canonical coin systems and predict whether greedy will succeed.
Apply the three-question recognition checklist to decide whether a problem is a greedy candidate.
Name at least four famous greedy algorithms and state why they work.
Compare the typical time and space complexity of greedy algorithms against dynamic programming.

Up next in Algorithms & Graph Algorithms