Advanced Algorithms · Lecture Notes
Chapter 2: Greedy Algorithms
When a cashier gives change, they hand over the largest banknote first, then the largest coin that still fits. An attendant filling a meeting room's schedule for the day writes in the meeting that ends earliest first. Neither computes the future; each takes the step that looks best at that moment and never revisits the decision. Algorithms of this kind are called greedy algorithms. The greedy approach is fast and its code is short, but it does not give the best result on every problem. These notes first present the general pattern of the approach and the conditions under which it gives the correct result, namely the greedy-choice property and optimal substructure. The exchange argument, the basic tool for proving correctness, is treated in detail. Five classic problems then follow: coin change, activity selection, job sequencing with deadlines, the fractional knapsack, and Huffman coding. The minimum spanning tree algorithms are then re-examined through the cut property from a greedy point of view. For each problem the notes give Java code, a step-by-step trace, a cost analysis, and counterexamples for the cases where the greedy approach fails.
Learning outcomes
- The approach
- Define the greedy strategy; explain when the greedy-choice property and optimal substructure guarantee a correct result; build a simple correctness proof with the exchange argument.
- Classic problems
- Solve the coin change, activity selection, job sequencing, and fractional knapsack problems greedily; trace their code step by step; give counterexamples for the cases where the greedy approach fails.
- Spanning trees
- Explain why the cut property makes the greedy choice of Kruskal, Prim, and Borůvka correct; compare the three algorithms by selection rule, data structure, and running time.
- Data compression
- Build a Huffman tree, derive prefix-free codes, encode and decode a text, and compute the saving in bits; justify why the Huffman code is optimal.
2.1The greedy approach
Many algorithmic problems consist of a sequence of decisions. Which coin to hand over, which activity to select, which job to put in which hour, which edge to add to the tree? These decisions have to be made in order, and each affects the ones that follow. Trying every sequence of decisions gives the correct result, but the number of sequences grows exponentially with the input. The greedy approach follows just a single branch of this tree: at each step it takes the option that looks best at that moment and moves on.
2.1.1Deciding one step at a time
A greedy algorithm builds the solution step by step and, at each step, selects the option that looks best at that moment according to some criterion. A decision once made is never undone; the algorithm does not backtrack.
A greedy algorithm resembles a treasure hunter. At every fork in the road the hunter turns toward the direction that shows the most gold. The hunter does not look at the whole map, only at the options directly ahead. Choosing, while planning a trip, the road that looks shortest to the destination at every junction is the same behavior. Sometimes that short-looking road leads to a dead end or a long detour. Because the algorithm does not turn back, it cannot correct this wrong step.
Both faces of the approach are plain in this example. On one side are speed and simplicity. At each step only one option is selected, and the options not selected are never examined again. Most greedy algorithms sort the candidates once and then decide in a single pass. On the other side is the lack of a guarantee. The choice that looks best at the moment does not always lead to the best solution of the whole. On many problems a greedy algorithm produces a good approximate solution, but that it finds the optimal solution can be shown only by a proof.
In these notes "best solution", "optimal solution", and "optimum" are used in the same sense. A problem can have more than one best solution. For example, two different sets of activities with the same number of activities are both best if both reach the maximum number. It is enough for a greedy algorithm to find any one of them.
2.1.2The general template
Most greedy algorithms follow the same skeleton. First one determines which choices do not violate the constraints, that is, what the feasible solutions are. Then a greedy criterion is chosen: cheapest, earliest finishing, most profitable, most frequent, and so on. The candidates are sorted by this criterion. Then each candidate is examined in turn. If adding the candidate to the current solution does not violate the constraints, it is added; if it does, it is skipped. When the solution is complete, the algorithm stops. The template code in the slides shows this skeleton in Java:
Solution greedy(Candidate[] cands) {
Solution s = new Solution(); // empty solution
sort(cands); // by the criterion
for (Candidate c : cands) {
if (s.isFeasible(c)) // constraints hold
s.add(c); // never undone
}
return s;
}Solution and Candidate in the code are abstract names; they carry a different meaning in each problem. In coin change, a candidate is a coin and the solution is the list of coins handed over. In activity selection, a candidate is an activity and the solution is the set of selected activities. The call sort orders the candidates by the greedy criterion. isFeasible checks whether the new candidate violates the constraints. The loop considers each candidate once, and a candidate that joins the solution with add is never removed again. The comments in the code stress these two properties: the check protects the constraints, and the addition is not undone.
Figure 2.1 shows this single pass. Six candidates arrive in sorted order. a1 and a2 do not violate the constraints and are added. a3 conflicts with those selected so far and is skipped. a4 is added, a5 is skipped, and a6 is added. The result is the set {a1, a2, a4, a6}. The skipping of a3 is permanent: after a4 and a6 are added, no one goes back to a3 to ask "is it feasible now?".
The cost of the template has two parts. Sorting the n candidates takes O(n log n). The scan that follows performs one isFeasible check for each candidate. If the check finishes in constant time, the scan takes O(n) and the sort determines the total cost: O(n log n). In some problems the candidates are not sorted up front; at each step the best candidate is taken from a priority queue. This is the case in Huffman coding and in Prim's algorithm. Since each queue operation takes O(log n), the total cost is again mostly of order O(n log n). If the check is expensive, for example when a free time slot has to be searched for, as in job sequencing, the dominant part of the cost shifts to the check.
Believing that applying the template correctly makes the algorithm correct. The template is only a skeleton; the criterion determines the result. The same skeleton gives the best result in activity selection with the "earliest finish" criterion, and a very bad result with the "earliest start" criterion. In every new problem, the correctness of the chosen criterion must be proved separately.
2.1.3The greedy-choice property and optimal substructure
For a greedy algorithm to give the best result, the problem must have two properties together. The first concerns the first step: the first choice the algorithm makes must not close off the path to the best solution. The second concerns the rest of the work. After the first choice, the remaining problem must be a smaller problem of the same kind. Its best solution, combined with the first choice, must give the best solution of the whole.
A problem has the greedy-choice property if there is at least one best solution that contains the locally best choice according to the greedy criterion. In other words, the first greedy choice never sends the algorithm down the "wrong path".
A problem has optimal substructure if, after a choice has been made, the best solution of the remaining subproblem together with that choice gives the best solution of the whole problem.
What the two properties give together can be seen by induction. The greedy-choice property says that there is a best solution containing the first choice. After this choice has been made, the remaining problem is of the same kind. Optimal substructure says that the best solution of the remaining problem combined with the first choice is the best solution of the whole. Because the greedy-choice property also holds in the remaining problem, the algorithm's second choice does not send it down the wrong path either. This continues: at every step, the partial solution at hand remains part of some best solution. When the algorithm finishes, the partial solution is complete and optimal.
The words "at least one" in the definition are important. The greedy-choice property does not say that every best solution contains the greedy choice. Activity selection is a good example: in the ten-activity example in the slides the maximum size is 6, and there are two different sets of this size. Only one of them contains the earliest-finishing activity. For the property this is enough.
Optimal substructure is not unique to greedy algorithms. Dynamic programming also rests on this property. What separates the two approaches is the greedy-choice property. Dynamic programming does not know which choice is best at the next step; it tries all the options and stores the results of the subproblems in a table. A greedy algorithm knows in advance which choice is safe and makes only that one. This is why, on the problems where it applies, a greedy algorithm is much faster than dynamic programming.
If the two properties do not hold together, a greedy algorithm is only a heuristic. A heuristic is fast and gives a reasonable result on most inputs. But it does not by itself say how much worse than the best its result can be. Coin change with the coins {4, 3, 1} is the simplest example: for the amount 6 the greedy algorithm gives 3 coins, although 2 suffice.
2.1.4The exchange argument
The most common way to prove the greedy-choice property is the exchange argument. The proof starts from an arbitrary best solution. Call it O. If O already contains the greedy choice, there is nothing more to say. If it does not, a suitable element of O is removed and the greedy choice is put in its place. The real work of the proof is to show two things:
- After the change the solution is still feasible; no constraint is violated.
- After the change the solution is no worse; the objective value either stays the same or improves.
Once these two points are shown, a best solution containing the greedy choice has been found. Together with optimal substructure, induction is applied and the result extends to all the steps.
The strength of the argument is that it does not require knowing what the best solution looks like. All that is known about O is that it is feasible and optimal. The proof makes O resemble the greedy solution step by step and shows that quality does not drop at any step. Most greedy proofs fit this pattern. In activity selection the first activity is exchanged. In the fractional knapsack a portion of one item trades places with a portion of another. In the cut property one edge is exchanged for another, and in Huffman coding two leaves are swapped with each other.
A student can read at most k of n exam papers; each paper has a score, and the total score should be as large as possible. The greedy criterion is obvious: the k papers with the highest scores are selected. The exchange argument is set up as follows. Let a be the paper with the highest score, and let O be a best selection that does not contain it. Any paper b is removed from O and a is put in its place. Since the number of papers has not changed, the selection is feasible. Since score(a) ≥ score(b), the total does not decrease. So there is a best selection that contains a. After a is selected, the remaining problem is to select k − 1 papers from the other n − 1, and it is of the same kind.
The example looks easy because the constraint concerns only the number of selected items. As constraints grow more complicated, it gets harder to show that the exchange does not violate feasibility. In activity selection this step requires comparing finish times, and in Huffman coding it requires comparing depths in the tree.
In the exchange argument, showing only the "no worse" part and skipping feasibility. If the changed solution is not feasible, that is, if it violates one of the constraints, the proof shows nothing. In the 0/1 knapsack, putting a high-ratio item in place of a low-ratio item can raise the profit, but if the new item is heavier, the capacity is exceeded. This is exactly why the ratio criterion fails in this problem.
2.1.5Strengths and weaknesses
The strengths of the greedy approach can be listed briefly:
- Clear, short code. The whole algorithm is often a sort and a loop. None of the Java code given in these notes exceeds twenty lines.
- Speed. Sorting and a single pass take O(n log n) in total. Solving the same problem with dynamic programming usually requires filling a table and a higher cost.
- Little memory. Only the current partial solution is kept. No table storing the results of subproblems is needed.
- The best result on the right problem. On problems such as the minimum spanning tree, Huffman coding, and activity selection, a greedy algorithm is provably optimal.
- A good start on hard problems. On problems where finding the best solution is very expensive, a greedy algorithm gives a fast approximate solution or a starting point for better methods.
The weaknesses are at least as important:
- There is no guarantee. Coin change with the coins {1, 3, 4} and the 0/1 knapsack are known examples where the greedy result is worse than the best.
- Each problem needs its own proof. That a greedy algorithm is correct on one problem does not show that it will be correct on another that looks similar.
- The choice of criterion is decisive. Of the many criteria that come to mind for the same problem, usually only one is correct. A wrong criterion makes an algorithm wrong even when its code is written perfectly.
- Mistakes cannot be corrected. Because a decision is never undone once made, the effect of an early bad choice is carried to the end.
2.1.6The greedy approach and divide and conquer
Divide and conquer also reduces a problem to smaller problems. This resemblance can lead to confusing the two approaches. The difference lies in how the reduction is done. Divide and conquer splits the problem by a predetermined rule, for example the array in the middle. There is no choice in this split. It then solves all the pieces and combines the results. The greedy approach, by contrast, makes a choice, and after this choice a single subproblem remains. That subproblem is solved; there is no other piece. Table 2.1 collects the differences under five headings.
| Greedy | Divide and conquer | |
|---|---|---|
| Decision | a single, locally best choice at each step; never undone | split by a fixed rule; no choice is made |
| Subproblems | one subproblem remains after the choice | several mutually independent subproblems |
| Correctness | the greedy-choice property and optimal substructure must be proved | depends on the correctness of the combine step |
| Cost | usually O(n log n): sorting and a single pass | found from the recurrence and the master theorem |
| Example | activity selection, Kruskal, Huffman | merge sort, Karatsuba |
The cost row reflects this difference as well. The running time of merge sort is found from the recurrence T(n) = 2T(n/2) + O(n) with the master theorem, and it is O(n log n). For the running time of a greedy algorithm there is usually no need to set up a recurrence; the sorting and scanning costs are simply added. The correctness row shows the most important difference between the two approaches. In divide and conquer, if the subproblems are solved correctly and the combine step is correct, the result is correct automatically. In the greedy approach, the correctness of the result depends on the safety of the choice made, and this must be proved separately.
2.2The coin change problem
The most familiar example of the greedy approach is giving change. If a cashier wants to pay 68 kuruş with as few coins as possible, they hand over the 50 first, then the 10, then the 5, and finally three 1s. At each step they select the largest coin that fits the remaining amount. This method works perfectly in everyday currency systems. But if the denominations are chosen differently, the same method can miss the best result. This section examines both the cases where the method works and the cases where it fails.
2.2.1The problem and the greedy criterion
The coin change problem: given k coin denominations with positive integer values p1 > p2 > … > pk = 1 and an amount T. Any number of coins of each denomination may be used. The goal is to find the fewest coins whose sum is exactly T.
That the smallest coin is 1 guarantees that every amount can be paid. Without this condition, some amounts cannot be paid at all; for example, 7 cannot be paid with only 3 and 5 coins. The greedy criterion is this: select the largest coin that is not greater than the remaining amount; repeat this step until the amount is zero. The Java code in the slides applies this rule with two nested loops:
// coins[] sorted from largest to smallest
static int makeChange(int[] coins, int amount) {
int count = 0;
for (int c : coins) {
while (amount >= c) {
amount -= c;
count++;
}
}
return count;
}The code assumes that the coin array arrives sorted from largest to smallest. The outer loop considers each denomination once, in this order. The inner while loop uses that coin as long as it fits the remaining amount: it subtracts it from the amount and increments the counter. When the coin no longer fits, the inner loop ends and the next, smaller denomination is taken up. Since the smallest coin is 1, the amount is always zero after the last denomination.
The cost has two parts. The outer loop runs k times and tests at least one while condition per iteration; this amounts to O(k). Each time the body of the inner loop runs, one coin is selected; the body runs count times in total. The total time is O(k + count). If the coin array does not arrive sorted, an O(k log k) sort is added. The inner loop can also be written with division and remainder: count += amount / c; amount %= c;. This version takes O(k) regardless of the number of coins and is faster on large amounts. The result is the same.
2.2.2Step by step in a canonical system
In the first example in the slides the coins are {50, 25, 10, 5, 1} and the amount is 68. Table 2.2 gives each step.
| Step | Largest coin that fits | Remaining amount | Coins used |
|---|---|---|---|
| start | — | 68 | 0 |
| 1 | 50 | 68 − 50 = 18 | 1 |
| 2 | 10 (25 does not fit) | 18 − 10 = 8 | 2 |
| 3 | 5 | 8 − 5 = 3 | 3 |
| 4 | 1 | 3 − 1 = 2 | 4 |
| 5 | 1 | 2 − 1 = 1 | 5 |
| 6 | 1 | 1 − 1 = 0 | 6 |
The result is 68 = 50 + 10 + 5 + 1 + 1 + 1, that is, 6 coins. This is indeed the fewest coins for 68. That fewer is impossible can be seen as follows. All the coins other than 1 are multiples of 5, and the remainder of 68 divided by 5 is 3. Every solution therefore contains at least three 1 coins. If there were a solution with at most 5 coins, at most two coins other than the 1s would have to pay 65. But 65 cannot be paid with two coins: 50 + 10 = 60, 50 + 25 = 75, and 25 + 25 = 50; no sum of two coins equals 65. It cannot be paid with one coin or with none, either.
Coin systems in which the greedy result is optimal for every amount are called canonical coin systems. {50, 25, 10, 5, 1} and {25, 10, 5, 1} are canonical systems. The {100, 50, 25, 10, 5, 1} kuruş corresponding to the coins of the Turkish lira is also canonical. So is the sequence {200, 100, 50, 20, 10, 5, 2, 1} cents of the euro system. The verification script for these notes compared every amount from 1 to 499 in each of these systems with dynamic programming and found no difference. That everyday currency systems are canonical is no accident; the systems are designed with this property in mind.
2.2.3Code trace: {4, 3, 1} and 10
Now let the denominations be {4, 3, 1} and call makeChange with the amount 10. The coins are given from largest to smallest. This system is not canonical; whether the greedy result will be optimal is not known in advance. Table 2.3 shows the values of the variables at each step of the code.
| Step | c | Condition amount >= c | Action | amount | count |
|---|---|---|---|---|---|
| 1 | 4 | 10 ≥ 4 true | subtract 4 | 6 | 1 |
| 2 | 4 | 6 ≥ 4 true | subtract 4 | 2 | 2 |
| 3 | 4 | 2 ≥ 4 false | while ends | 2 | 2 |
| 4 | 3 | 2 ≥ 3 false | the 3 coin is never used | 2 | 2 |
| 5 | 1 | 2 ≥ 1 true | subtract 1 | 1 | 3 |
| 6 | 1 | 1 ≥ 1 true | subtract 1 | 0 | 4 |
| 7 | 1 | 0 ≥ 1 false | while ends, return 4 | 0 | 4 |
makeChange({4, 3, 1}, 10): the initial state (top) and the final state (bottom). Greedy uses 4 coins with 4 + 4 + 1 + 1; the optimal solution is 3 coins with 4 + 3 + 3.The code returns 4: 10 = 4 + 4 + 1 + 1. Yet 10 = 4 + 3 + 3 uses only 3 coins. The mistake is made at the second step. After the first 4 is selected, for the remaining amount 6 the greedy rule again selects 4, because 4 still fits. But 6 could have been paid with two 3 coins. The moment the second 4 is selected, the 3 coin becomes useless for the remaining 2, and 2 is paid with two 1 coins. The fourth row of the trace shows this outcome: the 3 coin is never used.
2.2.4Why does the greedy choice fail?
In the same system the amount 6 is an even shorter counterexample. The greedy algorithm first selects 4 and pays the remaining 2 with two 1 coins: 6 = 4 + 1 + 1, 3 coins. The optimal solution is 6 = 3 + 3, 2 coins. Figure 2.4 shows these two results.
Here the greedy-choice property is broken. The first greedy choice is 4, but 3 + 3, the only optimal solution for 6, does not contain 4. Every solution that contains 4 uses at least 3 coins. The exchange argument does not work in this system either: if one of the 3 coins in the optimal solution is exchanged for a 4, the total becomes 7 and the solution loses feasibility.
Trying a single amount is not enough to tell whether a coin system is canonical. In the system {4, 3, 1}, among the amounts from 1 to 10, greedy errs only at 6 and 10; for the amounts 1–5, 7, 8, and 9 the greedy result is optimal. Up to 20, the amounts with errors are 6, 10, 14, and 18. The second counterexample system in the slides is {10, 7, 1}. In this system the first erroneous amount is 14: greedy uses 5 coins with 10 + 1 + 1 + 1 + 1, and the optimal solution is 2 coins with 7 + 7. For 15, greedy gives 6 coins (10 plus five 1s), and the optimal solution is 3 coins with 7 + 7 + 1.
Which coin system with the smallest largest coin makes greedy change fail? If the largest coin is 2, the system is {2, 1}, and greedy is optimal for every amount: as many 2s as possible, then at most one 1. If the largest coin is 3, the possible systems are {3, 1} and {3, 2, 1}. In both, any amount is paid in the form 3q + r (r ≤ 2), and nothing does better. The systems with largest coin 4 are {4, 1}, {4, 2, 1}, {4, 3, 1}, and {4, 3, 2, 1}. Of these, only {4, 3, 1} is not canonical, and its first counterexample is 6. The verification script found this result by scanning all the small systems. So {1, 3, 4} with the amount 6 is the smallest example on which greedy fails.
Whether a system is canonical is generally not easy to see. That neighboring coins are multiples of each other is a sufficient condition: in a system like {100, 50, 10, 5, 1}, each larger coin can stand in for the smaller ones. This condition is not necessary, however; in the system {25, 10, 5, 1}, 25 is not a multiple of 10, but the system is still canonical. As Kozen and Zaks showed, the smallest counterexample of a non-canonical system is smaller than the sum of the two largest coins. To check a system it therefore suffices to compare the amounts up to this bound with dynamic programming. For {4, 3, 1} the bound is 7, and 6 lies in this range. For {10, 7, 1} the bound is 17, and 14 lies in this range.
Trying greedy change on a few amounts and assuming it is correct. In the system {4, 3, 1} all the amounts from 1 to 5 give the correct result; the first error appears at 6. A few successful trials are not a proof. The correctness of a greedy algorithm is either shown by a proof or, as in coin change, checked by comparing a whole finite range against the optimal method.
2.2.5The optimal result: dynamic programming
If the coin system is not canonical, dynamic programming gives the best result. The idea is to compute the minimum number of coins for every amount, from smallest to largest. Let minCoins[t] be the minimum number of coins needed to pay the amount t. We have minCoins[0] = 0. For t > 0, if the last coin used is p, the amount t − p remains, and it too must be paid in the best way. All the coins are tried and the best is chosen:
minCoins[t] = 1 + min { minCoins[t − p] : p ≤ t }
This recurrence is an instance of optimal substructure: if the last coin is removed from the best solution for t, the remaining coins form the best solution for t − p. The difference from the greedy algorithm is that it is not known which coin will be last, and all the options are tried. Table 2.4 gives the table from 0 to 10 for the system {4, 3, 1} next to the greedy result.
| t | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| greedy | 0 | 1 | 2 | 1 | 1 | 2 | 3 | 2 | 2 | 3 | 4 |
| minCoins[t] | 0 | 1 | 2 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 |
Computing two cells of the table in detail shows how the recurrence works. For t = 6 there are three options: if the last coin is 1, 1 + minCoins[5] = 3; if it is 3, 1 + minCoins[3] = 2; if it is 4, 1 + minCoins[2] = 3. The smallest is 2, and it is obtained with the 3 coin. For t = 10 the options are 1 + minCoins[9] = 4, 1 + minCoins[7] = 3, and 1 + minCoins[6] = 3; the smallest is 3. The greedy algorithm follows only the option of the 4 coin and finds 4 coins for 10.
The price of dynamic programming is time. The table has T + 1 cells, and each cell tries the k coin denominations; O(k · T) time and O(T) memory are needed in total. The greedy algorithm finishes in O(k + count) time and uses no extra memory. The interactive slide in the presentation runs the two methods side by side: the desired set of coins and an amount are entered, and the greedy result is compared with the optimal result of dynamic programming. One of the ready-made buttons loads the example {1, 7, 10} with 14, and the other loads the canonical Turkish kuruş system with the amount 68.
Calling makeChange with an unsorted coin array. The code assumes the array is sorted from largest to smallest and does not check it. If it is called with the array {1, 5, 10}, the first denomination is 1, so the whole amount is paid with 1 coins; for 68 it returns 68 coins. Either the caller must sort the array, or a sort must be added at the start of the method.
2.3Activity selection
Many activities want to use a conference hall. Each activity has a known start time and finish time. Only one activity can take place in the hall at a time. The management wants to accept as many mutually non-overlapping activities as possible. It is not the duration or importance of the activities that matters, only their number. This problem is a classic example in which a greedy algorithm gives the best result and this can be shown by a short proof.
2.3.1The problem definition
Activity selection: n activities are given; activity i occupies the half-open interval [si, fi) (si < fi). Two activities [si, fi) and [sj, fj) are compatible if sj ≥ fi or si ≥ fj. The goal is to find a set consisting of the largest possible number of mutually compatible activities.
That the intervals are half-open means that another activity can start at the moment one ends. For example, [3, 4) and [4, 6) do not overlap. The finish instant is not part of the activity. The example in the slides has ten activities (Table 2.5).
| Activity | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| start s | 1 | 2 | 4 | 6 | 5 | 8 | 0 | 3 | 7 | 10 |
| finish f | 3 | 5 | 6 | 8 | 7 | 9 | 2 | 4 | 9 | 12 |
Trying all the subsets by brute force means 2n sets: 1024 sets for ten activities, and more than a trillion for forty. The greedy algorithm sorts the activities once and selects in a single pass.
2.3.2Which criterion?
To build a greedy algorithm one must first answer the question "which activity should be selected at each step?". Four criteria come to mind:
- Earliest start. Let the hall fill up as early as possible.
- Shortest duration. Short activities keep the hall busy for less time.
- Fewest conflicts. Select the one that blocks the fewest other activities.
- Earliest finish. Let the hall become free as early as possible.
Each looks reasonable, but only the last gives the best result on every input. A single counterexample suffices to show that a criterion is wrong. Figure 2.5 shows the counterexamples from the slides for the first two criteria.
In the upper example, the activity [0, 10) starts earliest. The greedy algorithm selects it and discards the activities [1, 3), [4, 6), and [7, 9) that overlap with it; the result is 1 activity. Yet these three short activities do not overlap one another and can be selected together. In the lower example, [4, 7) is the shortest activity (3 units). Greedy selects it, but this activity overlaps both [0, 5) and [6, 11). The result is again 1 activity; the best solution selects the two long activities together.
The fewest-conflicts criterion needs a subtler counterexample, because on small examples it often gives the right result. Table 2.6 gives a counterexample with eleven activities. The best solution consists of A, B, C, and D and contains 4 activities. But the activity with the smallest number of conflicts is M: it overlaps only B and C. Greedy selects M first and so loses both B and C. At most two more of the remaining activities can be selected; the result is 3 activities. The verification script tried every way of breaking ties and showed that this criterion cannot exceed 3 on this input.
| Activity | Interval | Number of conflicting activities |
|---|---|---|
| A | [0, 3) | 3 |
| B | [4, 7) | 4 |
| C | [8, 11) | 4 |
| D | [12, 15) | 3 |
| X1, X2, X3 | [2, 5) (three copies) | 4 each |
| Y1, Y2, Y3 | [10, 13) (three copies) | 4 each |
| M | [6, 9) | 2 |
The thinking behind the earliest-finish criterion is this: the activity that frees the hall earliest leaves the most time for the remaining activities. The longer the remaining time, the more activities can fit there. The criterion looks not at the duration or the start of the activity, only at its finish.
2.3.3Code and trace
The select method in the slides sorts the activities by finish time, selects the first, and then compares each activity with the finish of the last one selected:
static void select(Activity[] a) {
Arrays.sort(a, (x, y) -> x.finish - y.finish);
int i = 0; // last selected
System.out.print(a[i].id + " ");
for (int j = 1; j < a.length; j++) {
if (a[j].start >= a[i].finish) {
System.out.print(a[j].id + " ");
i = j;
}
}
}In the code, the Activity class has the fields id, start, and finish. The expression (x, y) -> x.finish - y.finish in the Arrays.sort call is a comparator: if the finish of x is smaller, a negative value is returned and x moves ahead. The sort Java uses for object arrays is stable; two activities with equal finish times keep their original order in the array. The variable i holds the position of the last selected activity in the array. The first element of the sorted array is the earliest-finishing activity and is selected unconditionally. The loop starts at j = 1. The condition a[j].start >= a[i].finish tests whether activity j starts after the last selected one, that is, whether it is compatible with it. If the condition is true, the activity is printed and i is updated.
There is an important observation here: the new activity is compared only with the last selected one, not with all the selected ones. This suffices because the activities are sorted by finish. The last selected is the latest-finishing among the selected. If the new activity starts after it, it also starts after all the selected activities that finished earlier.
After sorting, the array is as follows: #7 [0, 2), #1 [1, 3), #8 [3, 4), #2 [2, 5), #3 [4, 6), #5 [5, 7), #4 [6, 8), #6 [8, 9), #9 [7, 9), #10 [10, 12). #6 and #9 have the same finish (9); the stable sort keeps #6 in front. Table 2.7 gives each step of the loop.
j | Activity | a[j].start | a[i].finish | Decision | New i |
|---|---|---|---|---|---|
| 0 | #7 [0, 2) | 0 | — | first activity, selected | 0 |
| 1 | #1 [1, 3) | 1 | 2 | 1 < 2, overlaps, skipped | 0 |
| 2 | #8 [3, 4) | 3 | 2 | 3 ≥ 2, selected | 2 |
| 3 | #2 [2, 5) | 2 | 4 | 2 < 4, skipped | 2 |
| 4 | #3 [4, 6) | 4 | 4 | 4 ≥ 4, selected | 4 |
| 5 | #5 [5, 7) | 5 | 6 | 5 < 6, skipped | 4 |
| 6 | #4 [6, 8) | 6 | 6 | 6 ≥ 6, selected | 6 |
| 7 | #6 [8, 9) | 8 | 8 | 8 ≥ 8, selected | 7 |
| 8 | #9 [7, 9) | 7 | 9 | 7 < 9, skipped | 7 |
| 9 | #10 [10, 12) | 10 | 9 | 10 ≥ 9, selected | 9 |
The program prints 7 8 3 4 6 10; 6 activities have been selected. This number is indeed the largest: the verification script tried all 1024 subsets and found no compatible set of 7 activities. There are two sets of 6 activities: the one greedy found, {7, 8, 3, 4, 6, 10}, and {1, 8, 3, 4, 6, 10}. The second starts with #1 instead of #7. This shows concretely that the greedy-choice property speaks of "at least one" best solution: there is a best solution that does not contain #7, the earliest finisher, but there is also one that does.
Three steps in the trace show the importance of half-open intervals. #3 starts exactly at 4 and #8 ends exactly at 4; #4 starts exactly at 6 and #3 ends exactly at 6; #6 starts exactly at 8 and #4 ends exactly at 8. If the condition were written > instead of >=, the activities starting at the moment the last selected one ends would be skipped. After #8, #5 [5, 7) would be selected instead of #3; then #6 [8, 9) and #10 [10, 12) would follow, and the result would stay at 5 activities.
The cost is clear. Sorting takes O(n log n) and the single pass O(n); the total is O(n log n). If the activities arrive sorted by finish, the sort is unnecessary and the algorithm finishes in O(n) time. As extra memory only the variable i is kept.
Let eleven activities be given as (s, f) pairs: (1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16). The activities are already sorted by finish. The first activity (1, 4) is selected and the last finish becomes 4. (3, 5) and (0, 6) start before 4 and are skipped. (5, 7) is selected and the last finish becomes 7. (3, 9), (5, 9), and (6, 10) start before 7 and are skipped. (8, 11) is selected and the last finish becomes 11. (8, 12) and (2, 14) are skipped. (12, 16) is selected. The result is 4 activities: (1, 4), (5, 7), (8, 11), (12, 16).
Comparing the new activity not with the last selected one but with the previous activity in the array; that is, writing a[j].start >= a[j - 1].finish. The previous activity may have been skipped. #2 [2, 5) at j = 3 in the trace shows this: the finish of the previous activity #8 is 4, and since 2 < 4 the result comes out right. But #3 [4, 6) at j = 4 would be compared with 5, the finish of the skipped #2; since 4 < 5 it would be skipped by mistake. The comparison must always be made with the last selected activity.
2.3.4Why is earliest finish correct?
Let a1 be the earliest-finishing activity. The activity selection problem has a best solution that contains a1. Hence the algorithm "select the earliest finisher, discard the activities that overlap it, repeat with the rest" selects the largest number of activities.
The proof uses the exchange argument. Let O = {b1, b2, …, bk} be a best solution sorted by finish. If b1 = a1, there is nothing more to say. Otherwise form the set O' = (O − {b1}) ∪ {a1}. Since a1 is the earliest-finishing activity, f(a1) ≤ f(b1). Since O is compatible, f(b1) ≤ s(b2). Combining the two inequalities gives f(a1) ≤ s(b2). Since the activities b2, …, bk all start after b2 does, a1 overlaps none of them. So O' is feasible. The number of elements has not changed either: |O'| = |O| = k. Hence O' is also a best solution, and it contains a1.
For optimal substructure, a1 and the activities overlapping it are discarded. The remaining activities are those that start after f(a1), and they form a problem of the same kind. When a1 is removed from O', the remaining set is a solution of this smaller problem. If the smaller problem had a larger solution, adding a1 to it would give a solution larger than O'; this contradicts the optimality of O'. By induction, the algorithm's choice at every step remains part of a best solution. □
In the proof the earliest-finishing activity has a special role: it does not finish later than the b1 it replaces. So when it takes b1's place, it does not obstruct the later activities. The same argument cannot be set up for the earliest-starting activity: the earliest-starting activity may finish very late and may overlap b2. [0, 10) in Figure 2.5 is in exactly this situation.
The same problem can also be solved in the opposite direction. The activities are sorted by start from largest to smallest, and at each step the latest-starting activity is selected. This is the same as the earliest-finish criterion with the time axis reversed, and it gives the best result by the same proof. In weighted activity selection, a generalization of the problem, each activity has a value and the total value must be as large as possible. In this version no simple greedy criterion is correct; the problem is solved by dynamic programming.
2.4Job sequencing with deadlines
A workshop has a single machine and several orders waiting in the queue. Each order takes one day on the machine. Each order has a delivery deadline and a profit; if the order is finished by its deadline the profit is earned, and if not, the order is lost. Which orders should the workshop put on which days to make the total profit as large as possible? This problem resembles activity selection, but here all the jobs take the same time, and what matters is not the count but the profit.
2.4.1The problem definition
Job sequencing with deadlines: n jobs are given. Each job takes 1 unit; job i has a deadline di and a profit ki. Time is divided into unit slots numbered 1, 2, 3, …, and at most one job is done in each slot. If a job is finished by the end of slot di, the profit ki is earned. The goal is to find the set of jobs and the slot assignment with the largest total profit.
The deadline di of a job means the job can be placed in any of the slots from 1 to di. A job with deadline 1 can be placed only in the first slot. A job with deadline 3 can be placed in the first, second, or third slot. The example in the slides has six jobs (Table 2.8).
| Job | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| deadline | 4 | 1 | 1 | 1 | 3 | 2 |
| profit | 20 | 10 | 40 | 30 | 50 | 30 |
At first glance, three jobs (2, 3, and 4) have deadline 1, and only one of them can be done. Which one to do, and where to put the other jobs, must be considered together.
2.4.2The greedy criterion and the latest free slot
The greedy algorithm makes two decisions. The first is the order in which the jobs are considered: the jobs are examined in decreasing order of profit, that is, the most profitable job first. The second is which slot each job goes in: the job is placed in the latest free slot at or before its deadline. If no free slot remains up to its deadline, the job is skipped and never considered again.
The reasoning for the second decision is this. Putting a job in an earlier slot than necessary can block the place of a job whose deadline is closer. For example, if a job with deadline 3 is put in the first slot, the only place that a later job with deadline 1 could go is already taken. Had the same job been put in the third slot, the first slot would have stayed free. The latest free slot leaves the early slots to jobs with closer deadlines and preserves flexibility.
2.4.3Code and trace
The sequenceJobs method in the slides applies these two rules and returns the total profit:
static int sequenceJobs(Job[] jobs, int n) {
Arrays.sort(jobs, (a, b) -> b.profit - a.profit);
int[] slot = new int[n];
Arrays.fill(slot, -1);
int total = 0;
for (int i = 0; i < n; i++) {
int j = Math.min(n, jobs[i].deadline) - 1;
for (; j >= 0; j--) {
if (slot[j] == -1) {
slot[j] = jobs[i].id;
total += jobs[i].profit;
break;
}
}
}
return total;
}The Job class has the fields id, deadline, and profit. The comparator b.profit - a.profit in the Arrays.sort call moves the job with the larger profit forward. Thanks to the stable sort, jobs with equal profit keep their original order. The array slot holds n slots: slot[j] is the number of the job placed in slot j + 1, or −1 if it is empty. Because arrays start at 0 in Java, the first slot is in slot[0]. n jobs can use at most n slots; deadlines larger than n are therefore lowered to n. The expression Math.min(n, jobs[i].deadline) - 1 does this and gives the index of the latest slot the job can be put in. The inner loop searches backward from this slot for the first free slot. If a free slot is found, the job is placed, the profit is added to the total, and the search ends with break. If the loop descends to j = −1, there is no suitable slot and the job is silently skipped.
The array sorted by profit is Job 5 (50), Job 3 (40), Job 4 (30), Job 6 (30), Job 1 (20), Job 2 (10). Table 2.9 gives the placement of each job step by step. In the table the slots are numbered from 1.
| Job | Deadline | Profit | Slots checked | Decision | Slots 1–6 | total |
|---|---|---|---|---|---|---|
| 5 | 3 | 50 | 3 | into slot 3 | – – 5 – – – | 50 |
| 3 | 1 | 40 | 1 | into slot 1 | 3 – 5 – – – | 90 |
| 4 | 1 | 30 | 1 (full) | skipped | 3 – 5 – – – | 90 |
| 6 | 2 | 30 | 2 | into slot 2 | 3 6 5 – – – | 120 |
| 1 | 4 | 20 | 4 | into slot 4 | 3 6 5 1 – – | 140 |
| 2 | 1 | 10 | 1 (full) | skipped | 3 6 5 1 – – | 140 |
The method returns 140. The machine does Job 3 on the first day, Job 6 on the second, Job 5 on the third, and Job 1 on the fourth. The fifth and sixth slots stay empty; since no job's deadline exceeds 4, using these slots is not possible anyway. That 140 is the largest total profit was shown in the verification script by trying all subsets of the six jobs.
The interesting step in the trace is Job 4. Its profit is 30, equal to Job 6's, but its deadline is 1, and the first slot has been taken by the more profitable Job 3. There is no other slot for Job 4. Job 6, however, fits in the second slot because its deadline is 2. That one of two jobs with equal profit gets done and the other does not comes from their different deadlines.
Let five jobs be given as (number, deadline, profit): (1, 2, 100), (2, 1, 19), (3, 2, 27), (4, 1, 25), (5, 3, 15). The order by profit is Job 1, Job 3, Job 4, Job 2, Job 5. Job 1's deadline is 2; slot 2 is free and the job goes there (total 100). Job 3's deadline is also 2. Slot 2 is full, so the one before it is checked: slot 1 is free and the job goes there (total 127). The deadline of Job 4 and of Job 2 is 1; slot 1 is full and both are skipped. Job 5's deadline is 3; slot 3 is free (total 142). Result: the machine does Job 3, Job 1, and Job 5 in turn, and the total profit is 142.
2.4.4Wrong criteria
Either of the two decisions can be chosen wrongly. Consider the order of the jobs first. Sorting the jobs by deadline looks natural: let the urgent jobs be done first. But this criterion ignores profit. Consider two jobs with deadline 1: one has profit 10 and the other 40. Only one can be done. In a sort by deadline (with a stable sort) the job that comes first is selected; if the first one is the job with profit 10, the result is 10. Sorting by profit selects the job with 40. On the six jobs in the slides, sorting by deadline with the latest-free-slot rule gives a profit of 110; the profit order gives 140.
Now consider the choice of slot. Suppose the job is put in the earliest free slot at or before its deadline. In the six jobs of the slides, Job 5 (deadline 3) goes to the first slot. The only option for the following Job 3 is the first slot, but it is full; the job with profit 40 is lost. At the end the algorithm does Job 5, Job 6, and Job 1 and earns only 100. With the latest-free-slot rule the same jobs yield 140. A two-job example is shorter: let X have deadline 2 and profit 50, and Y have deadline 1 and profit 40. The earliest-free-slot rule puts X in the first slot and loses Y: 50. The latest-free-slot rule puts X in the second slot, and Y fits in the first: 90.
Putting a job in the earliest free slot at or before its deadline. This rule leaves no room for later jobs with close deadlines. The correct rule is the latest free slot. In the code this is ensured by the inner loop starting j at the deadline and counting backward; if the loop starts from 0 and counts forward, the algorithm is wrong.
2.4.5Correctness and cost
The correctness of the algorithm is shown in two parts. The first part is that the latest-free-slot rule rejects a job only if it really does not fit.
Let A be the set of jobs the algorithm has accepted so far and x the next job. If the latest-free-slot rule cannot find a free slot for x, then the jobs in A ∪ {x} cannot all be completed by their deadlines under any slot assignment.
Since no free slot was found for x, all the slots from 1 to d(x) are full. Let t ≥ d(x) be the largest number such that all the slots from 1 to t are full; slot t + 1 is empty, or t = n. Every job in slots 1–t has a deadline less than or equal to t. The reason is this: at the moment a job with a deadline greater than t was placed, slot t + 1 was empty, because slots are never emptied. The latest-free-slot rule would have put that job in t + 1 or a later slot, not between 1 and t. Hence the t jobs in slots 1–t and x, that is, all t + 1 jobs, have deadlines of at most t. t + 1 jobs do not fit in t slots. □
The second part is that the decreasing profit order is correct, and it is shown with an exchange argument. Let a be the most profitable job, and suppose it can meet its deadline alone. Let O be a best solution that does not contain a. If one of the slots 1–d(a) in O is empty, a is added there and the profit increases; this contradicts the optimality of O. If all are full, the job b in one of these slots is removed and a is put in its place. Since a is placed in a slot at or before its own deadline, the solution is feasible. Since k(a) ≥ k(b), the profit does not decrease. So there is a best solution containing a. The slides also recall this result in a more general language: the sets of jobs that can be completed together by their deadlines form a matroid, and in matroids the greedy selection in decreasing order of weight is always optimal. The correctness of Kruskal's algorithm is also an instance of the same general result.
The cost is computed as follows. Sorting takes O(n log n). For each job, the slot search looks at at most min(n, di) slots; if the largest deadline is dmax, the search takes O(n · dmax) in all. Since dmax can go up to n, the worst case is O(n2). For example, if all the jobs have deadline n, job i looks at i slots, and 1 + 2 + … + n = n(n + 1)/2 probes are made in total. This cost can be reduced with a disjoint-set (union-find) structure. Each full slot is linked to a set that points to the first free slot on its left. The latest free slot of a job is found with a single find call; when a slot fills, a union is made with the set on the left. With path compression and union by rank, each operation takes nearly constant time, and the slot search drops to nearly O(n) in total. The total cost is then determined by the sort.
2.5The fractional knapsack
A traveler's backpack can carry at most 50 kilograms. In front of the traveler are several sacks of spices; each sack has a known weight and value. The spice is divisible: if half of a sack is taken, half of its value is gained. What should the traveler put in the pack to carry the largest value? This question is the fractional knapsack problem. When the items cannot be divided, that is, when each item is either taken whole or not at all, the problem is called the 0/1 knapsack. The two problems are very similar, but the greedy approach gives the best result only in the first.
2.5.1The problem and the ratio criterion
Fractional knapsack: n items and a capacity W are given; item i has profit ki and weight wi. A portion 0 ≤ xi ≤ 1 of each item may be taken. The goal is to find the selection that satisfies the condition Σ xi wi ≤ W on the total weight and maximizes the total profit Σ xi ki.
How "efficient" an item is shows in the profit it brings per unit of weight. This value is called the item's ratio: ki / wi. The greedy criterion is to start from the item with the largest ratio and take as much of it as fits. If the whole item fits, it is taken whole. If it does not fit, a portion equal to the remaining capacity is taken and the pack is full. In the example in the slides the capacity is W = 50 and there are three items (Table 2.10).
| Item | Profit | Weight | Ratio |
|---|---|---|---|
| 1 | 60 | 10 | 6 |
| 2 | 100 | 20 | 5 |
| 3 | 120 | 30 | 4 |
The ratios are 6, 5, and 4; the items are already in ratio order. Item 1 is taken whole (10 kg, profit 60). Item 2 is taken whole (20 kg, profit 100). A capacity of 20 kg remains, but item 3 weighs 30 kg. 20/30 of item 3 is taken, earning 120 · 20/30 = 80. The total is 60 + 100 + 80 = 240.
Note that the ratio criterion does not take the item with the largest profit first. Item 3 has the largest profit (120), but it also has the largest weight and brings the least profit per kilogram. Taking in decreasing order of profit selects all of item 3 (30 kg, 120) and all of item 2 (20 kg, 100) and stops at 220. Taking in increasing order of weight gives the same result as the ratio order in this example, but that is a coincidence: it fails on an input containing a heavy, very profitable item and a light but worthless one.
2.5.2Code and trace
The fractional method in the slides sorts the items by decreasing ratio and fills the pack:
static double fractional(Item[] s, int W) {
Arrays.sort(s, (a, b) -> Double.compare(b.ratio(), a.ratio()));
double profit = 0;
int left = W;
for (Item x : s) {
if (x.weight <= left) { // fits whole
left -= x.weight;
profit += x.profit;
} else { // fractional part
profit += x.profit * (double) left / x.weight;
break;
}
}
return profit;
}The Item class has the fields profit and weight and the method ratio(); ratio() returns (double) profit / weight. The comparator Double.compare(b.ratio(), a.ratio()) moves the item with the larger ratio forward. Here Double.compare is used instead of subtraction, because the ratios are fractional, and if the difference of two ratios is converted to an integer, differences like 0.5 are lost. left is the capacity remaining in the pack. For each item the loop first checks whether the whole item fits. If it does, it subtracts the weight from the capacity and adds the profit. If it does not, the else branch takes a portion of left / weight of the item. The pack is now exactly full and the loop exits with break. The (double) cast matters when computing the profit of the fractional portion: if left / x.weight were written as integer division, 20/30 would be rounded down to zero.
| Item (ratio) | Condition weight <= left | Action | left | profit |
|---|---|---|---|---|
| start | — | sort: 1, 2, 3 | 50 | 0 |
| 1 (6) | 10 ≤ 50 true | taken whole | 40 | 60 |
| 2 (5) | 20 ≤ 40 true | taken whole | 20 | 160 |
| 3 (4) | 30 ≤ 20 false | 20/30 taken: 120 · 20/30 = 80; break | 20 | 240 |
In the last row left stays at 20, because the else branch does not update the capacity; since the loop is broken right after, this value is never used again. The method returns 240.0.
The dominant part of the cost is the sort: O(n log n). The scan looks at at most n items and takes O(n). Instead of sorting, the item with the largest ratio can be taken from a heap at each step; if the pack fills early, only a few items are removed from the heap, and the total time drops to O(n + m log n) (m is the number of items taken). There is also a linear-time method based on median finding.
Let the capacity be W = 10 and the items (profit, weight) be (10, 5), (40, 4), (30, 6), (50, 3). The ratios are 2, 10, 5, and about 16.7 respectively. The ratio order is (50, 3), (40, 4), (30, 6), (10, 5). (50, 3) is taken whole: 7 left, profit 50. (40, 4) is taken whole: 3 left, profit 90. (30, 6) does not fit; 3/6 of it is taken and 30 · 3/6 = 15 profit is added. The total is 105. (10, 5) is not taken at all.
2.5.3Why is the ratio criterion optimal?
The greedy algorithm that takes the items in decreasing order of ratio, as much as fits, finds the optimal solution of the fractional knapsack problem.
Number the items so that k1/w1 ≥ k2/w2 ≥ … ≥ kn/wn. If the total weight is less than W, everything is taken and there is nothing to say; so assume the pack gets full. Let G be the greedy solution and O a best solution. If O is different, let i be the first item at which the two solutions differ. Since the greedy method took as much of i as could fit, O has taken less of i. Since the pack of O is also full, this shortfall has been made up by taking extra of some item j that comes after i. In O, δ kilograms of j are removed and δ kilograms of i are put in their place. The weight does not change and the solution is feasible. The profit changes by δ · (ki/wi − kj/wj), and this value is nonnegative, because the ratio of i is not smaller than that of j. The change moves O one step closer to G without lowering its profit. When this operation is repeated a finite number of times, O turns into G; so the profit of G is not less than that of O. □
The crucial step of the proof is that weight can be exchanged in small portions. δ kilograms can be removed from one item and added to another, because the items are divisible. Every kilogram of the highest-ratio item brings at least as much profit as any other choice of the same weight. There is therefore no reason not to take it to the end.
2.5.4The ratio criterion in the 0/1 knapsack
If the items cannot be divided, the exchange step in the proof collapses. Consider the same three items and the 50 kg pack, but this time each item is either taken whole or not at all. The ratio criterion takes item 1 and item 2 (30 kg, profit 160). Item 3 does not fit in the remaining 20 kg and is skipped. The result is 160. Yet items 2 and 3 together weigh exactly 50 kg and bring 220. Comparing all the selections shows that this is the best. The single items bring 60, 100, and 120. The pairs bring 1 + 2 = 160, 1 + 3 = 180, and 2 + 3 = 220. All three items together weigh 60 kg and do not fit.
| Method | Selection | Weight | Profit |
|---|---|---|---|
| fractional, ratio criterion | 1, 2, and 20/30 of 3 | 50 | 240 (optimal) |
| 0/1, ratio criterion | 1, 2 | 30 | 160 |
| 0/1, optimal | 2, 3 | 50 | 220 |
In the 0/1 case the ratio criterion cannot fill the 20 kg gap. In the fractional case this gap is filled by a portion of item 3. In the 0/1 case, portions cannot be taken and the gap stays worthless. The exchange argument fails too: if item 3 is removed from the best solution and replaced by item 1, the weight drops to 30 kg but the profit falls from 220 to 160. Because the weights are not equal, the exchange cannot be made in the form "same weight, more profit". The 0/1 knapsack is solved by dynamic programming in O(n · W) time.
The value of the fractional solution is an upper bound on the value of the 0/1 solution: a 0/1 solution is also a feasible solution of the fractional problem, so it cannot exceed the value of the fractional optimum. In the example 220 ≤ 240. This bound is used for pruning in the algorithms that solve the 0/1 knapsack by branch and bound.
Applying the ratio criterion, which is optimal for the fractional problem, to the 0/1 knapsack. The input of the two problems is the same; only the answer to "can an item be divided?" differs. This small difference removes the greedy-choice property. In the 0/1 problem the ratio criterion can be used only as a heuristic.
2.6The greedy choice in the minimum spanning tree
The minimum spanning tree is one of the most successful applications of the greedy approach. A spanning tree of a connected, weighted, undirected graph is a connected, acyclic subgraph that contains all the vertices of the graph; in a graph with V vertices it has exactly V − 1 edges. The spanning tree with the smallest sum of edge weights is called the minimum spanning tree (MST). Connecting a network of cities with the least cable is a typical application of this problem. The algorithms of Kruskal, Prim, and Borůvka find the MST, and all three are greedy. This section does not describe the algorithms from scratch; it explains why the greedy choice of all three is safe through a single property.
2.6.1The cut property
Let the vertices of a graph be divided into two nonempty sets: S and V − S. This division is called a cut. Edges with one endpoint in S and the other in V − S cross the cut. Every spanning tree must contain at least one edge crossing the cut; otherwise no connection can be made between S and V − S.
Take any cut of a connected, weighted, undirected graph. If e is the edge of smallest weight among the edges crossing the cut, then there is an MST that contains e. If the lightest edge crossing the cut is unique, this edge is in every MST.
The proof is again an exchange argument. Let T be an MST that does not contain e = (u, v), with u ∈ S and v ∈ V − S. Since T is a tree, there is a single path from u to v. Since this path starts in S and ends in V − S, it crosses the cut at least once; let e' be an edge it crosses by. e is added to T and e' is removed. Removing e' splits the tree into two parts, and e reconnects these two parts; the result is again a spanning tree. The weight changes by w(e) − w(e'). Since e is the lightest edge crossing the cut, this difference is not greater than zero. Since the new tree is no heavier than T, it too is an MST and contains e. If e is the unique lightest edge, the difference is strictly negative; in that case T could not be an MST, and there is no MST that does not contain e. □
In the graph of Figure 2.12, four edges cross the cut: p–s (9), r–s (4), r–t (8), and q–t (11). The lightest is r–s, and since it is the unique lightest edge, it is in every MST. The MST of the graph indeed consists of the edges t–u (2), p–r (3), p–q (4), r–s (4), and s–u (6); the total weight is 19. Of the edges crossing the cut, only r–s enters the tree. This is no accident: it suffices for the MST to connect S and V − S by exactly one edge, and that edge must be the cheapest.
The meaning of the cut property for greedy algorithms is this. With the edges it has selected so far, the algorithm has built some components. A cut is chosen that separates one of these components from the others. None of the selected edges crosses this cut. If the lightest edge crossing the cut is added, the result, together with the selected edges, is still part of an MST. The exchange in the proof works in this case too, because the removed e' crosses the cut and is therefore not one of the selected edges. For this reason the algorithm never has to undo any of its choices.
If the weights are all different, the lightest edge of every cut is unique and the MST is unique as well. In the graph in the figure, p–q and r–s both have weight 4, so the weights are not all different; even so, the MST of this graph is unique. That all weights are different is sufficient for uniqueness but not necessary. Equal weights can lead to more than one MST, but all the MSTs have the same total weight.
In a graph with four vertices, the vertices are split into {A, B} and {C, D}; the edges crossing the cut are A–C 5, B–C 3, and B–D 4. The lightest edge crossing the cut is B–C (3) and it is the unique lightest edge; by the cut property it is in every MST. For A–C and B–D the cut property alone says nothing. Whether they are in the MST depends on the remaining edges of the graph. For example, if the edges A–B and C–D also exist and are light, the MST crosses the cut with B–C alone.
Reading the cut property as "the lightest edges are always safe". What is safe is the lightest edge crossing a cut. If the lightest edges of the whole graph are taken in order, a cycle can form: the third edge of the cycle reconnects two vertices that the first two already connect, and it crosses no cut. Kruskal's algorithm therefore discards the edge that forms a cycle; every cut that separates the endpoints of the discarded edge is already crossed by one of the selected edges.
2.6.2Kruskal, Prim, and Borůvka: three cuts
The three MST algorithms use the same property with different cuts. The difference is which cut is chosen at each step. Table 2.13 sets the three algorithms side by side.
| Kruskal | Prim | Borůvka | |
|---|---|---|---|
| Greedy choice | the lightest edge in the whole graph that forms no cycle | the lightest edge leaving the tree | the lightest edge leaving each component |
| Growth | forest → tree | a single tree, vertex by vertex | a forest, merging in rounds |
| Cut used | the two components that the edge's endpoints separate | the tree versus the remaining vertices | each component versus the rest |
| Data structure | sorting and disjoint sets | priority queue | disjoint sets |
| Time | O(E log V) | O(E log V) (binary heap) | O(E log V) |
| Suited to | sparse graphs, edge lists | dense graphs, adjacency structures | parallel or distributed computing |
Kruskal examines the edges in increasing order of weight. If the next edge connects two different components, it is added; if it connects two vertices of the same component, it is skipped because it would form a cycle. The cut used for the added edge is the one between the component of one of its endpoints and the remaining vertices. If a lighter edge crossed this cut, it would have been examined earlier and added; so the added edge is the lightest of the cut. The component check is done with a disjoint-set structure. The sort determines the time: O(E log E). Since E ≤ V2, log E ≤ 2 log V, and this time is also written O(E log V).
Prim grows a single tree starting from one vertex. At each step the lightest edge joining a vertex in the tree to a vertex outside it is added. The cut used is the one between the vertices of the tree and the remaining vertices. The cheapest connection of each vertex outside the tree to the tree is kept in a priority queue. With a binary heap the time is O((V + E) log V); in a connected graph this equals O(E log V). On dense graphs a version with array scanning can be faster, at O(V2).
Borůvka works in rounds. In each round every component finds the lightest edge leaving it, and all these edges are added together. Each component uses its own cut, namely the cut "this component versus everything else". Since each round at least halves the number of components, there are at most ⌈log2 V⌉ rounds, and each round takes O(E); the total is O(E log V). Because the components' choices are independent of one another, the algorithm suits parallel execution. If weights can be equal, a consistent tie-breaker is needed; otherwise two components may pick different edges of equal weight and form a cycle.
The three algorithms find the same MST on the same graph, provided the weights are distinct. If the weights are distinct, the MST is unique and it is the tree all of them find. If there are equal weights, they may find different trees, but their total weights are the same. They differ in the order in which they consider the edges and in the data structure they need. When all the edges have the same weight, for instance, every spanning tree is an MST; Kruskal in this case produces some spanning tree depending on the order of the edge list.
The weight of an edge alone does not say whether it will be in the MST. The edges that are in every MST are those that are the unique lightest edge of some cut. The edges that are in no MST are those that are the unique heaviest edge of some cycle; this second rule is called the cycle property, and the reverse-delete algorithm is based on it. Adding the same constant to all edges does not change the MST, because the order of the edges is preserved and, since every spanning tree has V − 1 edges, all the totals increase by the same amount. If the edges are processed in decreasing order, Kruskal in the same way finds the maximum spanning tree.
2.7Huffman coding
A text is stored on a computer as bits. Each character is assigned a bit string, that is, a codeword, and the text is formed by writing these codes one after another. In encodings such as ASCII every character's code has the same length. In real texts, however, characters do not occur equally often. In a Turkish text the letters "a" and "e" appear very often and "ğ" and "j" very rarely. If frequent characters are given short codes and rare characters long codes, the total length of the text shrinks. Huffman coding is a greedy algorithm that applies this idea in the best possible way.
2.7.1Fixed-length and variable-length codes
Huffman coding is a lossless data compression method: when the compressed data is decoded, the original data comes back bit for bit. David Huffman developed the method in 1952, as a student, for a term paper. The example text in the slides is 25 characters long and contains only six distinct characters: F, O, R, G, E, and T. To tell six characters apart, a fixed-length code needs ⌈log2 6⌉ = 3 bits; 2 bits can distinguish only four characters. In this case the text takes 25 × 3 = 75 bits. If every character were stored in 8-bit ASCII, it would take 200 bits.
In a variable-length code the codewords have different lengths. The total length of the text is the sum, over characters, of frequency times code length:
Total bits = Σ freq(c) · length(c)
To reduce this sum, the codes of the most frequent characters must be kept short. But codes cannot be shortened arbitrarily; the shortened codes must still be uniquely decodable.
2.7.2Prefix-free codes
Let the codes be a = 0, b = 01, c = 1. Given the bit string "01", it cannot be told whether it is "ab" or just "b". The source of the problem is that the code of a, 0, is at the beginning of the code of b, 01. The problem can be solved by placing a separator between codewords, but the separator also spends bits. A better solution is for no code to be the beginning of another code.
A code in which no codeword is a prefix of another codeword is called a prefix-free code. A bit string written with a prefix-free code is decoded uniquely by reading from left to right, without using a separator.
Prefix-free codes are represented by binary trees. One starts from the root; a left edge means 0 and a right edge means 1. Each character sits at a leaf, and the bits on the path from the root to that leaf are the character's code. If a character stood at an internal node, its code would be a prefix of the codes of the leaves below it. Since characters stand only at leaves, no code can be a prefix of another. The length of a code is the depth of the character in the tree.
Decoding is done on the tree. One starts at the root; as each bit is read, one descends to the left child if it is 0 and to the right child if it is 1. When a leaf is reached, the character at that leaf is written and one returns to the root. The moment a codeword ends is the moment a leaf is reached, and this moment is known exactly. For example, with the tree on the right of Figure 2.13, the string "00110" is read as 00 | 1 | 1 | 0…: the first two bits give a, the next bit gives c, and the next gives c again. The last 0 does not reach a leaf by itself; the string came in incomplete.
The tree of an optimal prefix-free code is a full binary tree: every internal node has two children. If there were an internal node with a single child, that node could be skipped and its child moved up; all the codes below it would become one bit shorter and the codes would remain prefix-free. In the left tree in the figure, the node a, the left child of the root, has a single child; the right tree is better for this reason.
Consider four sets of codes. {0, 10, 110, 111} is prefix-free: the only code beginning with 0 is 0, the only code beginning with 10 is 10, and 110 and 111 are not prefixes of each other. This set corresponds to a tree with four leaves, extending to the right. {0, 01, 110, 111} is not prefix-free; 0 is a prefix of 01. {1, 10, 00, 01} is not prefix-free; 1 is a prefix of 10. {00, 01, 0, 11} is not prefix-free; 0 is a prefix of both 00 and 01.
2.7.3The steps of the algorithm
The Huffman algorithm builds the tree from the bottom up. Each character starts as a single-node tree with its own frequency. At each step the two trees with the smallest frequencies are merged: they become the children of a new internal node, and the frequency of the new node is the sum of its children's frequencies. When a single tree remains, that tree is the Huffman tree. The steps are listed as follows:
- The frequency of each character is computed.
- A leaf is created for each character. The two nodes with the smallest frequencies are merged into a new internal node; this step is repeated until a single node remains.
- In the tree, the code of each character is read off the path from the root to its leaf: left edge 0, right edge 1.
- The text is encoded with these codes.
The greedy choice is in the second step: at each merge, the two trees with the smallest frequencies at that moment are selected. The leaves of these two trees sink one level deeper after the merge, that is, their codes grow by one bit. Lengthening the codes of the rarest characters is the choice that increases the total number of bits the least. The frequencies in the example in the slides are given in Table 2.14.
| Character | F | O | R | G | E | T |
|---|---|---|---|---|---|---|
| Frequency | 2 | 3 | 4 | 4 | 5 | 7 |
For n characters exactly n − 1 merges are made, because each merge reduces the number of trees by one and one goes from n trees to one tree. The Huffman tree therefore has n leaves and n − 1 internal nodes. In the example there are six characters and five merges.
2.7.4Building the tree: code and trace
The huffman method in the slides builds the tree with a priority queue:
static Node huffman(char[] ch, int[] fr) {
PriorityQueue<Node> queue =
new PriorityQueue<>((a, b) -> a.f - b.f);
for (int k = 0; k < ch.length; k++)
queue.add(new Node(ch[k], fr[k]));
while (queue.size() > 1) {
Node left = queue.poll();
Node right = queue.poll();
Node parent = new Node('\0', left.f + right.f);
parent.left = left;
parent.right = right;
queue.add(parent);
}
return queue.poll();
}The Node class has four fields: the character ch, the frequency f, and the left and right child. In leaves the children are null. The queue is a PriorityQueue built with the comparator (a, b) -> a.f - b.f. This Java class is a min-heap; each call of poll() removes the node with the smallest frequency. The first loop creates a leaf for each character and adds it to the queue. The while loop runs as long as the queue holds more than one node. In each round poll() is called twice; the first node removed becomes the left child and the second the right child. The character of the new internal node is '\0', because internal nodes carry no character; its frequency is the sum of the two children. The new node is added back to the queue. When the loop ends, a single node remains in the queue, and it is the root of the tree.
| Round | Left (1st poll) | Right (2nd poll) | New node | Queue at end of round |
|---|---|---|---|---|
| start | — | — | — | F2, O3, R4, G4, E5, T7 |
| 1 | F2 | O3 | (5) = 2 + 3 | R4, G4, E5, (5), T7 |
| 2 | G4 | R4 | (8) = 4 + 4 | E5, (5), T7, (8) |
| 3 | (5) | E5 | (10) = 5 + 5 | T7, (8), (10) |
| 4 | T7 | (8) | (15) = 7 + 8 | (10), (15) |
| 5 | (10) | (15) | (25) = 10 + 15 | (25) |
The queue contents in the table are written in frequency order; the actual layout of the heap in its array is different. There are ties in the second and third rounds. In the second round G4 and R4 have the same frequency, and in the third round (5) and E5 do. Which comes out first depends on the internal layout of the heap, and therefore on the order in which the characters were added to the queue. The table matches the trace in the slides. When the characters are added in the order F, O, R, G, E, T, Java's PriorityQueue removes E5 first in the third round, and E becomes the left child. In that case the codes become E = 00, F = 010, O = 011; the remaining codes do not change. The code lengths and the total number of bits are the same in both cases: E has 2 bits, F and O have 3 bits.
The structure of the tree can be read from the table. The left child of the root is (10) and the right child is (15). The children of (10) are (5) and E, and the children of (15) are T and (8). Under (5) are F and O, and under (8) are G and R. E and T are at depth 2; F, O, G, and R are at depth 3. The two most frequent characters have received the shortest codes.
The total bit cost of the tree also equals the sum of the frequencies of the internal nodes: 5 + 8 + 10 + 15 + 25 = 63. The reason is this: a character contributes once to the frequency of every internal node on the path from the root to its leaf. The number of internal nodes on the path is the depth of the character. Thus the frequency of each character is counted as many times as its depth, and the total equals Σ frequency · depth. This observation also explains why Huffman picks the two smallest frequencies at every merge: the cost of each merge is the frequency of the new internal node, and the algorithm keeps this cost as small as possible at every step.
The cost is as follows. Adding the n leaves to the queue takes O(n log n). The loop runs n − 1 times and in each round does two poll calls and one add; each is O(log n). The total is O(n log n). Here n is the number of distinct characters, not the length of the text. If the frequencies are sorted in advance, a version that runs in O(n) time with two ordinary queues can also be written: the first queue holds the sorted leaves, and the second holds the internal nodes in the order they are created. Since the frequencies of the internal nodes created arrive in increasing order, the second queue stays sorted by itself.
Let the frequencies of six characters be a:5, b:9, c:12, d:13, e:16, f:45 (100 in all). The merges are, in order: a5 + b9 = 14; c12 + d13 = 25; (14) + e16 = 30; (25) + (30) = 55; f45 + (55) = 100. The left child of the root 100 is f and the right child is (55). The codes are f = 0, c = 100, d = 101, a = 1100, b = 1101, e = 111. The total number of bits is 45 · 1 + 12 · 3 + 13 · 3 + 16 · 3 + 5 · 4 + 9 · 4 = 224. The sum of the internal nodes gives the same result: 14 + 25 + 30 + 55 + 100 = 224. With a fixed 3-bit code the text would take 300 bits; the saving is about 25%. In this example f is so dominant that it receives a one-bit code.
2.7.5Generating the codes: code and trace
Once the tree is built, the code of every character is found by traversing the tree once. The recursive genCodes method in the slides does this:
static void genCodes(Node d, String code) {
if (d.left == null) { // leaf
System.out.println(d.ch + " = " + code);
return;
}
genCodes(d.left, code + "0"); // left: 0
genCodes(d.right, code + "1"); // right: 1
}The method takes a node and the bit string accumulated on the way to that node. If the node is a leaf, that is, if its left child is null, the character and its code are printed. Because the Huffman tree is a full binary tree, it suffices to look at the left child alone: internal nodes have both children, and leaves have none. If the node is internal, the method descends first to the left child with "0" appended to the code, then to the right child with "1" appended. This is a preorder traversal; the leaves are printed in order from left to right. The first call has the form genCodes(root, "").
| Call | Node | code | What happens? |
|---|---|---|---|
| 1 | (25), root | "" | internal node; descend left with "0" |
| 2 | (10) | "0" | internal node; descend left with "00" |
| 3 | (5) | "00" | internal node; descend left with "000" |
| 4 | F | "000" | leaf: F = 000 is printed |
| 5 | O | "001" | leaf: O = 001 is printed |
| 6 | E | "01" | leaf: E = 01 is printed |
| 7 | (15) | "1" | internal node; descend left with "10" |
| 8 | T | "10" | leaf: T = 10 is printed |
| 9 | (8) | "11" | internal node; descend left with "110" |
| 10 | G | "110" | leaf: G = 110 is printed |
| 11 | R | "111" | leaf: R = 111 is printed |
The method is called 11 times in all: once each for 6 leaves and 5 internal nodes. Since each node is visited once, the traversal makes O(n) node visits. The recursion depth equals the height of the tree; in the example there are 3 edges from the root to the deepest leaf. The string concatenation code + "0" creates a new string at each call and takes time proportional to its length. If this cost is also counted, the total work is proportional to the sum of the lengths of all the codes. If the codes are kept in a StringBuilder or in a character array, this extra cost is avoided.
If the text has a single distinct character (for example "AAAA"), the Huffman tree consists of a single node: the root is also a leaf. In this case genCodes(root, "") prints the empty string as the code of the character, and the text looks as if it were encoded in 0 bits. The decoder cannot know how many characters there are. In this special case the character must be given a code of at least 1 bit (for example "0").
2.7.6Encoding, decoding, and the saving
Table 2.17 gives the code of each character and its total contribution in the text.
| Character | Frequency | Code | Length | Bits (frequency · length) |
|---|---|---|---|---|
| F | 2 | 000 | 3 | 6 |
| O | 3 | 001 | 3 | 9 |
| E | 5 | 01 | 2 | 10 |
| T | 7 | 10 | 2 | 14 |
| G | 4 | 110 | 3 | 12 |
| R | 4 | 111 | 3 | 12 |
| Total | 25 | 63 |
The Huffman code writes the text in 63 bits; the fixed 3-bit code uses 75 bits. The saving is (75 − 63) / 75 = 16%. On average 63 / 25 = 2.52 bits fall to each character. The saving depends on how unbalanced the frequencies are. If all the characters occurred equally often, the saving would be very small; if one character is very dominant, as in the a–f example, the saving grows.
For encoding, the code of each character is written in order. The word "FORTE" becomes 000 | 001 | 111 | 10 | 01, that is, 13 bits. With the fixed code the same word would take 5 × 3 = 15 bits. No separator is placed between the bits during encoding; the vertical bars here are only to make reading easier.
For decoding, the tree is used. Take the bit string "1100110". One starts at the root. With 1, go right to (15); with 1, go right to (8); with 0, go left to G. G is written and one returns to the root. With 0, go left to (10); with 1, go right to E. E is written and one returns to the root. With 1, go right to (15); with 0, go left to T. T is written. The result is 110 | 01 | 10, that is, "GET". Decoding descends one edge per bit; a string of m bits is decoded in O(m) time.
The placement of the left and right children is arbitrary. For example, T could be made the right child of (15). In that case the codes change, but the code lengths and the total of 63 bits do not. For the same reason, which of the nodes with equal frequencies is chosen first can change the code lengths, but not the total number of bits. A text can have more than one optimal prefix-free code.
Compressed data cannot be decoded on its own; the same tree or code table must also be in the decoder's hands. The tree (or the code length of each character) is therefore sent along with the compressed data. On short texts this extra information can eat up the whole gain. In the 25-character example, the code table for six characters takes far more space than the 12 bits gained. Huffman coding therefore makes sense on long texts and large files.
There is also a theoretical lower bound on how good a code can be. If the proportion of the character c in the text is pc, the average number of bits per character cannot fall below H = −Σ pc log2 pc. This value is called the entropy of the text. The entropy of the example text is about 2.48 bits; the Huffman code uses 2.52 bits. The average of a Huffman code always lies between the entropy and the entropy plus one bit.
Trying to decode Huffman-compressed data without the tree or code table. The bit string does not say which character was written with which code. The encoder and the decoder must use the same tree. Two trees that differ in the placement of left and right children, or in how ties are broken, produce different codes from the same frequencies.
2.7.7Why is the Huffman code optimal?
The cost of a prefix-free code tree T is B(T) = Σ f(c) · dT(c), where f(c) is the frequency of the character and dT(c) its depth in the tree. That the tree Huffman builds minimizes this cost is shown in two steps: the greedy choice and optimal substructure.
Let x and y be the two characters with the smallest frequencies. There is an optimal code tree in which x and y are sibling leaves at the deepest level.
Let T be an optimal tree. An optimal tree is a full binary tree; there are therefore two leaves at the deepest level that are siblings of each other. Let them be a and b. Let the positions of x and a be swapped. The cost changes by:
B(T') − B(T) = f(x) · d(a) + f(a) · d(x) − f(x) · d(x) − f(a) · d(a) = −(f(a) − f(x)) · (d(a) − d(x))
Since x is the character with the smallest frequency, f(a) − f(x) ≥ 0. Since a is at the deepest level, d(a) − d(x) ≥ 0. The product is nonnegative, and with the minus sign in front, the difference cannot be greater than zero: B(T') ≤ B(T). The same exchange is done for y and b. In the end x and y are siblings at the deepest level and the cost has not increased; the tree is still optimal. □
Let x and y be replaced by a new character z with frequency f(z) = f(x) + f(y), and let T' be an optimal tree for the reduced alphabet. If the leaf z in T' is replaced by an internal node whose children are x and y, an optimal tree T for the original alphabet is obtained.
x and y are one level deeper than z. Hence B(T) = B(T') − f(z) · d(z) + (f(x) + f(y)) · (d(z) + 1) = B(T') + f(x) + f(y). Suppose T is not optimal: there is a T'' with smaller cost. By the previous theorem, x and y can be assumed to be siblings in T''. If these two leaves are deleted in T'' and their parent is made the leaf z, a tree for the reduced alphabet results whose cost is B(T'') − f(x) − f(y) < B(T'). This contradicts the optimality of T'. □
Together, the two theorems give the correctness of the Huffman algorithm by induction. In the first step the algorithm merges the two smallest frequencies; the greedy-choice theorem says there is an optimal tree containing this choice. The two merged characters behave like a single character z, and the problem shrinks by one character. The optimal-substructure theorem says that an optimal tree for the original problem is obtained from the optimal tree of the smaller problem. Thus the Huffman code is, among prefix-free codes, the one that minimizes the sum Σ frequency · depth.
2.7.8Cost and applications
The cost of all the stages of Huffman coding is as follows. In a text of m characters, let there be n distinct characters. Counting frequencies reads the text once: O(m). Building the tree takes O(n log n) and generating the codes takes O(n) node visits. Encoding reads the text once more and takes each character's code from the table: O(m) characters and work proportional to the number of output bits. Usually n is far smaller than m (for example, n ≤ 256 for one-byte characters); the total time is therefore in practice directly proportional to the length of the text.
Huffman coding is used not alone but often together with other methods. The DEFLATE format, used by ZIP and gzip files and PNG images, first shortens repeated strings with backward pointers, then encodes the resulting symbols with Huffman. In the JPEG image and MP3 audio formats too, the data is first transformed and quantized; the entropy coding of the last stage is done with Huffman codes. LZW is dictionary-based: it gives codes to repeated strings. Huffman is frequency-based: it gives codes to single characters according to their frequencies. The difference between the two approaches can be seen by comparing the results of RLE and LZW with those of Huffman on the same texts.
2.8Other greedy algorithms
The greedy idea underlies many other algorithms as well. Some of them give a provably optimal result. Others do not guarantee the best result, but it is known how far the result can be from the best.
Dijkstra and Prim. Both algorithms take the node with the smallest key from a priority queue at each step and select it permanently. In Dijkstra the key is the shortest known distance from the source to that node; in Prim it is the weight of the cheapest edge connecting the node to the tree. A selected node is never changed again. Dijkstra finds shortest paths correctly in graphs with no negative-weight edges; if there is a negative edge, a distance counted as final can later become shorter and the greedy choice errs. Prim, since it rests on the cut property, is correct regardless of the sign of the weights.
Graph coloring. Coloring a graph with the fewest colors, subject to neighboring vertices getting different colors, is an NP-hard problem. Greedy coloring takes the vertices in some order and gives each vertex the smallest color not used by its neighbors. It is fast, but the number of colors used depends on the order. Consider a cycle of six vertices: a1 – b2 – a3 – b1 – a2 – b3 – a1. This cycle can be colored with two colors: the a's one color, the b's the other. If the vertices are colored in the order a1, a2, a3, b1, b2, b3, two colors indeed suffice. But if the order is a1, b1, a2, b2, a3, b3, then since a1 and b1 are not neighbors, both get color 1. Since a2 is a neighbor of b1, it gets 2, and since b2 is a neighbor of a1, it also gets 2. a3 is a neighbor of both b1 (1) and b2 (2) and gets 3; b3 gets 3 for the same reason. A bad order has caused one extra color to be used. Greedy coloring uses at most "the maximum degree plus one" colors; this bound always holds.
Bin packing. Items of given sizes are to be placed into the fewest bins of fixed capacity. This problem is also NP-hard. The first fit rule puts each item into the first bin it fits in; if it fits in none, it opens a new bin. The best fit rule puts the item into the bin that is left with the least space after it is placed. Let the capacity be 10 and the items 2, 5, 4, 7, 1, 3, 8. First fit in this order opens four bins: [2, 5, 1], [4, 3], [7], [8]. If the items are first sorted from largest to smallest (first fit decreasing), three bins suffice: [8, 2], [7, 3], [5, 4, 1]. Since the total size is 30, fewer than three bins is impossible. It has been proved that first fit decreasing uses at most about 11/9 · OPT + 1 bins, where OPT is the minimum number of bins.
Maximum coverage. A universe of elements and subsets of these elements are given; at most k sets are to be chosen so as to cover as many elements as possible. The greedy algorithm at each step chooses the set that covers the most elements not yet covered. It has been proved that this method covers at least 1 − 1/e ≈ 0.632 of what the optimum covers, that is, about 63% of the best. An algorithm guaranteeing a better ratio in polynomial time does not exist unless P = NP.
These last examples show the role of greedy algorithms in NP-hard problems. Finding the best solution is very expensive, but a greedy algorithm quickly produces a solution and gives a proven bound on the quality of this solution. Such algorithms are called approximation algorithms; the worst-case ratio of the solution to the optimum is called the approximation ratio.
2.9Comparison and common mistakes
Table 2.18 compares the problems studied in the notes by greedy criterion, time, and optimality.
| Problem | Greedy criterion | Time | Optimal? |
|---|---|---|---|
| Coin change | the largest coin that fits | O(k + count) | only in canonical systems |
| Activity selection | earliest finish | O(n log n) | yes |
| Job sequencing | the most profitable job, latest free slot | O(n2) | yes |
| Fractional knapsack | largest profit/weight ratio | O(n log n) | yes (no in the 0/1 version) |
| MST | the lightest edge crossing a cut (Kruskal, Prim, Borůvka) | O(E log V) | yes |
| Huffman | the two lowest-frequency trees | O(n log n) | yes |
The last column of the table sums up the most important lesson of the greedy approach. In five problems the greedy algorithm is optimal, and this is proved by an exchange argument in each. In coin change the result depends on the coin system. In the 0/1 knapsack the ratio criterion misses the best. The O(n2) in job sequencing is the worst case of the direct slot search in the slides; with disjoint sets this too drops to O(n log n).
The mistakes treated in detail in different places in these notes can be gathered as follows:
- Counting greedy as correct without a proof. With the coins {1, 3, 4} and the amount 6, greedy uses 3 coins and the best solution 2. For every problem the greedy-choice property must be shown; a few successful trials are not a proof.
- A wrong criterion. In activity selection, choosing the earliest-starting, the shortest, or the least-conflicting activity does not guarantee the best result. The correct criterion is earliest finish.
- The ratio criterion in the 0/1 knapsack. The ratio criterion, which is optimal for the fractional problem, does not guarantee the best when the items cannot be divided.
- The earliest free slot. In job sequencing, putting a job in the earliest free slot at or before its deadline leaves no room for jobs with close deadlines. The latest free slot must be chosen.
- Misreading the cut property. What is safe is the lightest edge crossing a cut. If the lightest edges of the whole graph are taken blindly, a cycle can form; Kruskal therefore discards the edge that forms a cycle.
- Decoding without the tree in Huffman coding. Without the code table or the tree, the data cannot be decoded. In a text with a single character the root is a leaf; the code must be given at least 1 bit.
2.10Summary
- Greedy algorithm: builds the solution step by step, at each step makes the choice that looks best at that moment according to a criterion, and does not undo its decisions. The typical structure is a sort and a single pass; the time is mostly O(n log n).
- Conditions for correctness: by the greedy-choice property, there is a best solution that contains the first choice. By optimal substructure, the best solution of the remaining problem, together with the first choice, gives the best solution of the whole. If the two properties hold together, the greedy algorithm is optimal; if not, it is only a heuristic.
- The exchange argument: a part of an arbitrary best solution is replaced by the greedy choice; the solution is shown to remain feasible and not get worse. The proofs for activity selection, job sequencing, the fractional knapsack, the cut property, and Huffman use this pattern.
- Coin change: the largest coin that fits is chosen; O(k + count). It is optimal in canonical systems (e.g. {50, 25, 10, 5, 1}); the amounts 6 and 10 in the system {4, 3, 1} and the amount 14 in the system {10, 7, 1} are counterexamples. The best result is found by the recurrence minCoins[t] = 1 + min minCoins[t − p] in O(k · T) time.
- Activity selection: the activities are sorted by finish; every activity that starts after the finish of the last selected is selected. O(n log n); 6 of the ten activities in the slides are selected.
- Job sequencing: the jobs are placed in decreasing order of profit, each in the latest free slot at or before its deadline. By direct search the worst case is O(n2); with disjoint sets, nearly the sorting time. On the six jobs in the slides the total profit is 140.
- Fractional knapsack: the items are taken in decreasing order of profit/weight ratio, as much as fits; a portion of the last item may be taken. O(n log n); 240 in the example. In the 0/1 version the same criterion gives 160, and the best is 220.
- MST and the cut property: the lightest edge crossing a cut belongs to an MST. Kruskal (a cut separating two components), Prim (the tree versus the rest), and Borůvka (each component versus the rest) use this property with different cuts; all three are O(E log V).
- Huffman coding: the two lowest-frequency trees are merged repeatedly; left edge 0, right edge 1. The codes are prefix-free and the sum Σ frequency · depth is minimal. In the example, 63 bits (75 with a fixed code); the tree is built in O(n log n) time and must be sent to the decoder.
- Approximation algorithms: on NP-hard problems such as graph coloring, bin packing, and maximum coverage, greedy algorithms do not guarantee the best but produce good solutions with proven ratios.
2.11Key terms
- greedy algorithm
- greedy-choice property
- optimal substructure
- exchange argument
- heuristic
- coin change problem
- canonical coin system
- activity selection
- job sequencing with deadlines
- matroid
- fractional knapsack
- 0/1 knapsack
- minimum spanning tree (MST)
- cut
- cut property
- Huffman coding
- prefix-free code
- compression
- entropy
- priority queue
- graph coloring
- approximation algorithm
- approximation ratio
2.12Test Yourself
Let the coin system be {9, 6, 5, 1}. How many coins does greedy change use for the amounts 11 and 12? What are the best solutions? Is this system canonical?
Answer
For 11 greedy uses 3 coins with 9 + 1 + 1; the best is 2 coins with 6 + 5. For 12 greedy uses 4 coins with 9 + 1 + 1 + 1; the best is 2 coins with 6 + 6. The system is not canonical. 11 is the smallest amount on which greedy fails in this system, and it is smaller than 15, the sum of the two largest coins.
Eight activities are given as (s, f) pairs and numbered 1 to 8: (0, 3), (1, 2), (2, 5), (3, 4), (4, 7), (5, 6), (6, 9), (8, 10). Which activities does the earliest-finish criterion select?
Answer
Order by finish: #2 (1, 2), #1 (0, 3), #4 (3, 4), #3 (2, 5), #6 (5, 6), #5 (4, 7), #7 (6, 9), #8 (8, 10). #2 is selected (last finish 2). #1 starts at 0 and is skipped. #4 starts at 3 and is selected (4). #3 is skipped. #6 starts at 5 and is selected (6). #5 is skipped. #7 starts at 6 and is selected (9). #8 starts at 8, and since 8 < 9 it is skipped. The result is 4 activities: #2, #4, #6, #7. If all subsets are tried, no compatible set of 5 activities is found.
In activity selection, does the algorithm that selects the latest-starting activity at each step give the best result? Justify your answer.
Answer
Yes. If the time axis is reversed (each [s, f) interval becomes [−f, −s)), the latest-starting activity turns into the earliest-finishing one, and the compatibility relation does not change. The exchange argument for earliest finish holds unchanged. The latest-starting a can be put in place of the last activity of a best solution. a does not start earlier than that activity and does not overlap the earlier ones.
Seven jobs are given as (name, deadline, profit): (A, 3, 35), (B, 4, 30), (C, 4, 25), (D, 2, 20), (E, 3, 15), (F, 1, 12), (G, 2, 5). How does greedy job sequencing fill the slots, and what is the total profit? What would the result be if jobs were placed in the earliest free slot?
Answer
The profit order is A, B, C, D, E, F, G. A → slot 3; B → slot 4; C's deadline is 4, slots 4 and 3 are full, so it goes to slot 2; D's deadline is 2, slot 2 is full, so it goes to slot 1. No suitable free slot is left for E, F, and G. Slots 1–4: D, C, A, B; the total profit is 20 + 25 + 35 + 30 = 110, the best result. With the earliest-free-slot rule, A goes to slot 1, B to slot 2, C to slot 3; there is no room for D, E, F, and G, and the total stays at 90.
Let the capacity be W = 20 and the items (profit, weight) be (48, 12), (30, 10), (28, 10), (5, 1). What is the value of the fractional knapsack? If the items could not be divided, what would the ratio criterion find, and what would the best result be?
Answer
The ratios are 4, 3, 2.8, and 5. The ratio order is (5, 1), (48, 12), (30, 10), (28, 10). (5, 1) and (48, 12) are taken whole: 13 kg, profit 53. For the remaining 7 kg, 7/10 of (30, 10) is taken: 21. The fractional value is 74. In the 0/1 case the ratio criterion takes (5, 1) and (48, 12); neither of the next two items fits in the remaining 7 kg, and the result is 53. The best 0/1 selection is (30, 10) with (28, 10): exactly 20 kg, profit 58.
Let the frequencies be A:1, B:1, C:2, D:3, E:5, F:8. Find the merges of the Huffman tree, the code lengths, and the total number of bits. Compare with a fixed-length code.
Answer
The merges: 1 + 1 = 2; 2 + 2 = 4; 3 + 4 = 7; 5 + 7 = 12; 8 + 12 = 20. Because each merge includes the result of the previous merge, the tree extends in a single direction. The code lengths are F 1, E 2, D 3, C 4, and A and B 5 bits. The total is 8 · 1 + 5 · 2 + 3 · 3 + 2 · 4 + 1 · 5 + 1 · 5 = 45 bits; the sum of the internal nodes also gives 2 + 4 + 7 + 12 + 20 = 45. For six characters a fixed code needs 3 bits: 20 × 3 = 60 bits.
Let the codes be F = 000, O = 001, E = 01, T = 10, G = 110, R = 111. To what text does the bit string 11001101001111 decode? How many bits would the same text take with a fixed 3-bit code?
Answer
Reading from the left: 110 → G, 01 → E, 10 → T, 10 → T, 01 → E, 111 → R. The text is "GETTER". It takes 14 bits with Huffman and 6 × 3 = 18 bits with the fixed code. Since no code is a prefix of another, the place where each code ends is known exactly.
Are the following two statements true? (a) In a connected graph with distinct weights, the lightest edge is in every MST. (b) The heaviest edge is in no MST.
Answer
(a) True. A cut is formed by putting one endpoint of the lightest edge in S and the other in V − S. This edge is the lightest of the edges crossing the cut, and since it is the unique lightest, it is in every MST by the cut property. (b) False. The heaviest edge can be a bridge: if the graph splits in two when it is deleted, it has to be in every spanning tree. For an edge to be excluded from the MST, it must be the unique heaviest edge of some cycle.
At which step does the exchange argument given for the fractional knapsack fail in the 0/1 knapsack?
Answer
The proof removes δ kilograms of a low-ratio item from the best solution and puts δ kilograms of a high-ratio item in its place. This exchange preserves the weight and does not reduce the profit. In the 0/1 case items cannot be taken in portions; only whole items can be exchanged. When two items of different weights are exchanged, either the capacity is exceeded or a worthless gap is left in the pack. Either the feasibility condition or the "no worse" condition breaks.
Let all of n = 106 jobs have deadline n. How many slot probes does job sequencing with direct slot search make? About how many with disjoint sets?
Answer
Job i starts at the latest slot and searches backward for the first free slot; because the previous i − 1 jobs have filled the last slots, it looks at i slots. The total is 1 + 2 + … + n = n(n + 1)/2 ≈ 5 · 1011 probes. With disjoint sets, each job is placed with a few
findandunioncalls, and the total work is nearly linear, that is, on the order of a few million steps. In this case the time is determined by the sort, which makes about n log2 n ≈ 2 · 107 comparisons.
2.13Further reading
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (4th ed., 2022), Chapter 15: activity selection, the elements of the greedy strategy, and the optimality of Huffman codes, given in full form for the proofs summarized here.
- J. Kleinberg and É. Tardos, Algorithm Design (2006), Chapter 4: interval scheduling, the "greedy stays ahead" and exchange-argument proof techniques, and counterexamples to the fewest-conflicts criterion are discussed in detail.
- R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Section 5.5: a complete Java implementation of Huffman compression, including writing and reading the tree to a file.
- D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes" (1952): the short and readable original paper in which the method was first published.
2.14References
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 (Chapter 15: Greedy Algorithms; Chapter 21: Minimum Spanning Trees).
- D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the IRE 40(9), 1098–1101, 1952.
- J. Kleinberg, É. Tardos, Algorithm Design, Addison-Wesley, 2006 (Chapter 4: Greedy Algorithms).
- D. Kozen, S. Zaks, "Optimal Bounds for the Change-Making Problem", Theoretical Computer Science 123(2), 377–388, 1994.
- J. B. Kruskal, "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem", Proceedings of the American Mathematical Society 7(1), 48–50, 1956.
- R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011 (Section 4.3: Minimum Spanning Trees; Section 5.5: Data Compression).
Related pages: Chapter 2 slides · © Sercan Külcü. All rights reserved.