Chapter 14: Greedy Algorithms

Vol 2: Algorithm Forest Adventure · Station 14

---

Metadata Card

Attribute	Value
Difficulty	(Looks simple, traps everywhere)
Prerequisites	Dynamic Programming (Chapter 13), Graphs (MST)
Core Idea	Local optimum → global optimum (don't trust it too soon)
Keywords	Greedy Choice Property Activity Selection Huffman Coding MST Kruskal Prim Dijkstra

---

Your Progress

Not every problem needs DP. Sometimes, picking the best option at each step — no looking back, no regret — gives the global optimum.

---

Breakthrough · Origins

Activity Selection

def activity_selection(activities):
    activities.sort(key=lambda x: x[1])  # sort by end time
    selected = [activities[0]]
    last_end = activities[0][1]
    for start, end in activities[1:]:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    return selected

Huffman Coding

import heapq
from collections import Counter

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None
    def __lt__(self, other):
        return self.freq < other.freq

def huffman_encoding(text):
    freq = Counter(text)
    heap = [HuffmanNode(c, f) for c, f in freq.items()]
    heapq.heapify(heap)
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = HuffmanNode(None, left.freq + right.freq)
        merged.left, merged.right = left, right
        heapq.heappush(heap, merged)
    codes = {}
    def build_codes(node, code=""):
        if node:
            if node.char is not None:
                codes[node.char] = code
            build_codes(node.left, code + "0")
            build_codes(node.right, code + "1")
    build_codes(heap[0])
    return codes, "".join(codes[c] for c in text)

Kruskal's MST

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return 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):
    edges.sort()
    uf = UnionFind(n)
    mst_weight = 0
    for w, u, v in edges:
        if uf.union(u, v):
            mst_weight += w
    return mst_weight

Dijkstra's Shortest Path

import heapq

def dijkstra(graph, start):
    n = len(graph)
    dist = [float('inf')] * n
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

Greedy vs DP

Dimension	Greedy	DP
Philosophy	Look ahead, never back	Remember all possibilities
Requirement	Greedy choice property + optimal substructure	Overlapping subproblems + optimal substructure
Typical complexity	O(n log n)	O(n²)+
Correctness proof	Independent mathematical proof	Derived from state transition
Failure rate	High	Low

---

Verification Checklist

• [ ] Can explain "greedy choice property"
• [ ] Can hand-write activity selection (earliest end time)
• [ ] Can compare Kruskal vs Prim (data structures + scenarios)
• [ ] Can explain why Dijkstra fails with negative edges

---

Traveler's Notes

• Greedy looks simple, but proving it works is harder than writing a DP equation
• Production environments use greedy everywhere: routing, scheduling, encoding
• Decision tree: can you prove greedy choice property? Yes → Greedy. No → DP.

---

→ Next Stop Preview

Chapter 14+ (Bonus): Reductions and NP-Completeness — "Hard problems you should stop trying to solve optimally."