Greedy Algorithms

A greedy algorithm builds a solution incrementally by always selecting the option that appears best at the current step, committing to that choice permanently (no backtracking). The hope — which must be proved, not assumed — is that a sequence of locally optimal choices produces a globally optimal solution.

Contrast this with the two neighboring paradigms:

• Divide and conquer: split the problem, recurse on independent subproblems, combine results.
• Dynamic programming: solve overlapping subproblems, store results, build up a global optimum by considering all combinations.

Greedy skips the "consider all combinations" step entirely. This makes it fast (often linear or $O(n \log n)$) but correct only under special conditions.

When does greedy work? A problem admits a correct greedy algorithm when it has two properties:

1. Greedy choice property: There exists an optimal solution that includes the greedy choice. That is, we can always extend a partial greedy solution toward a globally optimal one.
2. Optimal substructure: After making the greedy choice, the remaining problem has the same form, and an optimal solution to the remainder combines with the greedy choice to give an optimal solution to the whole.

Neither property is obvious — both must be proved for each specific problem. The standard proof technique is the exchange argument (covered next).

Counterexample instinct: Whenever you propose a greedy algorithm, immediately try to break it with a small counterexample. If you cannot find one, try to prove it. The coin-change problem is the canonical cautionary tale: greedy (always pick the largest coin) works for US denominations {1, 5, 10, 25} but fails for {1, 3, 4} where making change for 6 gives 4+1+1=3 coins greedily but 3+3=2 coins optimally.

# Coin change: greedy FAILS for arbitrary denominations
def greedy_coins(amount, coins):
    coins = sorted(coins, reverse=True)
    result = []
    for c in coins:
        while amount >= c:
            result.append(c)
            amount -= c
    return result

# With coins = {1, 3, 4}, amount = 6:
# Greedy: 4 + 1 + 1 = 3 coins
# Optimal: 3 + 3 = 2 coins
print(greedy_coins(6, [1, 3, 4]))  # [4, 1, 1]  -- WRONG

The exchange argument is the standard technique for proving that a greedy algorithm is correct. It works by showing that any optimal solution can be transformed into the greedy solution without decreasing its quality — which implies the greedy solution is also optimal.

The template (memorize this structure):

1. Suppose for contradiction (or by assumption) that there is an optimal solution $OPT$ that differs from the greedy solution $GRD$.
2. Identify the first (or any) difference: find the earliest step where $OPT$ made a different choice than $GRD$.
3. Swap: modify $OPT$ by replacing its choice at that step with the greedy choice. This creates a new solution $OPT'$.
4. Argue quality is preserved: show $OPT' \geq OPT$ in objective value (or $= OPT$ for exact optimality proofs). The key is that the swap cannot hurt.
5. Repeat: by repeating the exchange, transform $OPT$ into $GRD$ without ever decreasing quality. Therefore $GRD \geq OPT$.

Since $GRD \leq OPT$ by definition of optimality and $GRD \geq OPT$ from the exchange argument, we conclude $GRD = OPT$.

Why is this powerful? It decouples the proof from the implementation. You do not need to enumerate all possible solutions. You only need to show that one specific swap is safe — a much more tractable task.

Variants of the exchange argument:

• "Stays ahead" argument: show that at every step, the greedy solution is at least as good as any other solution (used in activity selection).
• Direct exchange: show that swapping two elements in a non-greedy solution improves or preserves it (used in scheduling to minimize weighted completion time).
• Matroid exchange: in matroid theory, the exchange argument is formalized and gives a complete characterization of when greedy is optimal (advanced; covered later).

Problem: Given $n$ activities each with a start time $s_i$ and finish time $f_i$, select the maximum number of non-overlapping activities (activities $i$ and $j$ are compatible if $f_i \leq s_j$ or $f_j \leq s_i$).

The greedy rule: Sort activities by finish time. Repeatedly select the next activity with the earliest finish time that is compatible with all previously selected activities.

This rule has a beautiful intuition: finishing early leaves the most "room" for future activities. An activity that finishes late is selfish — it hogs the resource longer.

Proof via the "stays ahead" argument:

Let $GRD = {a_1, a_2, \ldots, a_k}$ be the greedy solution (sorted by finish time) and $OPT = {b_1, b_2, \ldots, b_m}$ be any optimal solution (also sorted by finish time). We claim $k = m$.

Claim (Stays Ahead): For each $r \leq \min(k, m)$, the finish time of $GRD$'s $r$-th activity is $\leq$ the finish time of $OPT$'s $r$-th activity: $f(a_r) \leq f(b_r)$.

Proof by induction:

• Base: $r=1$. Greedy picks the globally earliest-finishing activity, so $f(a_1) \leq f(b_1)$. ✓
• Step: Assume $f(a_r) \leq f(b_r)$. Since $b_{r+1}$ is compatible with $b_r$ (in OPT), we have $s(b_{r+1}) \geq f(b_r) \geq f(a_r)$, so $b_{r+1}$ is also compatible with $a_r$ in the greedy solution. Greedy could have selected $b_{r+1}$ but instead chose $a_{r+1}$ which finishes at least as early, so $f(a_{r+1}) \leq f(b_{r+1})$. ✓

Conclusion: Suppose $k < m$. Then OPT has an $(k+1)$-th activity $b_{k+1}$ with $s(b_{k+1}) \geq f(b_k) \geq f(a_k)$, so $b_{k+1}$ is compatible with the greedy solution. But greedy stopped at $k$ activities — contradiction (greedy would have selected $b_{k+1}$). Therefore $k \geq m$, and since $OPT$ is optimal $k = m$.

Complexity: $O(n \log n)$ for sorting, then $O(n)$ for the scan — total $O(n \log n)$.

def activity_selection(activities):
    """
    activities: list of (start, finish) tuples
    Returns: list of selected (start, finish) tuples
    """
    # Sort by finish time -- the greedy key
    sorted_acts = sorted(activities, key=lambda x: x[1])
    
    selected = [sorted_acts[0]]          # Always take the first
    last_finish = sorted_acts[0][1]
    
    for s, f in sorted_acts[1:]:
        if s >= last_finish:             # Compatible with last selected
            selected.append((s, f))
            last_finish = f
    
    return selected

# Example from CLRS
acts = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
print(activity_selection(acts))
# => [(1,4), (5,7), (8,11), (12,16)]  -- 4 activities, optimal

Problem: Given an alphabet of $n$ symbols with known frequencies $f_1, f_2, \ldots, f_n$, construct a binary prefix-free code (no codeword is a prefix of another) that minimizes the expected bits per symbol: $\sum_{i} f_i \cdot d_i$, where $d_i$ is the depth (bit length) of symbol $i$'s codeword.

Prefix-free codes correspond to binary trees where symbols are leaves. The cost is the weighted external path length.

Huffman's greedy rule: Repeatedly merge the two symbols (or subtrees) with the smallest frequency into a new node whose frequency is their sum. This is a bottom-up tree construction.

Intuition: Symbols we see most often should have the shortest codes. To build such a tree, the two rarest symbols should share the deepest level — they will be siblings at the bottom. After merging them, we have a new problem of size $n-1$ where the merged node acts as a single symbol.

Proof sketch (exchange argument):

Lemma 1: In an optimal tree, the two symbols with the smallest frequencies have the maximum depth, and they are siblings.

Proof: Suppose $x$ and $y$ are the two rarest symbols. If there is an optimal tree where they are not at the maximum depth, swap them with the deepest pair $(a, b)$. Since $f_x \leq f_a$ and $f_y \leq f_b$, and we increased $d_x, d_y$ and decreased $d_a, d_b$, the cost changes by: $$\Delta = (f_x - f_a)(d_{x'} - d_{a'}) + (f_y - f_b)(d_{y'} - d_{b'}) \leq 0$$ So the swap does not increase cost. Hence an optimal tree exists where $x, y$ are at maximum depth as siblings.

Lemma 2 (optimal substructure): Let $T^$ be an optimal tree for symbols ${x, y, z_1, \ldots, z_{n-2}}$ where $x$ and $y$ are merged into $z$ with $f_z = f_x + f_y$. Then replacing $z$ with the subtree for $x, y$ in $T^$ gives an optimal tree for the original $n$ symbols.

These two lemmas together justify Huffman's algorithm by induction.

Complexity: Using a min-heap, each of the $n-1$ merge steps costs $O(\log n)$, giving $O(n \log n)$ total. This is optimal for comparison-based construction.

Real-world note: Huffman coding is used in DEFLATE (zlib/gzip), JPEG (for AC coefficients), MP3, and many other compression standards. It is optimal among all prefix-free codes for a known symbol distribution.

import heapq
from collections import defaultdict

def huffman(frequencies):
    """
    frequencies: dict {symbol: freq}
    Returns: dict {symbol: binary_codeword_string}
    """
    # Build min-heap of (freq, id, node)
    # node is either a symbol or ('internal', left, right)
    heap = []
    for i, (sym, freq) in enumerate(frequencies.items()):
        heapq.heappush(heap, (freq, i, sym))
    
    counter = len(frequencies)
    while len(heap) > 1:
        f1, _, left  = heapq.heappop(heap)
        f2, _, right = heapq.heappop(heap)
        heapq.heappush(heap, (f1 + f2, counter, ('node', left, right)))
        counter += 1
    
    _, _, root = heap[0]
    
    # Walk tree to assign codes
    codes = {}
    def walk(node, prefix):
        if isinstance(node, str):        # leaf
            codes[node] = prefix or '0'  # single-symbol edge case
        else:
            _, left, right = node
            walk(left,  prefix + '0')
            walk(right, prefix + '1')
    walk(root, '')
    return codes

freqs = {'a': 45, 'b': 13, 'c': 12, 'd': 16, 'e': 9, 'f': 5}
codes = huffman(freqs)
for sym, code in sorted(codes.items()):
    print(f"{sym}: {code}")
# a: 0  (most frequent -> shortest)
# b: 101
# c: 100
# d: 111
# e: 1101
# f: 1100

Problem: Given a connected undirected weighted graph $G = (V, E, w)$, find a spanning tree $T \subseteq E$ that connects all vertices and minimizes $\sum_{e \in T} w(e)$.

MSTs arise in network design (cheapest way to connect cities), clustering (remove the $k-1$ heaviest MST edges to get $k$ clusters), and as subroutines in approximation algorithms.

Kruskal's algorithm: Sort all edges by weight. Process edges in non-decreasing order; include an edge if and only if it does not create a cycle (equivalently, it connects two different components). Stop when $|V|-1$ edges are included.

Implementation: Use a Union-Find (Disjoint Set Union) data structure to efficiently detect cycles. Each edge $(u, v)$ is safe to add iff $\text{find}(u) \neq \text{find}(v)$.

Proof of correctness — the Cut Property:

A cut $(S, V \setminus S)$ partitions $V$ into two non-empty sets. The cut property states:

For any cut $(S, V \setminus S)$, the minimum-weight edge crossing the cut is in some MST. (With distinct weights, it is in every MST.)

When Kruskal's adds edge $e = (u, v)$, the two components containing $u$ and $v$ form a natural cut. Edge $e$ is the minimum-weight edge crossing this cut at the time of consideration (since we process edges in sorted order and cycle edges are skipped). By the cut property, $e$ belongs to some MST.

By induction, each edge Kruskal's adds is in some MST, and after $|V|-1$ additions we have a spanning tree that is a superset of no other spanning tree — hence it is an MST.

Complexity: $O(E \log E)$ for sorting (dominant), $O(E \cdot \alpha(V))$ for Union-Find operations where $\alpha$ is the inverse Ackermann function (essentially constant). Total: $O(E \log E) = O(E \log V)$.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank   = [0] * n
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1
        return True

def kruskal(n, edges):
    """
    n: number of vertices (0..n-1)
    edges: list of (weight, u, v)
    Returns: (MST weight, list of MST edges)
    """
    edges = sorted(edges)            # sort by weight
    uf = UnionFind(n)
    mst_weight, mst_edges = 0, []
    for w, u, v in edges:
        if uf.union(u, v):           # safe edge -- no cycle
            mst_weight += w
            mst_edges.append((u, v, w))
            if len(mst_edges) == n - 1:
                break                # MST complete
    return mst_weight, mst_edges

# Example: 4 vertices
edges = [(1,0,1),(4,0,2),(3,1,2),(2,1,3),(5,2,3)]
print(kruskal(4, edges))  # weight=6: edges (0,1,1),(1,3,2),(1,2,3)

Prim's algorithm is the second major MST algorithm. While Kruskal's thinks globally (sort all edges, pick greedily), Prim's grows the MST from a single starting vertex, at each step adding the cheapest edge that crosses the frontier between the current tree and the rest of the graph.

Algorithm:

1. Initialize: put all vertices in a priority queue keyed by key[v] = ∞. Set key[start] = 0.
2. Repeat until queue is empty: a. Extract the vertex $u$ with minimum key. b. For each neighbor $v$ of $u$: if $v$ is still in the queue and $w(u,v) < \text{key}[v]$, update $\text{key}[v] = w(u,v)$ and record $\text{parent}[v] = u$.
3. The MST is ${(\text{parent}[v], v) : v \neq \text{start}}$.

Correctness: Same cut property as Kruskal's. At each step, Prim's adds the minimum-weight edge crossing the cut $(T, V \setminus T)$ where $T$ is the current tree. This edge is guaranteed to be in some MST.

Complexity:

• With a binary heap: $O((V + E) \log V)$.
• With a Fibonacci heap: $O(E + V \log V)$, which is better for dense graphs.

Kruskal vs. Prim:

• Kruskal's is better for sparse graphs ($E \approx V$): $O(E \log E)$.
• Prim's with a Fibonacci heap is better for dense graphs ($E \approx V^2$): $O(V^2)$ vs. $O(V^2 \log V)$ for Kruskal's on a dense graph.
• In practice, both are widely used; Kruskal's is simpler to implement correctly.

Deep connection: Both Kruskal's and Prim's are instantiations of a general greedy MST framework: maintain a set of "safe" edges (a forest growing into an MST), and at each step add the minimum-weight edge that does not create a cycle and crosses some cut of the current forest. The cut property is the single unifying theorem.

import heapq

def prim(n, adj):
    """
    n: number of vertices
    adj: adjacency list adj[u] = [(w, v), ...]
    Returns: MST total weight
    """
    visited = [False] * n
    # (weight, vertex)
    heap = [(0, 0)]   # start from vertex 0, cost 0
    total = 0

    while heap:
        w, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        total += w
        for edge_w, v in adj[u]:
            if not visited[v]:
                heapq.heappush(heap, (edge_w, v))

    return total

# Same 4-vertex example
adj = [
    [(1,1),(4,2)],     # vertex 0
    [(1,0),(3,2),(2,3)],  # vertex 1
    [(4,0),(3,1),(5,3)],  # vertex 2
    [(2,1),(5,2)],     # vertex 3
]
print(prim(4, adj))  # 6

Activity selection is the simplest interval scheduling problem. Several variants reveal how greedy rules must be carefully chosen:

1. Interval partitioning (minimum number of rooms/machines): Schedule all $n$ lectures (each with a start and end time) using the fewest conference rooms so no two lectures in the same room overlap.

Greedy rule: Sort lectures by start time. Assign each lecture to any available room (one whose last lecture has finished). If no room is free, open a new room.

Key insight: The minimum number of rooms needed equals the maximum number of lectures simultaneously in progress (depth of the interval set). Greedy achieves this bound: whenever it opens a new room, it is because all existing rooms are in use simultaneously, proving optimality.

2. Minimizing lateness (single machine, deadlines): Each job $j$ has processing time $t_j$ and deadline $d_j$. Schedule all jobs on a single machine to minimize the maximum lateness $L_{\max} = \max_j (C_j - d_j)$ where $C_j$ is the completion time.

Greedy rule: Earliest Deadline First (EDF) — schedule jobs in non-decreasing order of deadline.

Proof via exchange argument: An "inversion" occurs when job $i$ with later deadline is scheduled before job $j$ with earlier deadline. Swapping $i$ and $j$ (adjacent) never increases $L_{\max}$: job $i$'s lateness may increase, but since $d_i \geq d_j$, the new lateness of $i$ is at most the old lateness of $j$. By bubble sort logic, any sequence without inversions is EDF, and EDF is optimal.

3. Minimizing total weighted completion time: Job $j$ has weight $w_j$ (importance) and processing time $p_j$. Minimize $\sum_j w_j C_j$.

Greedy rule: Schedule in decreasing order of $w_j / p_j$ (the ratio of importance to processing time).

This is the "Smith's rule" — provably optimal by an exchange argument on adjacent jobs.

from functools import cmp_to_key

def earliest_deadline_first(jobs):
    """jobs: list of (processing_time, deadline)"""
    schedule = sorted(jobs, key=lambda j: j[1])  # sort by deadline
    time, max_lateness = 0, float('-inf')
    for p, d in schedule:
        time += p
        lateness = time - d
        max_lateness = max(max_lateness, lateness)
    return max_lateness

def smiths_rule(jobs):
    """jobs: list of (weight, processing_time)
    Minimize sum of weighted completion times."""
    # Sort by decreasing w/p ratio
    schedule = sorted(jobs, key=lambda j: -j[0]/j[1])
    time, total = 0, 0
    for w, p in schedule:
        time += p
        total += w * time
    return total

# EDF example
print(earliest_deadline_first([(3,6),(2,8),(1,9),(4,15)]))  # max lateness
# Smith's rule example  
print(smiths_rule([(3,1),(2,3),(5,2)]))  # weighted completion time

Why does greedy work for activity selection, Huffman, and MST but fail for coin change and shortest paths? The answer lies in matroid theory, one of the most beautiful structures in combinatorial optimization.

Definition: A matroid $M = (E, \mathcal{I})$ consists of a finite ground set $E$ and a collection $\mathcal{I}$ of independent sets (subsets of $E$) satisfying:

1. Emptiness: $\emptyset \in \mathcal{I}$.
2. Hereditary: If $A \in \mathcal{I}$ and $B \subseteq A$, then $B \in \mathcal{I}$.
3. Exchange: If $A, B \in \mathcal{I}$ and $|A| < |B|$, then there exists $x \in B \setminus A$ such that $A \cup {x} \in \mathcal{I}$.

The fundamental theorem of matroids: The greedy algorithm — repeatedly add the maximum-weight element that keeps the set independent — correctly finds the maximum-weight basis (maximal independent set) of any matroid.

Key examples:

• Graphic matroid: $E$ = edges of a graph, $\mathcal{I}$ = forests (acyclic subsets). Greedy on this matroid = Kruskal's MST algorithm. ✓
• Partition matroid: $E$ = activities, $\mathcal{I}$ = sets of non-overlapping activities. Greedy = activity selection. ✓
• Linear matroid (vector matroid): $E$ = set of vectors over a field, $\mathcal{I}$ = linearly independent subsets.

Why coin change is NOT a matroid: The feasible subsets of coins (those summing to $\leq n$) do not satisfy the exchange property in general, so greedy fails.

Matroid intersection (advanced): Some problems require finding a maximum independent set in the intersection of two matroids (e.g., bipartite matching). These cannot generally be solved by simple greedy and require polynomial-time matroid intersection algorithms.

Matroid theory, developed by Whitney (1935) and Edmonds (1970), tells us exactly when greedy works — not just for the examples in this course, but for any combinatorial optimization problem.

Recognizing when greedy fails is as important as knowing when it succeeds. Here are the main failure modes and their canonical examples:

1. No greedy choice property: Coin change (arbitrary denominations) Coins ${1, 3, 4}$, amount $= 6$. Greedy gives $4+1+1 = 3$ coins. Optimal: $3+3 = 2$ coins. The local choice of picking the largest coin is not part of any optimal solution for this instance.

2. Fractional vs. integer: 0/1 Knapsack For the fractional knapsack (you can take fractions of items), greedy by value/weight ratio is optimal. For the 0/1 knapsack (whole items only), greedy fails. The feasible sets do not form a matroid. This is an NP-hard problem.

3. Graph shortest paths with negative edges: Dijkstra's failure Dijkstra's algorithm is greedy (always relax the nearest unvisited vertex). It is correct for non-negative edge weights because the greedy choice property holds: the nearest unvisited vertex cannot have its distance improved later. With negative edges, a "longer" path found later might actually be shorter — destroying the greedy choice property. Use Bellman-Ford ($O(VE)$) instead.

4. Global structure not captured by local view: Travelling Salesman Problem Greedy nearest-neighbor heuristic for TSP gives poor approximations in the worst case (can be $O(\log n)$ times optimal). TSP is NP-hard; no polynomial greedy algorithm gives an optimal solution unless P=NP.

5. The "almost greedy" trap: Weighted interval scheduling For unweighted interval scheduling (maximize count), greedy by finish time is optimal. Add weights (maximize total weight of selected intervals), and greedy by finish time fails immediately. You need dynamic programming.

Summary heuristic for when to be skeptical of greedy:

• The problem has interacting constraints (knapsack, TSP).
• Weights or values complicate a structure that is clean without them.
• You cannot find a natural "cut property" or "stays ahead" argument.
• Small counterexamples exist (always try $n = 3$ or $n = 4$).

# Fractional knapsack: GREEDY WORKS
def fractional_knapsack(capacity, items):
    # items: list of (value, weight)
    items = sorted(items, key=lambda x: -x[0]/x[1])  # by value/weight desc
    total, remaining = 0, capacity
    for v, w in items:
        if remaining <= 0: break
        take = min(w, remaining)
        total += take * (v / w)
        remaining -= take
    return total

# 0/1 knapsack: GREEDY FAILS (needs DP)
def zero_one_knapsack_dp(capacity, items):
    n = len(items)
    dp = [[0]*(capacity+1) for _ in range(n+1)]
    for i, (v, w) in enumerate(items, 1):
        for c in range(capacity+1):
            dp[i][c] = dp[i-1][c]
            if w <= c:
                dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
    return dp[n][capacity]

items = [(60,10),(100,20),(120,30)]
cap = 50
print(f"Fractional: {fractional_knapsack(cap, items):.1f}")  # 240.0
print(f"0/1 DP:     {zero_one_knapsack_dp(cap, items)}")       # 220