Chapter 4: Greedy Algorithms

• Summary:

Sometimes greed works. An algorithm is greed if it builds up a solution in small steps, choosing a decision at each step myopically to optimize some underlying criterion. When algorithms work to give an optimal or almost optimal solution, it says something about the problem's underlying structure. Problem: how to find cases where greedy works and prove that it works. First way: greedy stays ahead. Second way: exchange argument. Uses: shortest paths in a graph, minimum spanning tree, Huffman codes.

• Insights and Questions:

• Readability: