Greedy Algorithms

A greedy algorithm is very similar to a dynamic programming algorithm. Both require the problem to have optimal substructure. However, whereas DP also needs overlapping subproblems, a greedy algorithm must have the opposite -- subproblems are not interdependent. Furthermore, the subproblems must be structured in such a way that making a locally optimal decision at each step in constructing the solution always leads to the globally optimal solution. This is known as the greedy-choice property. To know that a greedy algorithm will correctly solve a problem, you generally need to prove that the problem has the greedy-choice property. According to CLR, that proof can sometimes require "some cleverness."

The textbook examples are:

• Activity Scheduling
• Fractional Knapsack Problem (but not 0-1 Knapsack Problem)
  
• Huffman Codes
• Dijkstra's Algorithm