Source code online books for professionals by professionals

remaining tasks, as this is the only way we’re allowed to extend it. Now, assume we have a promising partial schedule 
P. Some of its slots are filled in, and some are not. The fact that P is promising means that it can be extended to an 
optimal schedule—let’s call it S. Also, let’s say T is the next task under consideration.
We now have four cases to consider:
T won’t fit in P, because there is no room before the deadline. In this case, T can’t affect 
•
anything, so P is still promising once T is discarded.
T will fit in P, and it ends up in the same position as in S. In this case, we’re actually extending 
•
toward S, so P is still promising.
16
Versions of this problem can be found in Soltys’ book (see “References” in Chapter 4) and that of Cormen et al. (see “References” 
in Chapter 1). My proof closely follows Soltys’s, while Cormen et al. choose to prove that the problem forms a matroid, which means 
that a greedy algorithm will work on it.

---

Chapter 7 
■
 Greed Is Good? prove It! 
159
T will fit, but it ends up somewhere else. This might seem somewhat troubling.
•
T will fit, but S doesn’t contain it. Even more troubling, perhaps.
•
Clearly we need to address the last two cases, because they seem to be building away from the optimal schedule 
S. The thing is, there may be more than one optimal schedule—we just need to show that we can still reach one of 
them after T has been added.
First, let’s consider the case where we greedily add T, and it’s not in the same place as it would have been in S. 
Then we can build a schedule that’s almost like S, except that T has swapped places with another task T’. Let’s call 
this other schedule S’. By construction, T is placed as late as possible in S’, which means it must be placed earlier in 
S. Conversely, T’ must be placed later in S and therefore earlier in S’. This means that we cannot have broken the 
deadline of T’ when constructing S’, so it’s a valid solution. Also, because S and S’ consist of the same tasks, the profits 
must be identical.
The only case that remains is if T is not scheduled in the optimal schedule S. Again, let S’ be almost like S. The 
only difference is that we’ve scheduled T with our algorithm, effectively “overwriting” some other task T’ in S. We 
haven’t broken any deadlines, so S’ is valid. We also know that we can get from P to S’ (by almost following the steps 
needed to get to S, just using T instead of T’).
The last question then becomes, does S’ have the same profit as S? We can prove that it does, by contradiction. 
Assume that T’ has a greater profit than T, which is the only way in which S could have a higher profit. If this were the 
case, the greedy algorithm would have considered T’ before T. As there is at least one free slot before the deadline of 
T’, the greedy algorithm would have scheduled it, necessarily in a different position than T, and therefore in a different 
position than in S. But we assumed that we could extend P to S, and if it has a task in a different position, we have a 
contradiction.
Note
 
■
  this is an example of a proof technique called proof by cases, where we add some conditions to the situation 
and make sure to prove what we want for all cases that these conditions can create.
Summary
Greedy algorithms are characterized by how they make decisions. In building a solution, step-by-step, each added 
element is the one that looks best at the moment it’s added, without concern for what went before or what will happen 
later. Such algorithms can often be quite simple to design and implement, but showing that they are correct (that is, 
optimal) is often challenging. In general, you need to show that making a greedy choice is safe—that if the solution 
you had was promising, that is, it could be extended to an optimal one, then the one after the greedy choice is also 
promising. The general principles, as always, is that of induction, though there are a couple of more specialized ideas 
that can be useful. For example, if you can show that a hypothetical optimal solution can be modified to become 
the greedy solution without loss of quality, then the greedy solution is optimal. Or, if you can show that during the 
solution building process, the greedy partial solutions in some sense keep up with a hypothetical optimal sequence of 
solutions, all the way to the final solution, you can (with a little care) use that to show optimality.
Important greedy problems and algorithms discussed in this chapter include the knapsack problem (selecting a 
weight-bounded subset of items with maximum value), where the fractional version can be solved greedily; Huffman 
trees, which can be used to create optimal prefix codes and are built greedily by combining the smallest trees in the 
partial solution; and minimum spanning trees, which can be built using Kruskal’s algorithm (keep adding the smallest 
valid edge) or Prim’s algorithm (keep connecting the node that is closest to your tree).

---

Chapter 7 
■
 Greed Is Good? prove It! 
160
If You’re Curious …
There is a deep theory about greedy algorithms that I haven’t really touched upon in this chapter, dealing with such 
beasts as matroids, greedoids, and so-called matroid embeddings. Although the greedoid stuff is a bit hard and the 
matroid embedding stuff can get really confusing fast, matroids aren’t really that complicated, and they present an 
elegant perspective on some greedy problems. (Greedoids are more general, and matroid embeddings are the most 
general of the three, actually covering all greedy problems.) For more information on matroids, you could have a look 
at the book by Cormen et al. (see the “References” section of Chapter 1).
If you’re interested in why the change-making problem is hard in general, you should have a look at the material 
in Chapter 11. As noted earlier, though, for a lot of currency systems, the greedy algorithm works just fine. David 
Pearson has designed an algorithm for checking whether this is the case, for any given currency; if you’re interested, 
you should have a look at his paper (see “References”).
If you find you need to build minimum directed spanning trees, branching out from some starting node, you can’t 
use Prim’s algorithm. A discussion of an algorithm that will work for finding these so-called min-cost arborescences 
can be found in the book by Kleinberg and Tardos (see the “References” section of Chapter 1).
Exercises
7-1. Give an example of a set of denominations that will break the greedy algorithm for giving change.
7-2. Assume that you have coins whose denominations are powers of some integer k > 1.  
Why can you be certain that the greedy algorithm for making change would work in this case?
7-3. If the weights in some selection problem are unique powers of two, a greedy algorithm will 
generally maximize the weight sum. Why?
7-4. In the stable marriage problem, we say that a marriage between two people, say, Jack and Jill, 
is feasible if there exists a stable pairing where Jack and Jill are married. Show that the Gale-Shapley 
algorithm will match each man with his highest-ranking feasible wife.
7-5. Jill is Jack’s best feasible wife. Show that Jack is Jill’s worst feasible husband.
7-6. Let’s say the various things you want to pack into your knapsack are partly divisible. That is, you 
can divide them at certain evenly spaced points (such as a candy bar divided into squares).  
The different items have different spacings between their breaking points. Could a greedy algorithm 
still work?
7-7. Show that the codes you get from a Huffman code are free of ambiguity. That is, when decoding a 
Huffman-coded text, you can always be certain of where the symbol boundaries go and which symbols 
go where.
7-8. In the proof for the greedy choice property of Huffman trees, it was assumed that the frequencies 
of a and d were different. What happens if they’re not?
7-9. Show that a bad merging schedule can give a worse running time, asymptotically, than a good one 
and that this really depends on the frequencies.
7-10. Under what circumstances can a (connected) graph have multiple minimum spanning trees?
7-11. How would you build a maximum spanning tree (that is, one with maximum edge-weight sum)?
7-12. Show that the minimum spanning tree problem has optimal substructure.
7-13. What will Kruskal’s algorithm find if the graph isn’t connected? How could you modify Prim’s 
algorithm to do the same?

---

Chapter 7 
■
 Greed Is Good? prove It! 
161
7-14. What happens if you run Prim’s algorithm on a directed graph?
7-15. For n points in the plane, no algorithm can find a minimum spanning tree (using Euclidean 
distance) faster than loglinear in the worst case. How come?
7-16. Show that m calls to either union or find would have a running time of O(m lg n) if you used 
union by rank.
7-17. Show that when using a binary heap as priority queue during a traversal, adding nodes once for 
each time they’re encountered won’t affect the asymptotic running time.
7-18. In selecting the largest nonoverlapping subset of a set of intervals, going left to right, why can’t we 
use a greedy algorithm based on starting times?
7-19. What would the running time be of the algorithm finding the largest set of nonoverlapping 
intervals?
7-20. Implement the greedy solution for the scheduling problem where each task has a cost and a hard 
deadline and where all tasks take the same amount of time to perform.
References
Gale, D. and Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical