**__Chapter 4:  Greedy Algorithms__**

"Greed...is good.  Greed is right.  Greed works." - Michael Douglas.

An algorithm is greedy if it builds up a solution in small steps, choosing a decision at each step myopically to optimize some underlying criterion.  When a greedy algorithm succeeds there is a local decision rule that one can use to construct optimal solutions.  There are two basic methods that we will follow for proving that a greedy algorithm produces an optimal solution to a problem.  One can view the first approach as establishing that //the greedy algorithm stays ahead.//  The second approach is known as an //exchange argument.//

We will run through a few of the most well-known applications of greedy algorithms: //shortest paths in a graph, the Minimum Spanning Tree Problem,// and the construction of //Huffman codes// for performing data compression.  Also a more complex application will be considered, the //Minimum-Cost Arborescence Problem//.