Greedy algorithms

Dijkstra takes the vertex with the smallest estimate, Prim the cheapest edge leaving the tree, Kruskal the cheapest edge anywhere, and all three are provably optimal.

That is worth being suspicious about. Each one commits to a choice at the moment it looks best and never revisits it, which is the behaviour that in ordinary life is called short-sighted, and the three proofs given in the previous lesson were separate, each needing its own argument. This lesson names the pattern, states exactly what must be proved before it can be believed, works the proof properly on one problem, computes a real code with it, and then breaks it on a problem one word away from a problem it solves perfectly.

The pattern and its obligation

A greedy algorithm builds a solution one piece at a time. At each step it picks whatever looks best by some local rule, adds it to the partial solution, and never undoes the choice.

Compared with divide and conquer, this is not a technique so much as a hope, and it is usually a false one. The obligation to discharge has two parts.

The greedy choice property: there exists an optimal solution containing the first choice the rule makes. Note the shape carefully. It is not that the greedy choice is obviously good, and it is not that every optimal solution contains it. It is that at least one optimal solution can be found that agrees with the greedy choice, which is what allows the choice to be made without loss.

Optimal substructure: after making that choice and removing it from the problem, the remainder is a smaller instance of the same problem, and an optimal solution to the remainder combines with the choice to give an optimal solution overall.

Together these give an induction: the first choice is safe, the rest of the problem is the same problem, so every choice is safe. The greedy choice property is where all the work is, and the standard way to prove it is an exchange argument: take any optimal solution, and show that it can be transformed into one containing the greedy choice without becoming worse.

Interval scheduling, done properly

One lecture theatre, and a set of talks each with a fixed start and finish. Overlapping talks cannot both be held. Schedule as many talks as possible.

The obvious rules are wrong. Take the talk that starts earliest, and a single talk running all day is chosen, excluding everything else. Take the shortest talk: given talks over the intervals $(1, 5)$ , $(4, 6)$ and $(5, 9)$ , the shortest is $(4, 6)$ , which conflicts with both of the others, so one talk is scheduled where two were possible. Take the talk conflicting with fewest others, which sounds much more thoughtful, and there are known instances where it also fails.

The rule that works is: take the talk that finishes earliest, then discard everything conflicting with it, and repeat.

The exchange argument. Let $g$ be the earliest-finishing talk overall, and let $S$ be any optimal schedule. If $g \in S$ , done. Otherwise, let $f$ be the earliest-finishing talk in $S$ . Since $g$ finishes no later than $f$ , and the other talks in $S$ all start after $f$ finishes, they all start after $g$ finishes too. So $S$ with $f$ replaced by $g$ is a valid schedule of the same size, and it contains $g$ . An optimal schedule containing the greedy choice therefore exists. Optimal substructure is immediate: once $g$ is fixed, the remaining problem is the same problem on the talks starting after $g$ finishes.

The intuition the proof formalises is that finishing early leaves the most room for whatever comes next, and no other rule maximises the resource that later choices consume.

Sorting by finish time costs $Θ (n \log n)$ and the sweep is $Θ (n)$ .

Example. Talks occupy the intervals $(1, 4)$ , $(3, 5)$ , $(0, 6)$ , $(5, 7)$ , $(3, 8)$ , $(5, 9)$ , $(6, 10)$ , $(8, 11)$ , $(8, 12)$ , $(2, 13)$ and $(12, 14)$ . Which does the rule choose, and what would earliest start give?

Sorted by finish, the first is $(1, 4)$ : take it. The earliest-finishing talk starting at or after 4 is $(5, 7)$ : take it. Then $(8, 11)$ , then $(12, 14)$ . Four talks. Sorting by start time instead takes $(0, 6)$ first, which rules out $(1, 4)$ , $(3, 5)$ and $(5, 7)$ , then $(6, 10)$ , then $(12, 14)$ : three talks, 25 per cent worse on an instance of eleven.

Now you. Apply the rule to $(0, 3)$ , $(2, 5)$ , $(4, 7)$ , $(1, 8)$ , $(6, 9)$ , $(8, 10)$ and $(7, 11)$ .

Answer

Sorted by finish: $(0, 3)$ , $(2, 5)$ , $(4, 7)$ , $(1, 8)$ , $(6, 9)$ , $(8, 10)$ , $(7, 11)$ . Take $(0, 3)$ . The next finishing at or after a start of 3 is $(4, 7)$ , since $(2, 5)$ starts too early. Then $(8, 10)$ , since $(1, 8)$ , $(6, 9)$ all start before 7. Three talks. Note that $(7, 11)$ also starts at or after 7 and was passed over for $(8, 10)$ , which finishes earlier and blocks nothing that $(7, 11)$ would have allowed.

Huffman coding

The best-known greedy algorithm is a compression scheme, from a 1951 term paper by David Huffman, then a graduate student who took the assignment instead of the final exam.

Fixed-width encoding gives every symbol the same number of bits: six distinct symbols need three bits each. That is wasteful when the symbols are not equally common, and the fix is to give common symbols short codes and rare symbols long ones. The danger is ambiguity, and it is avoided by a prefix code: no code word is a prefix of another, so a bit stream decodes with no separators and no lookahead. A prefix code is exactly a binary tree with symbols at the leaves, left meaning 0 and right meaning 1, and the length of a symbol's code is its depth.

The cost to minimise is $\sum_{s} f (s) depth (s)$ over the symbols, with $f$ the frequency. Huffman's rule is greedy and works from the bottom: repeatedly take the two least frequent items remaining, make them the children of a new node with their combined frequency, and put that node back. Stop when one node is left.

The greedy choice property is again an exchange. The two least frequent symbols $x$ and $y$ can be assumed to be siblings at the greatest depth of some optimal tree: take any optimal tree, look at the two deepest siblings $a$ and $b$ , and swap $x$ with $a$ and $y$ with $b$ . Since $x$ and $y$ have the smallest frequencies and $a$ and $b$ were at the greatest depth, each swap moves a smaller frequency to a deeper place and a larger one to a shallower place, so the total cannot increase. Optimal substructure follows because merging $x$ and $y$ into one symbol of combined frequency gives a smaller instance whose optimal tree extends to an optimal tree for the original.

Using a heap for the repeated "two smallest" query costs $O (n \log n)$ , which is the other half of why the previous lesson built one.

Example. Six symbols occur 40, 20, 15, 12, 8 and 5 times in a 100-symbol message. Build the Huffman code and measure the saving against fixed width.

Take the two smallest, 5 and 8, and merge them into 13. Now the smallest two are 12 and 13, merging to 25. Then 15 and 20 merge to 35. Then 25 and 35 merge to 60. Finally 40 and 60 merge to 100. Reading depths off the tree: the symbol of frequency 40 sits at depth 1, those of 20, 15 and 12 at depth 3, and those of 8 and 5 at depth 4. The total is $40 (1) + 20 (3) + 15 (3) + 12 (3) + 8 (4) + 5 (4) = 233$ bits. Fixed width needs three bits for six symbols, so 300 bits. The saving is 67 bits, 22.3 per cent, and the average code length is 2.33 bits per symbol.

Now you. Do the same for frequencies 35, 25, 20, 10, 6 and 4.

Answer

Merge 4 and 6 into 10; merge that 10 with the symbol of frequency 10 into 20; merge that 20 with the symbol of frequency 20 into 40; merge 25 and 35 into 60; merge 40 and 60 into 100. Depths are 2 for the symbols of frequency 35, 25 and 20, 3 for the one of frequency 10, and 4 for those of 6 and 4. The total is $35 (2) + 25 (2) + 20 (2) + 10 (3) + 6 (4) + 4 (4) = 230$ bits against 300, a saving of 23.3 per cent. Note that the most frequent symbol got a two-bit code here and a one-bit code in the previous example: the code depends on the whole frequency distribution, not on any symbol's frequency alone.

Be honest about the limit. Huffman is optimal among codes assigning a whole number of bits to each symbol, and that constraint costs something. Shannon's entropy for the first distribution is 2.278 bits per symbol against Huffman's 2.330, so rounding to whole bits wastes 2.3 per cent. When one symbol has probability 0.9, entropy is 0.47 bits and Huffman must still spend 1, wasting more than half. Arithmetic coding and the modern ANS family avoid the whole-bit constraint and reach the entropy, which is why they, and not Huffman, are inside modern formats such as Zstandard and AV1. Huffman survives inside DEFLATE, JPEG and MP3, and as the last stage of hybrids.

Greed that depends on the numbers

Between the proved cases and the failures sits a third category, where whether greed works depends on the particular data, and change-making is the standard illustration.

To make an amount from coins of given denominations using as few coins as possible, the obvious rule is to take the largest coin that fits and repeat. With British or American coins it is optimal, which is a fact about those denominations rather than about the rule.

Change the denominations to 1, 3 and 4 and it breaks at the sixth coin. Greed makes 6 as $4 + 1 + 1$ , three coins; the optimum is $3 + 3$ , two. A coin system for which the greedy rule is always optimal is called canonical, and deciding whether a given system is canonical is itself work: Pearson gave an algorithm in 2005 that tests it in $O (m^{3})$ for $m$ denominations.

So "greedy works here" is a claim about a specific problem with specific data, never about the strategy, and a greedy algorithm that passes every example is still unjustified without a proof.

Where greed fails

Now the failure, and it is worth how close it sits to a success.

The fractional knapsack problem: a bag of capacity $W$ , items with values and weights, and items may be cut. The greedy rule is to sort by value per unit weight and take the best until the bag is full, cutting the last item to fit. It is optimal, by exchange: any solution containing a unit of a worse item and lacking a unit of a better one can be improved by swapping them.

The 0/1 knapsack problem is identical except that items must be taken whole. That one word destroys the argument, because there is no longer a unit to swap.

Example. A bag holds 50 kg. Item A is worth 60 and weighs 10, item B is worth 100 and weighs 20, item C is worth 120 and weighs 30. What does the ratio rule give, and what is optimal?

The ratios are 6, 5 and 4, so greed takes A then B, filling 30 kg for a value of 160, and C's 30 kg does not fit in the remaining 20. Greedy scores 160. But B and C together weigh exactly 50 and are worth 220. Greed is 27 per cent short, and no reordering of the rule fixes it: taking C first gives $120 + 100 = 220$ by luck here, but ratio-first is the only rule with any general justification and it fails. Fractionally, the same instance allows A, B and two thirds of C, for $60 + 100 + 80 = 240$ .

Now you. A bag holds 10 kg. One item is worth 10 and weighs 6; two others are each worth 8 and weigh 5. What does greed give?

Answer

Ratios are $10 / 6 = 1.67$ and $8 / 5 = 1.60$ , so greed takes the 6 kg item first, leaving 4 kg, into which neither 5 kg item fits. Value 10. The optimum is the two 5 kg items, exactly filling the bag, value 16. Greed loses 37.5 per cent, and it loses on an instance of three items, which is the point: this is not an asymptotic failure that appears at scale, it is wrong immediately.

What the failure is made of

The reason is precise. In interval scheduling, taking the earliest-finishing talk leaves a subproblem whose optimal solution does not depend on which talk was taken, only on the time now free. In 0/1 knapsack, taking an item leaves a subproblem parameterised by the remaining capacity, and whether taking the item was right depends on what best fills that remaining capacity, which is not known yet. The first choice cannot be evaluated without the answer to the rest.

Optimal substructure still holds: an optimal packing of the bag does contain an optimal packing of whatever capacity it leaves for the remaining items. What fails is only the greedy choice property. So the structure that made recursion possible survives, and the only thing lost is the right to commit to one branch.

If the choice cannot be made in advance, the alternative is to try both and keep the better. Done naively that is exponential, since $n$ items give $2^{n}$ subsets. But the subproblems that arise are described entirely by two numbers, how many items remain and how much capacity is left, and there are only $n W$ such pairs however many of the $2^{n}$ paths reach them. Solving each once and reusing the answer is the technique of the next lesson.