Greedy Algorithm Applications

Why This Matters

Greedy algorithms solve optimization problems by making locally optimal choices at each step, aiming for a globally optimal solution. You're being tested not just on knowing these algorithms exist, but on understanding when and why the greedy approach works. That means recognizing two key properties:

• Greedy choice property: a locally optimal choice leads to a globally optimal solution.
• Optimal substructure: an optimal solution contains optimal solutions to its subproblems.

These applications span graph algorithms, data compression, scheduling, and resource allocation. Exam questions frequently ask you to prove greedy correctness, analyze time complexity, or identify when greedy fails. Don't just memorize the algorithms. Know what structural property each problem exploits, and be ready to contrast greedy solutions with dynamic programming alternatives.

---

Graph Optimization Problems

Graph-based greedy algorithms build solutions edge-by-edge or vertex-by-vertex. The reason this works is that committing to locally best edges or paths doesn't prevent you from finding the global optimum, as long as certain conditions hold (like non-negative weights).

Minimum Spanning Tree (Kruskal's and Prim's Algorithms)

An MST connects all vertices in a weighted, undirected graph with the minimum possible total edge weight. Both Kruskal's and Prim's guarantee optimality, but they use different greedy strategies.

• Kruskal's sorts all edges by weight, then adds them one at a time, skipping any edge that would create a cycle. It uses a Union-Find data structure to check for cycles efficiently. Time complexity: $O(E \log E)$.
• Prim's grows the tree outward from a starting vertex, always adding the cheapest edge that connects a vertex already in the tree to one outside it. With a priority queue, it runs in $O(E \log V)$.

Dijkstra's Shortest Path Algorithm

Dijkstra's finds the shortest path from a single source to all other vertices, but only in graphs with non-negative edge weights.

1. Initialize the source distance to 0 and all others to infinity.
2. Extract the vertex with the smallest tentative distance from a priority queue.
3. For each neighbor, check if going through the current vertex offers a shorter path. If so, update the neighbor's distance (this is called relaxation).
4. Repeat until all vertices have been processed.

Time complexity is $O((V + E) \log V)$ with a binary heap. The algorithm fails on negative weights because once a vertex is finalized, its distance can't be revised, and a negative edge could later provide a shorter path.

---

Scheduling and Selection Problems

These problems share a common structure: given a set of tasks with constraints, select or order them optimally. The greedy insight is that sorting by the right criterion (usually finish time or deadline) enables optimal sequential selection.

Activity Selection Problem

The goal is to select the maximum number of non-overlapping activities. This is the classic greedy scheduling problem.

1. Sort activities by finish time (earliest first).
2. Select the first activity.
3. For each remaining activity, select it if its start time is at or after the finish time of the last selected activity.

Correctness is proven via an exchange argument: you can take any optimal solution and swap its first activity for the one with the earliest finish time without reducing the count. This shows the greedy choice is always safe.

Interval Scheduling

This is equivalent to activity selection. You're selecting the maximum number of non-overlapping intervals from a set defined by start and end times. Greedy by earliest finish time guarantees leaving maximum room for subsequent intervals. The overall complexity is $O(n \log n)$ due to sorting; the selection phase itself is linear.

Job Sequencing with Deadlines

Here the goal shifts: maximize total profit by scheduling jobs before their deadlines, where each job takes one time unit.

1. Sort jobs by decreasing profit.
2. For each job, assign it to the latest available time slot before its deadline.
3. If no slot is available, skip the job.

Prioritizing high-profit jobs ensures maximum total profit when slots are limited.

---

Data Compression

Greedy compression algorithms build optimal encodings by prioritizing frequent elements. The key mechanism is constructing prefix-free codes, where no codeword is a prefix of another. This guarantees unambiguous decoding.

Huffman Coding

Huffman coding assigns variable-length codes based on character frequency. More frequent characters get shorter codes, which minimizes the expected message length.

1. Create a leaf node for each character, weighted by its frequency.
2. Insert all nodes into a min-priority queue.
3. Extract the two nodes with the lowest frequencies.
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 queue.
6. Repeat steps 3-5 until one node remains. That node is the root of the Huffman tree.

Time complexity: $O(n \log n)$ where $n$ is the number of distinct characters. Huffman coding is proven optimal among all prefix-free encoding schemes for known frequency distributions.

Huffman Decoding

Decoding reconstructs the original data by traversing the Huffman tree. Read each bit: go left for 0, right for 1. When you reach a leaf, output that character and return to the root. The prefix-free property guarantees there's never ambiguity about where one codeword ends and the next begins. Decoding runs in $O(m)$ time for $m$ encoded bits, since each bit requires constant work.

---

Resource Allocation Problems

These problems involve distributing limited resources optimally. Greedy works when items can be ranked by a single efficiency metric and selected accordingly.

Fractional Knapsack Problem

You want to maximize value in a weight-limited knapsack, and items can be divided into fractions (unlike the 0/1 version).

1. Compute the value-to-weight ratio $\frac{v_i}{w_i}$ for each item.
2. Sort items by this ratio in decreasing order.
3. Add items greedily. If the next item fits entirely, take all of it. If not, take the fraction that fills the remaining capacity.

Greedy is optimal here because you can take fractions. With 0/1 knapsack, you must take an item entirely or not at all, which means a high-ratio item might waste too much capacity. That's why 0/1 knapsack requires dynamic programming.

Coin Change Problem (Canonical Coin Systems)

The goal is to find the minimum number of coins to make a target amount. The greedy approach is simple: always pick the largest denomination that fits, and repeat.

For canonical coin systems like US coins (1, 5, 10, 25), this works perfectly. But for non-canonical systems, greedy can fail. With coins {1, 3, 4} and target 6, greedy picks {4, 1, 1} (3 coins), but the optimal answer is {3, 3} (2 coins). For non-canonical systems, you need dynamic programming.

---

Mathematical Applications

Some greedy algorithms solve number-theoretic problems by iteratively selecting the largest valid component.

Egyptian Fraction

An Egyptian fraction represents any fraction as a sum of distinct unit fractions (fractions of the form $\frac{1}{n}$).

The greedy algorithm works like this: given $\frac{a}{b}$, subtract the largest unit fraction that doesn't exceed it, which is $\frac{1}{\lceil b/a \rceil}$. Then repeat on the remainder.

This greedy approach always terminates and produces a valid representation, but it's not always optimal in terms of fewest fractions. The greedy decomposition may produce more terms than the minimum possible.

---

Quick Reference Table

---

Self-Check Questions

1. Both Activity Selection and Interval Scheduling use the same greedy strategy. What sorting criterion do they share, and why does it guarantee optimality?

2. Compare Kruskal's and Prim's algorithms: what data structures does each use, and how do their greedy selection strategies differ?

3. Why does the greedy approach work for Fractional Knapsack but fail for 0/1 Knapsack? What property does the fractional version have that the 0/1 version lacks?

4. Given a coin system {1, 3, 4}, explain why greedy fails to find the minimum coins for amount 6. What algorithm would you use instead?

5. (FRQ-style) Prove that Dijkstra's algorithm fails on graphs with negative edge weights by constructing a small counterexample. Then explain what property of greedy algorithms is violated.