Guided Notes
Greedy & Classic Algorithms
Greedy algorithms and when they work, the Euclidean algorithm, Huffman coding, and the traveling salesman problem.
Greedy algorithms
Slide 1 / 5A 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.