optional · CSS study notes
Greedy Algorithms
Definition
A Greedy Algorithm builds a solution step by step, at each step making the choice that looks best right now (the locally optimal choice) — without reconsidering or undoing earlier choices — in the hope that a sequence of locally optimal choices adds up to a globally optimal solution.
When Greedy Actually Works
A greedy strategy is only guaranteed to produce the true optimal solution when the problem has both:
- Greedy-choice property — a globally optimal solution can always be reached by making a single locally optimal choice at each step, without needing to look ahead or backtrack.
- Optimal substructure — an optimal solution to the whole problem contains optimal solutions to its subproblems.
If a problem lacks the greedy-choice property, a greedy algorithm still runs fast but may return a solution that is only approximately good — sometimes far from optimal. This is the key contrast with Dynamic Programming, which also relies on optimal substructure but explicitly explores/compares overlapping subproblems (via a table) rather than committing irrevocably to one choice at each step — DP costs more but guarantees optimality for a wider class of problems.
Classic Greedy Algorithms (cross-references)
- Dijkstra's Algorithm (single-source shortest path, non-negative weights) — greedily extracts the closest unvisited vertex at each step. See the Graphs page.
- Kruskal's & Prim's Algorithm (Minimum Spanning Tree) — greedily add the cheapest safe edge. See the Graphs page.
- Huffman Coding (optimal prefix-free compression) — greedily merges the two lowest-frequency nodes at every step, using a min-priority queue. See the Queues page.
- Fractional Knapsack, Activity/Interval Selection, and Coin Change (only for "canonical" coin systems like standard currency — greedy coin change is NOT optimal for arbitrary denominations, a classic exam trap).
Greedy vs Dynamic Programming vs Divide & Conquer
| Paradigm | Strategy | Revisits earlier choices? | Example |
|---|---|---|---|
| Greedy | Locally optimal choice, commit and move on | Never | Dijkstra's, Kruskal's, Huffman |
| Dynamic Programming | Solve overlapping subproblems once, combine via a table | Effectively yes (memoized) | Fibonacci (memoized), Knapsack (0/1), Longest Common Subsequence |
| Divide & Conquer | Split into independent subproblems, solve, combine | No (subproblems don't overlap) | Merge Sort, Quick Sort, Binary Search |
Exam Angle
FPSC most often tests greedy indirectly — through Dijkstra/Kruskal/Huffman questions elsewhere in this vault — but also directly, via a one-line identification MCQ. Know the one-sentence definition cold, and be ready to name 2–3 classic greedy algorithms with a one-line reason each for why they're greedy.
📌 Sample & Repeated FPSC Questions (2016–2026)
📝 Exam Practice: Identifying Greedy (MCQ)
2025, Paper I, Q18 (1 mark) — Which technique works by selecting the local optimal choice at each step?
- A. Dynamic Programming
- B. Divide and Conquer
- C. Greedy Algorithm ✓
- D. None of these
MCQ Trap: Dynamic Programming is the tempting wrong answer, since it also relies on optimal substructure — but DP explicitly reconsiders and combines overlapping subproblems via a table (memoization), whereas Greedy commits to one choice at each step and never looks back. "Local optimal choice, no reconsideration" is the phrase that pins this to Greedy specifically.
📜 Past-Paper Questions & MCQs (CSS 2016–2026)
MCQs
2025 P-I · Q10. What is the correct data structure for implementing the Huffman algorithm?
- (A) Priority queue ✅
- (B) Linked list
- (C) Binary tree
- (D) None of these
- Answer: (A) Priority queue.
- Why: Huffman coding repeatedly removes the two nodes with the lowest frequency and merges them. A priority queue (min-heap) gives the smallest item in O(log n). The result is a binary tree, but the tree is the output, and the priority queue is the working structure.
2025 P-I · Q18. Which technique works by selecting the locally optimal choice at each step?
- (A) Dynamic Programming
- (B) Divide and Conquer
- (C) Greedy Algorithm ✅
- (D) None of these
- Answer: (C) Greedy Algorithm.
- Why: a greedy algorithm always picks the best-looking option now (Kruskal's, Huffman, Dijkstra). Dynamic programming combines solutions of overlapping sub-problems, and divide and conquer splits the problem into independent parts.