Greedy Algorithms

Greedy algorithms are a powerful and intuitive class of algorithmic strategies that solve complex problems by making a series of simple, locally optimal decisions. Their elegance lies in building a solution piece by piece, always choosing the next piece that offers the most immediate benefit. While not universally applicable, when they work, they often provide exceptionally efficient and clever solutions to problems in scheduling, compression, and network design, making them a cornerstone of algorithmic thinking.

What is a Greedy Strategy?

A greedy algorithm constructs a solution incrementally. At each decision point, it selects the choice that appears best at that moment—the locally optimal choice—without reconsidering or looking ahead to see the long-term consequences. The fundamental hope is that this sequence of locally optimal choices will lead to a globally optimal solution for the entire problem.

Consider the analogy of making change with the fewest coins. If you have standard U.S. denominations (25¢, 10¢, 5¢, 1¢) and need to give 41¢ in change, a greedy approach is to always take the largest coin that doesn’t exceed the remaining amount. You would pick a quarter (25¢), leaving 16¢. Then a dime (10¢), leaving 6¢. Then a nickel (5¢), leaving 1¢. Finally, a penny (1¢). This yields four coins total, which is indeed the optimal solution. The algorithm never reconsidered the quarter; it greedily took the biggest coin first and succeeded. This intuitive "take what you can get now" logic is the essence of the greedy paradigm.

The Two Pillars: Greedy Choice and Optimal Substructure

For a greedy algorithm to guarantee an optimal solution, the problem must possess two key properties:

Greedy Choice Property: This property states that a globally optimal solution can be arrived at by making a locally optimal (greedy) choice. In other words, we can assemble an optimal solution by always choosing the option that looks best right now, without needing to solve all possible subproblems first or backtrack. In the coin change example with standard denominations, the greedy choice of the largest possible coin is always part of some optimal solution.

Optimal Substructure: This property, shared with dynamic programming, means that an optimal solution to the problem contains within it optimal solutions to its subproblems. After making the first greedy choice, we are left with a smaller instance of the same problem. If we can solve this subproblem optimally and combine it with our first choice to get an optimal global solution, the problem has optimal substructure. After taking the quarter for 41¢, the subproblem is "make change for 16¢ optimally," which the algorithm then solves.

A problem lacking these properties will not yield to a simple greedy approach. For instance, if our coin system were [1¢, 3¢, 4¢] and we needed to make 6¢, the greedy choice (take a 4¢ coin) leads to [4¢, 1¢, 1¢] for three coins. The optimal solution, however, is [3¢, 3¢] using only two coins. Here, the greedy choice property fails; the locally optimal choice (4¢) is not part of the globally optimal solution.

Classic Applications and Algorithm Walkthroughs

Activity Selection Problem

Given a set of activities with start and finish times, the goal is to select the maximum number of non-overlapping activities. The greedy strategy is to repeatedly select the activity with the earliest finish time that doesn’t conflict with previously chosen activities.

Why it works (Informal Proof): Choosing the activity that finishes earliest leaves the maximum possible remaining time for future activities. This choice is the greedy choice that satisfies the greedy choice property. The subproblem after selecting an activity is selecting from the set of activities that start after it finishes, which is a smaller instance of the same problem (optimal substructure).

The algorithm runs in $O(n\log n)$ time, dominated by sorting the activities by finish time, followed by a single linear scan.

Huffman Coding

This is a foundational algorithm for lossless data compression. Given the frequencies of characters in a text, the goal is to build a binary prefix code (a Huffman code) that minimizes the total encoded bit length. The greedy strategy is to repeatedly merge the two trees with the smallest frequencies.

The algorithm works by building a binary tree from the bottom up:

1. Create a leaf node for each symbol, weighted by its frequency.
2. While more than one node exists in the priority queue:

a. Remove the two nodes with the smallest frequencies. b. Create a new internal node with these two as children. The frequency of this new node is the sum of the frequencies of its children. c. Insert the new node back into the priority queue.

1. The remaining node is the root of the Huffman Tree.

The codes are derived from the paths from root to leaves. This process minimizes the weighted path length because the least frequent symbols end up with the longest codes, and the most frequent get the shortest codes. The algorithm's correctness relies on the fact that merging the two smallest frequencies is always the optimal first merge (greedy choice property).

Minimum Spanning Tree (Prim's Algorithm)

For a connected, weighted graph, a Minimum Spanning Tree (MST) is a subset of edges that connects all vertices with the minimum total edge weight. Prim's algorithm is a greedy approach to find an MST.

The algorithm starts from an arbitrary vertex and grows the MST one vertex at a time:

1. Maintain two sets: vertices already in the MST ($T$) and vertices not yet in it.
2. Initialize $T$ with any starting vertex.
3. Repeatedly add the cheapest edge that connects a vertex in $T$ to a vertex outside $T$.
4. Add the new vertex to $T$ and repeat until all vertices are included.

This works because cutting the graph between $T$ and the remaining vertices partitions the edges. The cheapest edge crossing this cut (the light edge) must be part of some MST (greedy choice property). Adding it and its new vertex creates a new, smaller instance of the same problem.

Common Pitfalls

1. Assuming Greedy Always Works: The most frequent error is applying a greedy strategy to a problem that lacks the necessary properties. The coin change problem with non-standard denominations is a classic trap. Always ask: "Can I prove the greedy choice property and optimal substructure hold?" If not, you likely need dynamic programming or another technique.

1. Choosing the Wrong Greedy Criterion: Even for greedy-solvable problems, selecting the wrong local criterion leads to suboptimal solutions. For the Activity Selection problem, choosing the shortest activity or the activity that starts earliest does not yield the maximum number of activities. You must rigorously justify why your chosen criterion (earliest finish time) is the correct one.

1. Ignoring Sorting or Preprocessing Costs: Greedy algorithms often require data to be in a specific order (e.g., sorted by finish time or frequency). A common oversight is to state the algorithm's complexity as $O(n)$ while neglecting the $O(n\log n)$ sorting overhead. Accurately account for all steps in your complexity analysis.

1. Failing to Recognize Optimal Substructure: A student might correctly make the first greedy choice but then fail to properly define the resulting subproblem. The subproblem must be independent and of the same type. In the activity selection problem, after choosing an activity that finishes at time $f$, the valid subproblem only contains activities with start times $s\ge f$. Including activities that start before $f$ would violate the optimal substructure.

Summary

• Core Philosophy: A greedy algorithm builds a solution by making a sequence of locally optimal choices at each step, with the hope of finding a globally optimal solution.
• Required Properties: For a greedy algorithm to be correct and optimal, the problem must exhibit both the greedy choice property (local choices lead to global optimum) and optimal substructure (optimal solutions contain optimal sub-solutions).
• Classic Examples: Key applications include the Activity Selection problem (choose by earliest finish time), Huffman Coding for data compression (merge smallest frequencies), and finding a Minimum Spanning Tree (e.g., using Prim's algorithm to add the cheapest connecting edge).
• Inherent Limitation: Greedy algorithms are not a universal solution. They fail on problems like the general coin change problem with arbitrary denominations, where the greedy choice property does not hold.
• Critical Skill: The essential takeaway is the ability to identify when a greedy approach is applicable through careful analysis of the problem's properties, rather than blindly applying an intuitive but incorrect heuristic.