15.1 Greedy Algorithm Design

Greedy Algorithm Design

Greedy algorithms solve optimization problems by making the best-looking choice at each step, hoping those local decisions add up to a globally optimal solution. They're simple to implement and often efficient, but the tricky part is knowing when they actually work and when they'll lead you astray.

Principles of Greedy Algorithms

Two properties must hold for a greedy approach to produce an optimal solution:

Greedy choice property means that picking the locally optimal choice at each stage can lead to a globally optimal solution. You never need to reconsider a choice once it's made. Dijkstra's algorithm demonstrates this: at each step, it commits to the nearest unvisited vertex and never revisits that decision.

Optimal substructure means the optimal solution to the whole problem contains optimal solutions to its subproblems. For shortest paths, this is intuitive: if the shortest path from A to C goes through B, then the A-to-B portion must itself be the shortest path from A to B.

A greedy algorithm builds its solution incrementally, one choice at a time, and never backtracks. This is both its strength (efficiency) and its weakness (it can fail on problems that lack the two properties above). The Traveling Salesman Problem is a classic example where always visiting the nearest unvisited city often produces a suboptimal tour.

Common problems where greedy does work:

• Minimum Spanning Tree (Prim's, Kruskal's)
• Huffman Coding (optimal prefix-free codes)
• Dijkstra's Algorithm (single-source shortest paths with non-negative weights)

Greedy Techniques for Optimization

Designing a greedy algorithm follows a consistent process:

1. Define the objective function. What are you maximizing or minimizing? (e.g., minimize total edge weight, maximize total profit)

2. Identify the greedy choice. At each step, which locally optimal decision is feasible and moves you toward the objective? In Dijkstra's, that's selecting the unvisited vertex with the smallest tentative distance.

3. Prove the greedy choice is safe. This is the step most students skip, and it's the most important. You need to show that committing to the greedy choice at each step doesn't prevent you from reaching the global optimum. The two standard proof techniques are:

   • Exchange argument: Assume an optimal solution that differs from the greedy choice, then show you can "swap in" the greedy choice without making the solution worse.
   • Proof by contradiction: Assume the greedy choice leads to a suboptimal solution and derive a contradiction.

4. Build the algorithm. Repeatedly make the greedy choice and update the problem state until a complete solution is formed (e.g., Prim's algorithm adds the cheapest crossing edge until the spanning tree is complete).

5. Verify optimality. If you can't prove optimality, look for a counterexample. Finding one means greedy won't work for that problem, and you'll need a different strategy (often dynamic programming).

Analysis of Greedy Algorithms

Time Complexity

To analyze a greedy algorithm's running time:

1. Count the number of iterations the main loop performs.
2. Determine the cost of each iteration (selecting the greedy choice, updating state).
3. Combine them using Big-O notation.

For example, Dijkstra's algorithm with a binary heap priority queue:

• The main loop runs $V$ times (once per vertex).
• Each extraction from the priority queue costs $O(\log V)$.
• Each edge relaxation may trigger a decrease-key operation, also $O(\log V)$.
• Overall: $O((V + E) \log V)$.

With a Fibonacci heap, the decrease-key drops to amortized $O(1)$, giving $O(V \log V + E)$.

Optimality Analysis

If the greedy approach is correct, prove it using an exchange argument or contradiction (as described above). If it's not correct, a single counterexample is enough to show failure. For the Traveling Salesman Problem, you can construct small graphs where the nearest-neighbor heuristic produces a tour significantly longer than the optimal one.

Implementation of Greedy Algorithms

Huffman Coding

Huffman coding assigns variable-length binary codes to characters so that more frequent characters get shorter codes. This minimizes the total number of bits needed to encode a message.

1. Create a leaf node for each character, weighted by its frequency.

2. Insert all nodes into a min-priority queue.

3. While more than one node remains in the queue:

   • Extract the two nodes with the lowest frequencies.
   • Create a new internal node with these two as children, with frequency equal to their sum.
   • Insert the new node back into the queue.

4. The remaining node is the root of the Huffman tree.

5. Assign codes by traversing the tree: go left = append 0, go right = append 1.

For frequencies {a: 45, b: 13, c: 12, d: 16, e: 9, f: 5}, the resulting codes might be something like a: 0, b: 101, c: 100, d: 111, e: 1101, f: 1100. Characters with higher frequencies (like a) get shorter codes.

The time complexity is $O(n \log n)$ where $n$ is the number of distinct characters, since each insertion and extraction from the priority queue costs $O(\log n)$.

Dijkstra's Shortest Path Algorithm

Dijkstra's finds the shortest path from a single source vertex to all other vertices in a graph with non-negative edge weights.

1. Initialize the distance to the source as 0 and all other distances as $\infty$. Mark all vertices as unvisited.
2. Set the source as the current vertex.
3. For the current vertex, examine each unvisited neighbor. Calculate the tentative distance through the current vertex. If it's less than the neighbor's recorded distance, update it.
4. After checking all neighbors, mark the current vertex as visited (it won't be reconsidered).
5. Select the unvisited vertex with the smallest tentative distance as the next current vertex.
6. Repeat steps 3-5 until all vertices are visited or the destination is reached.

Example: In a graph where the shortest path from vertex 0 to vertex 4 is 0 → 2 → 3 → 4 with total distance 9, Dijkstra's discovers this by progressively locking in the shortest distances to vertices 2, then 3, then 4.