Source code online books for professionals by professionals

Algorithm 1: add a shortest edge that joins two different fragments.
Algorithm 2: add a shortest edge that joins the fragment containing the root to another fragment.
Algorithm 3: For every fragment, add the shortest edge that joins it to another fragment.
For algorithm 2, the root is chosen arbitrarily at the beginning. For algorithm 3, it is assumed that all edge weights 
are different to ensure that no cycles can occur. as you can see, all three algorithms are based on the same 
fundamental fact—that the shortest edge over a cut is safe. also, in order to implement them efficiently, you  
need to be able to find shortest edges, detect whether two nodes belong to the same fragment, and so forth  
(as explained for algorithms 1 and 2 in the main text). still, these brief explanations can be useful as a memory 
aid or to get the bird’s-eye perspective on what’s going on.
Greed Works. But When?
Although induction is generally used to show that a greedy algorithm is correct, there are some extra “tricks” that 
can be employed. I’ve already used some in this chapter, but here I’ll try to give you an overview, using some simple 
problems involving time intervals. It turns out there are many problems of this type that can be solved by greedy 
algorithms. I’m not including code for these; the implementations are pretty straightforward (although it might be a 
useful exercise to actually implement them).
Keeping Up with the Best
This is what Kleinberg and Tardos (in Algorithm Design) call staying ahead. The idea is to show that as you build your 
solution, one step at a time, the greedy algorithm will always have gotten at least as far as a hypothetical optimal 
algorithm would have. Once you reach the finish line, you’ve shown that greed is optimal. This technique can be 
useful in solving a common example of greed: resource scheduling.

---

Chapter 7 
■
 Greed Is Good? prove It! 
156
The problem involves selecting a set of compatible intervals. Normally, we think of these intervals as time 
intervals (see Figure 
7-4
). Compatibility simply means that none of them should overlap, so this could be used to 
model requests for using a resource, such as a lecture hall, for certain time periods. Another example would be to 
let you be the “resource” and to let the intervals be various activities you’d like to participate in. Either way, our 
optimization task is to choose as many mutually compatible (nonoverlapping) intervals as possible. For simplicity,  
we can assume that no start or end points are identical. Handling identical values is not significantly harder.
15
Because the intervals don’t overlap, sorting by starting and finishing times is equivalent.