Greedy algorithms
A greedy algorithm builds a solution step by step, always making the choice that looks best right now. When it works, it is simple and fast; the challenge is proving that it works.
The greedy idea
Greedy algorithms make a locally optimal choice at each step and never reconsider it. They are usually fast and easy to implement, but they are correct only when the problem has the greedy-choice property, meaning some optimal solution starts with the greedy choice, and optimal substructure, meaning the rest is an optimal solution to the remaining subproblem.
Activity selection
Given activities with start and finish times, choose the largest number that do not overlap. The greedy rule that works is: always pick the activity that finishes earliest, discard those that overlap it, and repeat. Sorting by finish time gives an O(n log n) algorithm. Picking the shortest activity or the earliest start does not always work.
Proving greedy correct
A common proof technique is the exchange argument: take any optimal solution and show it can be transformed, step by step, into the greedy solution without getting worse. For activity selection, swapping the first activity of an optimal schedule for the earliest-finishing activity never causes an overlap, so an optimal solution begins with the greedy choice.
Huffman coding
David Huffman's 1952 algorithm builds an optimal prefix-free binary code for compression. Repeatedly merge the two least frequent symbols, or subtrees, into a new node whose frequency is their sum, until one tree remains; left and right edges spell 0 and 1. Frequent symbols get short codes. Huffman coding appears inside formats such as JPEG, MP3, and DEFLATE (used in ZIP and PNG).
Other greedy successes
Dijkstra's algorithm, Prim's and Kruskal's minimum spanning tree algorithms, and fractional knapsack are greedy. So is the standard way to give change in most national currencies. Interval scheduling, scheduling to minimise maximum lateness by earliest deadline first, and some caching policies also have greedy optimal solutions.
When greedy fails
Greedy fails on the 0/1 knapsack, on coin systems such as {1, 3, 4}, and on the travelling salesperson problem, where always going to the nearest unvisited city can produce tours far longer than optimal. Without a proof, a greedy algorithm is a heuristic: possibly useful, but not guaranteed optimal.
Matroids
Matroids are abstract structures that capture exactly when a simple greedy algorithm, sorting elements by weight and adding each one if it keeps the set independent, is optimal for every weighting. Spanning forests of a graph form a matroid, which is why Kruskal's algorithm works. The theory explains many greedy successes in a single framework.
Worked example
Huffman coding for frequencies A 5, B 9, C 12, D 13, E 16, F 45. Merge A + B = 14; merge C + D = 25; merge 14 + E = 30; merge 25 + 30 = 55; merge F + 55 = 100. F gets a 1-bit code, C, D, and E get 3-bit codes, and A and B get 4-bit codes. Total bits for 100 symbols: 45 x 1 + (12 + 13 + 16) x 3 + (5 + 9) x 4 = 45 + 123 + 56 = 224, versus 300 with a fixed 3-bit code.
Key takeaways
Greedy algorithms make the best local choice and never backtrack; they need the greedy-choice property and optimal substructure. Activity selection picks the earliest finish time. Exchange arguments prove greedy correctness. Huffman coding (1952) merges least frequent symbols for optimal prefix codes used in JPEG, MP3, and ZIP. Dijkstra, Prim, Kruskal, and fractional knapsack are greedy. Greedy fails for 0/1 knapsack, some coin systems, and the travelling salesperson problem. Matroids characterise when greedy is always optimal.
Flashcard
Best local choice at each step
Check your understanding
For scheduling the most non-overlapping meetings in one room, which greedy rule is optimal?