Overview

Greedy algorithms solve optimization problems by making a sequence of locally optimal choices, each of which looks best at the moment, with the hope of arriving at a globally optimal solution. Unlike dynamic programming, which considers all subproblem solutions before choosing, a greedy algorithm commits to a choice first and then solves the resulting subproblem. The chapter develops the greedy method through the activity-selection problem and Huffman coding, formalizes when greedy works via the greedy-choice property and optimal substructure, and presents a rigorous matroid-theoretic framework that unifies many greedy algorithms.

Key Concepts

• Greedy-choice property: A globally optimal solution can be assembled by making locally optimal (greedy) choices. At each decision point, the algorithm makes the choice that seems best without considering solutions to subproblems — in contrast to dynamic programming, which solves subproblems first.
• Optimal substructure: After making the greedy choice, the remaining subproblem has the property that combining its optimal solution with the greedy choice yields an optimal solution to the original problem. This property is shared with dynamic programming.
• Greedy vs. dynamic programming: DP proceeds bottom-up, solving subproblems before making choices; greedy proceeds top-down, making a choice and then solving a single remaining subproblem. Greedy algorithms are simpler and more efficient when they yield optimal solutions, but they do not always do so.
• Proof technique: Correctness of a greedy algorithm is typically proved by an exchange argument — showing that any optimal solution can be modified to include the greedy choice without worsening its quality.
• Design steps for greedy algorithms: (1) Cast the problem as one where making a choice leaves a single subproblem; (2) prove the greedy choice is always safe (part of some optimal solution); (3) demonstrate optimal substructure.
• Prefix codes: A binary code where no codeword is a prefix of another. Prefix codes can always achieve optimal data compression and are naturally represented as binary trees (leaves = characters).
• Matroids: A combinatorial structure M = (S, 𝓘) with a finite ground set S and a hereditary family of independent subsets 𝓘 satisfying the exchange property. When a matroid is weighted, the GREEDY algorithm (sort by decreasing weight, greedily add elements that maintain independence) always finds an optimal independent subset.
• Graphic matroid: M_G = (S_G, 𝓘_G) where S_G is the edge set of a graph and A ∈ 𝓘_G iff A is acyclic (a forest). Maximal independent subsets are spanning trees, connecting the greedy matroid framework to minimum spanning tree algorithms.

Algorithms and Techniques

1. Activity-Selection Problem

• Problem: Given n activities with start times s_i and finish times f_i, select a maximum-size subset of mutually compatible (non-overlapping) activities.
• Dynamic programming formulation: Define S_{ij} as activities that start after a_i finishes and finish before a_j starts. Recurrence: c[i,j] = max_{a_k ∈ S_{ij}} {c[i,k] + c[k,j] + 1}.
• Greedy insight: Always choose the activity with the earliest finish time from the remaining compatible activities. This leaves the resource available for the maximum number of future activities.
• Theorem 16.1: For any nonempty subproblem S_k, the activity a_m with the earliest finish time is included in some maximum-size compatible subset. Proved by an exchange argument: swapping a_m for the first-finishing activity in any optimal set does not reduce compatibility.
• RECURSIVE-ACTIVITY-SELECTOR(s, f, k, n): Scans activities in finish-time order starting from a_k; finds first compatible activity a_m (where s[m] ≥ f[k]) and recurses on S_m. Runs in Θ(n) assuming pre-sorted input.
• GREEDY-ACTIVITY-SELECTOR(s, f): Iterative version. Maintains the most recent selection k; for each activity m, adds it if s[m] ≥ f[k]. Also Θ(n) time with pre-sorted input.

2. Huffman Codes