← Algorithm Design learning pathAlgorithm Design · Module 3 of 10
Greedy algorithms
Make the locally best choice at each step.
📖 Key ideas
- Greedy algorithms pick the best immediate option.
- Work when the problem has greedy-choice property and optimal substructure.
- Examples: activity selection, Huffman coding, Kruskal, Prim, Dijkstra.
- Fractional knapsack is greedy; 0/1 knapsack is not.
- Prove correctness with exchange arguments.
💡 Real-life example: Greedy is eating the best dish at each buffet counter; it works only if each local best leads to the best meal.
Greedy choiceBest local decision
Optimal substructureOptimal solution built from optimal subproblems
Huffman codingGreedy compression
Activity selectionPick max non-overlapping intervals