Mastering Algorithms

Chapter 9: Greedy Algorithms

Greedy Strategy

Greedy algorithms make locally optimal choices at each step, hoping to find a global optimum. They work when the problem has the greedy choice property and optimal substructure.

Activity Selection

Select maximum number of non-overlapping activities. Greedy choice: always pick the activity that ends earliest.

Huffman Coding

Optimal prefix-free encoding for data compression using a greedy approach.

Minimum Spanning Tree

Kruskal's and Prim's algorithms use greedy strategies to find MST (see Chapter 6 for Union-Find used in Kruskal's).