Greedy Algorithm Examples

Why This Matters

Greedy algorithms represent one of the most elegant problem-solving paradigms you'll encounter in data structures and algorithm design. The core principle is deceptively simple: make the locally optimal choice at each step and hope it leads to a globally optimal solution. But here's what you're really being tested on—understanding when greedy works and why it fails. Exam questions love to probe whether you can identify the conditions that guarantee optimality: optimal substructure and the greedy choice property.

These algorithms appear everywhere in technical interviews and form the foundation for understanding more complex approaches like dynamic programming. When you study these examples, don't just memorize the steps—ask yourself: "What's the greedy choice? Why does it work here? Would it work with different constraints?" That comparative thinking is exactly what FRQ prompts and coding interviews demand.

---

Graph Optimization Algorithms

These algorithms solve fundamental graph problems by greedily selecting the "cheapest" option at each step. The key insight is that local minimum-cost decisions accumulate into globally optimal solutions when edge weights are non-negative.

Dijkstra's Shortest Path Algorithm

• Greedy choice: always expand the unvisited node with the smallest known distance—this guarantees you've found the shortest path to that node before moving on
• Priority queue (min-heap) enables efficient selection of the next node, achieving $O((V + E) \log V)$ time complexity
• Non-negative weights required—negative edges break the algorithm because a "longer" path might become shorter later

Prim's Minimum Spanning Tree Algorithm

• Greedy choice: add the minimum-weight edge connecting the tree to a non-tree vertex—grows the MST one vertex at a time from a starting node
• Priority queue stores candidate edges, updating keys as new vertices join the tree
• Optimal for dense graphs—performs well when $E$ approaches $V^2$ due to its vertex-centric approach

Kruskal's Minimum Spanning Tree Algorithm

• Greedy choice: sort all edges by weight and add the smallest edge that doesn't create a cycle—builds the MST edge by edge globally
• Union-Find (Disjoint Set Union) data structure enables near-constant-time cycle detection with path compression and union by rank
• Optimal for sparse graphs—the $O(E \log E)$ sorting step dominates, making it efficient when $E$ is much smaller than $V^2$

---

Scheduling and Selection Problems

These problems involve choosing a maximum-size subset from competing options. The greedy insight is that finishing early leaves the most room for future selections.

Activity Selection Problem

• Greedy choice: always select the activity that finishes earliest—this maximizes remaining time for additional activities
• Sorting by finish time is essential; sorting by start time or duration does not yield optimal results
• Classic proof of greedy correctness—exchanging any selected activity with an earlier-finishing one never reduces the solution size

Interval Scheduling

• Greedy choice: select the interval with the earliest end time that doesn't overlap with previous selections—identical logic to activity selection
• Foundational problem that generalizes to weighted interval scheduling (which requires dynamic programming)
• Time complexity is $O(n \log n)$ dominated by the initial sort; selection itself is linear

Job Sequencing Problem

• Greedy choice: sort jobs by profit (descending) and schedule each in the latest available slot before its deadline—maximizes total profit
• Feasibility tracking requires checking slot availability, typically using an array or union-find for optimization
• Deadline constraints make this different from pure interval scheduling—you're maximizing value, not count

---

Knapsack and Resource Allocation

These problems optimize value subject to capacity constraints. The critical distinction is whether items are divisible—this determines if greedy works.

Fractional Knapsack Problem

• Greedy choice: select items by highest value-to-weight ratio ($\frac{v_i}{w_i}$) until capacity is exhausted
• Divisibility is key—because items can be split, taking the "densest" value always improves the solution
• Guaranteed optimal—unlike 0/1 knapsack, the greedy approach provably yields the maximum value

Coin Change Problem

• Greedy choice: always select the largest denomination that doesn't exceed the remaining amount—intuitive but dangerous
• Works only for canonical coin systems like U.S. currency (1, 5, 10, 25); fails for systems like {1, 3, 4} when making 6
• Classic counterexample for greedy limitations—dynamic programming is required for arbitrary denominations

---

Data Compression

Huffman coding demonstrates greedy algorithm design for information theory problems. The insight is that frequent symbols should have shorter codes, and building bottom-up ensures optimality.

Huffman Coding

• Greedy choice: repeatedly merge the two nodes with lowest frequency—builds an optimal prefix-free binary tree from the bottom up
• Prefix-free codes ensure no codeword is a prefix of another, enabling unambiguous decoding without delimiters
• Provably optimal for symbol-by-symbol encoding; produces minimum expected code length for given frequencies

Huffman Decoding

• Tree traversal: follow '0' for left child, '1' for right child—traverse until reaching a leaf node (character)
• Prefix property guarantees unique decoding—each bit sequence maps to exactly one character
• Linear-time decoding in the length of the encoded message; the tree structure enables streaming decode

---

Quick Reference Table

---

Self-Check Questions

1. Both Prim's and Kruskal's algorithms produce minimum spanning trees. What data structure does each rely on, and how does graph density affect which you should choose?

2. Why does the greedy approach guarantee an optimal solution for the Fractional Knapsack Problem but fail for the 0/1 Knapsack Problem?

3. Activity Selection and Job Sequencing both involve scheduling, but they sort by different criteria. What does each sort by, and why does this difference matter for optimality?

4. Compare and contrast Dijkstra's Algorithm and the greedy Coin Change approach: both make "minimum cost" choices, but one always works and one sometimes fails. Explain the key difference.

5. If you're asked to design a compression scheme and given character frequencies, walk through the greedy choice Huffman Coding makes at each step. Why does merging the two smallest frequencies first lead to an optimal prefix-free code?