A greedy algorithm constructs a solution one piece at a time, and at each step it commits to the option that appears best right now, never reconsidering that decision later. The appeal is simplicity and speed: there is no search over alternatives, just a sequence of locally optimal choices.
The catch is that locally best does not always mean globally best. For some problems the greedy choice provably leads to an optimal overall solution, and for others it does not. Establishing that a greedy strategy is correct usually requires showing a specific structural property of the problem, such as a greedy-choice property and an underlying matroid structure.
Greedy methods succeed for several important problems. Building a minimum spanning tree by repeatedly adding the cheapest safe edge, as in the classic algorithms covered in the MIT 6.046J “Design and Analysis of Algorithms” lecture notes, is greedy and optimal. Dijkstra’s shortest-path algorithm is greedy, always finalizing the nearest unprocessed vertex, and Huffman coding builds an optimal prefix code by repeatedly merging the two least frequent symbols.
Greedy algorithms are often contrasted with dynamic programming. Both build solutions from subproblems, but a greedy algorithm makes one irrevocable choice at each step, while dynamic programming explores and combines the answers to overlapping subproblems. When the greedy choice is valid it is typically faster and simpler than the dynamic programming alternative.