Greedy & Classic Algorithms

A greedy algorithm makes the best-looking choice at each step and never reconsiders it. It's simple and fast — and correct only for some problems.

Greedy works when choosing the local best always leads to the global best: • Dijkstra's, Prim's, and Kruskal's algorithms. • Activity selection — always pick the event that ends earliest. • Making change with standard coins.

It fails elsewhere: for 0/1 knapsack or unusual coin sets, the best local choice can lead to a worse overall answer — use dynamic programming instead.