1. Introduction
A greedy algorithm solves an optimization problem by making a sequence of choices, where at every step it takes the option that looks best right now — the locally optimal choice — and never reconsiders it. The hope is that these local best choices add up to a globally optimal solution.
This topic is a favourite of BCS, Bank IT, and IT-officer written and viva exams because it is compact yet conceptually rich. Questions test whether you can (a) state the greedy strategy, (b) know the classic problems (activity selection, fractional knapsack, Huffman coding, Kruskal, Prim, Dijkstra, coin change), (c) tell when greedy works versus when it fails (0/1 knapsack!), and (d) compute time complexities. Mastering greedy also sets you up for Dynamic Programming, which is its frequent contrast.
2. Learning objectives
- Define a greedy algorithm and the greedy-choice property and optimal substructure.
- Distinguish greedy from dynamic programming and brute force.
- Solve the Activity Selection, Fractional Knapsack, and Huffman Coding problems step by step.
- Know why greedy fails for the 0/1 Knapsack and general coin change.
- Recall which classic algorithms are greedy (Kruskal, Prim, Dijkstra) and their complexities.
- Analyse the running time of a greedy algorithm.
- Avoid the common exam traps.