Advanced · Module 16
Greedy algorithms
When taking the best local choice is provably right, and how to prove it.
A greedy algorithm takes the best-looking choice at every step and never looks back. When that is correct, it is the fastest and simplest solution there is; when it isn't, it is confidently wrong. This module teaches both sides: the conditions under which greedy works, the exchange and stays-ahead arguments that prove it, the scheduling problems where it shines, and Huffman coding, the greedy algorithm inside zip, PNG and JPEG.
- 1When greedy worksPro — members onlyA 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.14 min
- 2Exchange argumentsPro — members onlyTo prove a greedy order is optimal, take any solution that differs from it, swap two elements to make it more like the greedy one, and show the swap never makes it worse. Repeat until the two agree.14 min
- 3Scheduling and intervalsPro — members onlyTo fit the most non-overlapping intervals, always take the one that ends first. A 'greedy stays ahead' proof shows why, and the same rule solves a family of removal, arrow and partition problems.14 min
- 4Huffman codingPro — members onlyHuffman coding gives frequent symbols short bit codes and rare ones long codes, with no code a prefix of another. Repeatedly merging the two rarest subtrees in a heap builds the provably shortest such code.15 min