Greedy Algorithms¶

Greedy algorithms embody a paradigm where locally optimal decisions—chosen at each step to maximize immediate gain—are hypothesized to yield a globally optimal solution. Pioneered in the 1950s alongside DP (with which it contrasts by forgoing exhaustive subsolutions), greediness trades recomputation for simplicity, succeeding when problems exhibit the greedy choice property (local opt is safe) and optimal substructure (global built from subs). Unlike DP's polynomial exhaustiveness, greedy risks suboptimal (e.g., 0/1 knapsack) but shines in linear time for matroids (e.g., MST). Theoretical rigor: Matroid theory formalizes when greedy works (independent sets via rank); approximation guarantees (e.g., 1/2 for set cover).

1. Core Principles¶

Greedy selects the "best" immediate option without lookahead, assuming it embeds in an optimal global path.

Greedy Choice Property: A global optimum contains a locally optimal choice (safe to take without regret).
Optimal Substructure: Subproblems' optima compose to global (shared with DP).
Mechanics: Sort/prioritize options; iteratively pick best safe (no violation).
Failure Modes: No substructure (e.g., knapsack: greedy by v/w suboptimal); proven via counterexample.

Pseudocode Template (Generic Greedy):

function greedy(problem: Instance, choice: func(opt)->item, safe: func(current, item)->bool): solution
    sort problem.options by choice descending  // Or PQ
    solution = []
    current = empty
    for opt in sorted_options:
        if safe(current, opt):
            add opt to solution
            update current
    return solution

2. Complexity Analysis¶

Greedy's efficiency stems from O(n log n) prep (sort) + O(n) selections.

Time Complexity:

Step Time Examples

Prep (Sort/PQ) O(n log n) Kruskal edges

Selections O(n) or O(n log n) PQ extracts

Total O(n log n) Most classics
- Derivation: n choices × O(log n) PQ; safe check O(1) amortized (DSU α(n)).
Space Complexity:

Variant Space Notes

Basic O(n) Options array

PQ/DSU O(n) Heap + parent
Average/Worst: Random: O(n log n); adversarial sort O(n log n).

3. Derivations and Theoretical Foundations¶

Matroid Framework: Greedy optimal on matroids (independent sets w/ exchange: |I ∪ {e}| = |I| +1 or swap). MST = graphic matroid.
Approximation Ratio: For non-optimal, ρ-approx if greedy ≥ OPT/ρ (e.g., interval scheduling =1).
Greedy vs. DP: Greedy skips table (assumes choice safe); DP verifies all.

4. Proofs of Correctness and Optimality¶

Greedy Choice Lemma: Proof by contradiction/exchange: Assume opt S includes non-greedy c (local best g not in S). Replace suboptimal in S with g (worse in S ≥ g by choice) → better or equal, contradiction.
Optimal Substructure: Induction: Base empty. Inductive: Safe choice + opt subproblem = global.
Matroid Optimality: Sort weights descending; add if extends independent → max weight basis.

5. Classic Examples¶

Activity Selection¶

The Activity Selection problem is a classic optimization challenge in greedy algorithms: Given a set of n activities, each defined by a start time s_i and finish time f_i (assuming s_i < f_i), select the maximum number of non-overlapping activities that can be scheduled without conflicts. Formally, maximize |S| where S ⊆ {1..n} and ∀ i,j ∈ S, i < j ⇒ f_i ≤ s_j. This models resource scheduling (e.g., conference rooms, machine jobs) under mutual exclusion. Greedy succeeds via earliest-finish-time choice, yielding an optimal solution in O(n log n) time—provably due to interval matroid structure. Unlike knapsack (NP-hard), activity selection is tractable, with extensions to weighted/maximization under constraints. Theoretical depth: Exchange arguments for optimality; reductions to graph coloring (intervals as paths).

1. Core Mechanics

The algorithm sorts activities by finish time, then iteratively selects the earliest-finishing compatible one, skipping conflicts. This prioritizes "early release" to accommodate more later.

State Management:
- Sorted List: Activities by f_i ascending.
- Selected Set: Accumulator of compatible activities.
- Last Finish: f of last selected (tracks compatibility: next s ≥ last_f).
Phases:
1. Sort activities by f_i (O(n log n)).
2. Select first (earliest f).
3. For each subsequent: If s_i ≥ last_f, select and update last_f = f_i.
4. Return selected (size maximal).
Key Invariant: Selected prefix is optimal for first k activities (induction basis).
Termination: End of list; |selected| = max compatible.

Pseudocode (Standard Greedy):

function activitySelection(activities: list<Activity>): list<Activity>
    if activities.empty(): return []
    // Sort by finish time
    sort activities by activity.finish ascending
    selected = [activities[0]]
    last_finish = activities[0].finish
    for i from 1 to activities.length - 1:
        if activities[i].start >= last_finish:
            selected.append(activities[i])
            last_finish = activities[i].finish
    return selected

class Activity:
    start: int, finish: int

Example: Activities: (1,4), (3,5), (0,6), (5,7), (8,9), (5,9). Sorted f: (1,4),(3,5),(0,6),(5,7),(5,9),(8,9). Select (1,4) then (5,7) then (8,9); max 3.

2. Complexity Analysis

Activity selection's efficiency: Prep dominates, scan linear.

Time Complexity:

Step Time Derivation

Sort O(n log n) Comparison sort

Scan/Select O(n) Linear pass post-sort

Total O(n log n) Dominant sort
- Details: n comparisons in scan; space O(1) aux (in-place sort).
Space Complexity:

Variant Space Notes

Basic O(1) aux In-place selected list O(n) output

Recursive O(n) stack Rare
Average/Worst: Random intervals: O(n log n); sorted input O(n) if pre-sorted.

3. Derivations and Theoretical Foundations

Interval Graph Derivation: Activities = intervals; compatibility = non-adjacent in interval graph (clique=overlaps). Max independent set = max non-overlap.
Matroid Structure: Intervals form interval matroid; greedy on f_i = max weight independent set (weight=1).
Exchange Property: If opt S, replace latest-start in S with greedy g (ends earlier, frees more).

4. Proofs of Correctness and Optimality

Greedy Choice Lemma: Let A be opt solution; g = earliest f overall. Then A' = (A - {a}) ∪ {g} optimal, where a=first in A (if g not in A).
- Proof by Exchange: If g compatible with A - {a} (g ends ≤ a start, else a ends before g contradiction), |A'|=|A|. If not, g conflicts only a (earliest f); swap preserves.
Optimal Substructure: Proof by induction on #activities.
- Base n=1: Trivial.
- Inductive: Assume for <n; greedy selects g, then opt on remaining compatible = global opt (by lemma, safe).
Maximality: Selected non-overlapping; size ≥ any (induction: Prefix opt, append opt suffix).

5. Advanced Variants

Weighted Activity Selection: Max ∑ v_i non-overlap.
- DP-Greedy Hybrid: Sort by f_i; T[i] = max value ending ≤f_i; T[i] = v_i + max T[j] where j<i, f_j ≤ s_i.
- Complexity: O(n²) naive; O(n log n) convex hull if v monotone.
- Proof: Substructure on ending time.
Parallel Activity Selection: Sort distributed; scan with prefix max compatible.
- Complexity: O(n log n / p + log n).
Constrained (Machine Scheduling): k resources; greedy per machine.

6. Pros/Cons, Optimizations, and Practical Nuances

Pros: O(n log n) exact; simple scan.
Cons: Sort mandatory; unweighted only basic.
Optimizations: Pre-sort if input sorted; union-find for dense overlaps (but overkill).
Empirical: n=10^6: ~0.1s; weighted DP for v_i.

7. Applications and Real-World Integrations

OS Scheduling: Job slots (non-preemptive).
Genomics: Overlap-free sequence assembly.
Wireless: Channel allocation (time slots).

Huffman Coding¶

Huffman coding, invented by David A. Huffman in 1952 as part of his MIT master's thesis, is a greedy, variable-length prefix code algorithm that constructs an optimal binary tree for lossless data compression. Given symbol frequencies f_i (probabilities p_i = f_i / total), it assigns shorter codes to frequent symbols, minimizing expected code length (weighted path length) while ensuring prefix-freeness (no code is prefix of another). As a greedy matroid solution on the code tree, it builds a full binary tree bottom-up by merging lowest-frequency nodes, yielding codes via left/right paths (0/1). Theoretical elegance: Kraft inequality (∑ 2^{-l_i} ≤1 for lengths l_i) equality for optimal; entropy bound (H ≤ avg length < H+1). Unlike fixed-length (e.g., ASCII 8 bits), Huffman achieves near-entropy rates (e.g., 20-30% savings on text).

1. Core Mechanics

Huffman builds a prefix code tree by treating symbols as leaves and iteratively combining lowest-frequency subtrees into internal nodes (sum freq), using a min-heap (PQ) for efficiency.

State Management:
- Frequency Nodes: Leaf nodes {symbol, freq=f_i, left/right=null}.
- Min-Heap (PQ): Priority queue of nodes by freq (min first); supports extract-min O(log n).
- Code Tree: Root internal; leaves at depths = code lengths.
- Code Assignment: Post-build: Traverse left=0/right=1, assign to leaves.
Phases:
1. Create n leaf nodes with f_i.
2. Enqueue all to PQ.
3. While >1 node: Extract two mins x,y; create parent z {freq=x.freq+y.freq, left=x, right=y}; enqueue z.
4. Root = last node; traverse for codes (dict symbol→binary string).
Key Invariant: Each merge preserves optimality for subtree (lowest combined first).
Termination: n-1 merges → single root.

Pseudocode (PQ-Based Build and Coding):

class HuffmanNode:
    freq: int, symbol: str or null, left: HuffmanNode, right: HuffmanNode

function huffmanCoding(frequencies: dict<str,int>): dict<str,str>
    n = len(frequencies)
    if n == 0: return {}
    // Build leaves
    pq = priority_queue<HuffmanNode>  // Min-heap by freq
    for symbol, freq in frequencies:
        node = HuffmanNode(freq, symbol, null, null)
        pq.insert(node)
    // Merge
    while pq.size() > 1:
        x = pq.extract_min()
        y = pq.extract_min()
        z = HuffmanNode(x.freq + y.freq, null, x, y)
        pq.insert(z)
    root = pq.extract_min()
    // Assign codes
    codes = {}
    assign_codes(root, "", codes)
    return codes

function assign_codes(node: HuffmanNode, code: str, codes: dict<str,str>):
    if node.symbol != null:  // Leaf
        codes[node.symbol] = code
        return
    if node.left != null:
        assign_codes(node.left, code + "0", codes)
    if node.right != null:
        assign_codes(node.right, code + "1", codes)

Example: Symbols A:5, B:2, C:1, D:1. PQ init: C1,D1,B2,A5. Merge C+D=2 (E2); PQ: B2,E2,A5. Merge B+E=4 (F4); PQ: F4,A5. Merge F+A=9 root. Tree: Root-A(1), left F(0)-B(10), left E(00)-C(000), right D(001). Codes: A:1 (len1), B:00 (2), C:000(3), D:001(3). Avg len ≈1.4 bits/symbol.

2. Complexity Analysis

Huffman's n-1 merges dominate via PQ, yielding near-linear for sorted input.

Time Complexity:

Step Time Derivation

Heap Build O(n) n inserts

Merges O(n log n) n-1 extract/insert pairs O(log n) each

Coding O(n) Tree traversal O(n nodes)

Total O(n log n) Dominant merges
- Details: Each merge creates internal node (2n-1 total); PQ size ≤n.
Space Complexity:

Component Space Notes

PQ/Nodes O(n) 2n-1 nodes

Codes O(n) Dict output
Average/Worst: Uniform freq: O(n log n); sorted: O(n) if linear scan.

3. Derivations and Theoretical Foundations

Expected Length Derivation: Avg L = ∑ p_i l_i, where l_i = depth(leaf i); tree minimizes ∑ f_i l_i (equiv weighted external path).
Kraft Inequality: For prefix codes, ∑ 2^{-l_i} ≤1; Huffman achieves =1 (full tree).
Entropy Bound: H(p) ≤ L < H(p)+1 (Shannon); Huffman near-optimal.
Matroid: Code trees as partition matroid; greedy merges max weight basis.

4. Proofs of Correctness and Optimality

Prefix-Free: Full binary tree; no leaf on path to leaf (codes unambiguous).
Greedy Choice Lemma: Lowest-freq pair merge safe. Proof by exchange: Assume opt T; if not merged in T, replace higher-freq pair with greedy (increases weighted path? No: Lowest sum minimizes subtree cost).
- Full Proof (Huffman 1952): Induction on n symbols. Base n=2: Trivial merge. Inductive: Opt T for n; root subtrees L/R, min freq in deepest (say L); greedy merges two mins (possibly in L/R). Exchange: If mins in different subtrees, merge them at root level (reduces depth). If same, swap with higher in other → no worse.
Optimality: Weighted path min (induction: Subtree opt by ind, merge min sum).

5. Advanced Variants

Adaptive Huffman: Online: Build tree incrementally (e.g., Vitter: sibling lists for updates). O(log n) per symbol.
Arithmetic Coding: Interval-based (continuous Huffman); better entropy but complex.
Canonical Huffman: Post-lengths, assign lexic codes; O(n) decode.
Parallel Huffman: Merge phases (butterfly); O(n / p + log n).

6. Pros/Cons, Optimizations, and Practical Nuances

Pros: Optimal prefix; O(n log n) build.
Cons: Tree decode O(n); static (needs freqs).
Optimizations: Canonical for fast encode; escape codes for adaptive.
Empirical: Text: 20-50% compression; n=256 symbols (ASCII) fine.

7. Applications and Real-World Integrations

Compression: DEFLATE (ZIP: LZ77 + Huffman).
Multimedia: JPEG (AC/DC coeffs).
Genomics: DNA symbol encoding.
Extensions: Dynamic Huffman (Splay trees).

Fractional Knapsack¶

The Fractional Knapsack problem extends the classical 0/1 Knapsack by allowing items to be taken in fractions (0 ≤ x_i ≤ 1), modeling divisible goods like liquids or commodities where partial amounts are feasible. Formally, maximize ∑ v_i x_i subject to ∑ w_i x_i ≤ W and 0 ≤ x_i ≤ 1, where v_i = value, w_i = weight of item i. Unlike 0/1's NP-hard indivisibility (requiring DP O(n W)), fractional is solvable greedily by sorting items by density ρ_i = v_i / w_i descending and filling the knapsack sequentially—taking full items until the last, which is fractional. This leverages the greedy choice property (highest density first maximizes marginal value per weight) and optimal substructure (remaining capacity subproblem identical). Theoretical ties: Linear programming relaxation of 0/1 (dual greedy); matroid on fractional independent sets. Greedy achieves exact optimality in O(n log n), contrasting 0/1's pseudo-polynomial.

1. Core Mechanics

Fractional Knapsack greedily prioritizes high-value-per-weight items, filling the knapsack to capacity with wholes and a fraction of the marginal item.

State Management:
- Sorted Items: By ρ_i = v_i / w_i descending (value density).
- Remaining Capacity: R = W init; tracks space left.
- Total Value: Accum = 0; adds v_i or fraction × v_i.
- Selected Fractions: List {i, x_i} (optional for output).
Phases:
1. Compute ρ_i for all; sort items by ρ descending (O(n log n)).
2. For each item in order: If w_i ≤ R, take full: Accum += v_i, R -= w_i, x_i=1.
3. For last fitting: If R >0 and w_i > R, take fraction x_i = R / w_i, Accum += x_i v_i.
4. Return Accum (or fractions).
Key Invariant: After k items, solution optimal for first k (highest densities packed).
Termination: R=0 or end list (unsaturated ok, but optimal).

Pseudocode (Standard Greedy):

function fractionalKnapsack(n: int, W: int, values: array<double>, weights: array<double>): double
    if W == 0: return 0.0
    // Compute densities and sort
    items = list of {i, rho = values[i]/weights[i], v=values[i], w=weights[i]}
    sort items by rho descending
    total_value = 0.0
    remaining = W
    for item in items:
        if remaining == 0: break
        if item.w <= remaining:
            // Take full
            total_value += item.v
            remaining -= item.w
        else:
            // Take fraction
            fraction = remaining / item.w
            total_value += fraction * item.v
            remaining = 0
    return total_value

Example: Items: A(v=60,w=10,ρ=6), B(100,20,5), C(120,30,4); W=50. Sorted: A(6),B(5),C(4). Take A full (10≤50, +60, R=40); B full (20≤40, +100, R=20); C fraction 20/30=2/3 (+80, R=0). Total 240 (opt).

2. Complexity Analysis

Fractional Knapsack's prep sort overshadows the O(n) fill, yielding linearithmic exact.

Time Complexity:

Step Time Derivation

Density Calc O(n) Per item

Sort O(n log n) Comparison by ρ

Filling O(n) Sequential scan

Total O(n log n) Dominant sort
- Details: Floating ρ; ties broken by index. Space O(n) items list.
Space Complexity:

Variant Space Notes

Basic O(n) Items array

In-Place O(1) aux Sort indices
Average/Worst: Uniform ρ: O(n log n); pre-sorted O(n).

3. Derivations and Theoretical Foundations

Density Greedy Derivation: Marginal value/weight ρ_i; highest first maximizes "bang for buck" until saturated.
LP Relaxation: Fractional = ILP relax of 0/1; greedy = simplex pivot on density column.
Matroid: Fractional packing = continuous matroid; greedy on ρ = max weight fractional independent.

4. Proofs of Correctness and Optimality

Greedy Choice Lemma: Highest ρ item g safe in opt S. Proof by exchange: If g not in S, replace lowest-ρ h in S with g (ρ_g > ρ_h ⇒ value increase per weight, but since fractional, adjust h fraction to fit g → ≥ value).
- Formal: Opt V = ∑ vk x_k ≤ ∑ ρ_k (∑ w_k x_k) ≤ maxρ * W; greedy achieves max_ρ fill.
Optimal Substructure: Proof by induction on items.
- Base n=1: Trivial full/fraction.
- Inductive: Assume for <n; greedy takes g (top ρ); remaining subproblem on rest/capacity → opt by ind.
Exactness: Saturates W with decreasing ρ; any other order ≤ (by rearrangement ineq: ∑ ρ_perm ≤ ∑ ρ_sorted).

5. Advanced Variants

Bounded Fractional: x_i ≤ b_i (multiples ≤b_i); greedy per item up to b_i.
- Complexity: O(n log n).
Multi-Constraint (Vector Knapsack): Multiple capacities W_k; density vector lex-sort.
- Complexity: O(n log n); approx if Pareto.
Approx for 0/1: Greedy fractional upper bound; PTAS O(n log n / ε).

6. Pros/Cons, Optimizations, and Practical Nuances

Pros: O(n log n) exact; simple fill.
Cons: Fractions require divisible model; no indivisibility.
Optimizations: Quickselect top-k if W small; stable sort ties.
Empirical: n=10^6: ~0.05s; floating precision ok (double).

7. Applications and Real-World Integrations

Portfolio: Assets (v=return, w=risk); fractional shares.
Cargo: Liquids (v=profit, w=volume).
Crypto: Continuous knapsack attacks.

Example	Choice Criterion	Safe Check	Time	Approx Ratio
Activity Sel	Earliest end	Start ≥ last end	n log n	1 (exact)
Huffman	Min freq pair	Merge	n log n	1 (opt prefix)
Fractional Knapsack	Max v/w	Capacity	n log n	1 (exact)

6. Advanced Variants¶

Greedy for Set Cover: Pick set covering most uncovered; O(log n)-approx.
- Proof: Charging: Each elem charged to log sets.
Parallel Greedy: Distributed PQ (e.g., activity: sort, scan parallel segments).
Stochastic Greedy: Prob choices for bandits.

7. Pros/Cons, Optimizations, and Practical Nuances¶

Pros: Simple linearithmic; exact when properties hold.
Cons: Suboptimal without proof; no general test.
Optimizations: PQ over sort (online greedy).
Empirical: Huffman 20-30% better than fixed codes.

8. Applications and Real-World Integrations¶

Scheduling: CPU jobs (activity).
Compression: ZIP (Huffman).
Resource: Cloud alloc (fractional).
Approx: Vertex cover (2-approx).

Step	Time	Examples
Prep (Sort/PQ)	O(n log n)	Kruskal edges
Selections	O(n) or O(n log n)	PQ extracts
Total	O(n log n)	Most classics

Step	Time	Derivation
Sort	O(n log n)	Comparison sort
Scan/Select	O(n)	Linear pass post-sort
Total	O(n log n)	Dominant sort

Variant	Space	Notes
Basic	O(1) aux	In-place selected list O(n) output
Recursive	O(n) stack	Rare

Step	Time	Derivation
Heap Build	O(n)	n inserts
Merges	O(n log n)	n-1 extract/insert pairs O(log n) each
Coding	O(n)	Tree traversal O(n nodes)
Total	O(n log n)	Dominant merges

Step	Time	Derivation
Density Calc	O(n)	Per item
Sort	O(n log n)	Comparison by ρ
Filling	O(n)	Sequential scan
Total	O(n log n)	Dominant sort