Greedy Algorithm Examples

Why This Matters

Greedy algorithms are one of the most elegant problem-solving paradigms in algorithm design. The core principle is deceptively simple: make the locally optimal choice at each step, aiming for a globally optimal solution. But what you're really being tested on is understanding when greedy works and why it fails. Exam questions probe whether you can identify the two conditions that guarantee optimality: optimal substructure (an optimal solution contains optimal solutions to subproblems) and the greedy choice property (a locally optimal choice can lead to a globally optimal solution).

These algorithms appear constantly in technical interviews and build the foundation for understanding 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?"

---

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. Once you expand a node, you've guaranteed the shortest path to it, so you never need to revisit it.
• A priority queue (min-heap) enables efficient selection of the next node, achieving $O((V + E) \log V)$ time complexity.
• Non-negative weights are required. Negative edges break the algorithm because a path that currently looks longer could become shorter after traversing a negative edge. For graphs with negative edges (but no negative cycles), use Bellman-Ford instead.

Prim's Minimum Spanning Tree Algorithm

• Greedy choice: add the minimum-weight edge connecting the growing tree to a non-tree vertex. The MST grows one vertex at a time from a starting node.
• A priority queue stores candidate edges, updating keys as new vertices join the tree.
• Performs well on dense graphs (where $E$ approaches $V^2$) because its vertex-centric approach avoids sorting all edges upfront.

Kruskal's Minimum Spanning Tree Algorithm

• Greedy choice: sort all edges by weight and add the smallest edge that doesn't create a cycle. This builds the MST edge by edge, considering edges globally rather than growing from one vertex.
• The Union-Find (Disjoint Set Union) data structure enables near-constant-time cycle detection. With path compression and union by rank, each operation runs in $O(\alpha(n))$, where $\alpha$ is the inverse Ackermann function (effectively constant).
• Better suited for sparse graphs. The $O(E \log E)$ sorting step dominates, so when $E$ is much smaller than $V^2$, Kruskal's is efficient.

---

Scheduling and Selection Problems

These problems involve choosing a maximum-size or maximum-value 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 the remaining time available for additional activities.
• Sorting by finish time is essential. Sorting by start time or by duration does not yield optimal results. For example, a short activity in the middle of the timeline could block two non-overlapping activities.
• This problem has a classic proof of greedy correctness: you can show that swapping any selected activity for one that finishes earlier never reduces the total number of activities selected.

Interval Scheduling

• Greedy choice: select the interval with the earliest end time that doesn't overlap with previous selections. The logic is identical to activity selection.
• This is a foundational problem that generalizes to weighted interval scheduling, which requires dynamic programming because you can no longer just count intervals — you need to maximize total weight.
• Time complexity is $O(n \log n)$, dominated by the initial sort. The selection pass itself is linear.

Job Sequencing Problem

• Greedy choice: sort jobs by profit in descending order, then schedule each job in the latest available slot before its deadline. Scheduling late preserves earlier slots for other jobs.
• Feasibility tracking requires checking slot availability. A simple approach uses an array of time slots; a more optimized version uses union-find.
• Deadline constraints make this different from pure interval scheduling. Here you're maximizing total profit, not the count of scheduled items.

---

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. If the last item doesn't fully fit, take a fraction of it.
• Divisibility is the key. Because items can be split, taking the "densest" value first always improves the solution. There's no scenario where skipping a high-ratio item and taking a lower-ratio one yields more total value.
• Guaranteed optimal, unlike the 0/1 knapsack. In 0/1 knapsack, items are indivisible, so a high-ratio item might waste capacity that two smaller items could fill more profitably. That version requires dynamic programming.

Coin Change Problem

• Greedy choice: always select the largest denomination that doesn't exceed the remaining amount. This is intuitive but unreliable.
• Works only for canonical coin systems like U.S. currency (1, 5, 10, 25). For the system {1, 3, 4}, greedy picks 4 + 1 + 1 = three coins to make 6, but the optimal answer is 3 + 3 = two coins.
• This is a classic counterexample for greedy limitations. For arbitrary denominations, dynamic programming is required to guarantee the minimum number of coins.

---

Data Compression

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

Huffman Coding

The algorithm builds an optimal prefix-free binary tree:

1. Create a leaf node for each symbol, weighted by its frequency.
2. Insert all nodes into a min-heap (priority queue).
3. Extract the two nodes with the lowest frequency.
4. Create a new internal node with these two as children, with frequency equal to their sum.
5. Insert the new node back into the heap.
6. Repeat steps 3-5 until only one node remains (the root).

• Greedy choice: repeatedly merge the two lowest-frequency nodes. This ensures the least frequent symbols end up deepest in the tree (longest codes) and the most frequent symbols stay near the root (shortest codes).
• Prefix-free codes mean no codeword is a prefix of another, so decoding is unambiguous without delimiters.
• Provably optimal for symbol-by-symbol encoding. It produces the minimum expected code length for a given set of frequencies.

Huffman Decoding

• Tree traversal: start at the root, follow '0' for left child and '1' for right child until you reach a leaf node, which gives you the decoded character. Then return to the root for the next character.
• The prefix property guarantees unique decoding. Each bit sequence maps to exactly one character.
• Linear-time decoding in the length of the encoded message ($O(m)$ for $m$ bits). The tree structure enables streaming decode with no need to buffer.

---

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 Dijkstra's Algorithm and the greedy Coin Change approach: both make "minimum cost" choices, but one always works and one sometimes fails. What's the key difference?

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