Greedy Algorithms

🎯 Learning Objectives

• Design greedy algorithms for scheduling and resource allocation
• Prove greedy optimality using exchange arguments
• Analyze the stable matching problem and Gale-Shapley algorithm
• Recognize when greedy works and when it doesn't

1. Introduction to Greedy

1.1 Intuition

1.2 When Greedy Works

2. Interval Scheduling

2.1 Problem

1. Sort jobs by finish time
2. Pick first job, skip overlapping jobs
3. Repeat until no jobs remain

2.2 Tracing Table

• Let greedy = $\{i_1, i_2, ..., i_k\}$, optimal = $\{j_1, j_2, ..., j_m\}$
• Show $f(i_1) \leq f(j_1)$ (greedy picks earliest finish)
• Replace $j_1$ with $i_1$ in optimal (still feasible, same count)
• By induction, $k = m$ (greedy matches optimal)

3. Storing Files on Tape

3.1 Problem

3.2 Tracing Table

3.3 Optimality Proof (Exchange)

• Current cost contribution: $(L + l_x) + (L + l_x + l_y) = 2L + 2l_x + l_y$
• After swap: $(L + l_y) + (L + l_y + l_x) = 2L + 2l_y + l_x$
• Difference: $(2L + 2l_x + l_y) - (2L + 2l_y + l_x) = l_x - l_y > 0$ Swapping reduces total cost → shortest-first is optimal.

4. Stable Matching (Gale-Shapley)

4.1 Problem

4.2 Algorithm

python
Run Inline
def gale_shapley(men_prefs, women_prefs):
    # Men propose, women decide
    free_men = list(men_prefs.keys())
    matches = {}  # woman → man
    proposals = {man: 0 for man in men_prefs}
    while free_men:
        man = free_men.pop(0)
        # Next woman on his list
        woman = men_prefs[man][proposals[man]]
        proposals[man] += 1
        if woman not in matches:
            matches[woman] = man
        else:
            current = matches[woman]
            # Woman prefers new man?
            if women_prefs[woman].index(man) < women_prefs[woman].index(current):
                matches[woman] = man
                free_men.append(current)  # current man is now free
            else:
                free_men.append(man)  # man rejected
    return {man: woman for woman, man in matches.items()}

4.3 Properties

5. When Greedy Fails

6. Common Pitfalls

Pitfall 1: Assuming Greedy Always Works

Pitfall 2: Wrong Greedy Choice

Pitfall 3: Ignoring Tie-breaking in Stable Matching

7. Key Concepts Reference

8. 📝 Practice Questions

Q1: Prove that earliest-finish-first is optimal for interval scheduling.

Answer: Exchange argument: Let greedy = {i₁,...,iₖ} and optimal = {j₁,...,jₘ}. Show f(i₁) ≤ f(j₁) since greedy picks earliest finish. Create new optimal = {i₁, j₂,...,jₘ} which is feasible because i₁ finishes before j₁ starts (since f(i₁) ≤ f(j₁) ≤ s(j₂)). By induction, |greedy| ≥ |optimal|. Since optimal has max possible size, |greedy| = |optimal| and greedy is optimal. Q2: Show that the closest-pair greedy fails for TSP.

Answer: Consider 4 cities at positions (0,0), (10,0), (10,10), (0,10). Starting at (0,0), closest is (10,0). From (10,0), closest is (10,10). From (10,10), must go to (0,10). Return to (0,0). Tour: (0,0)→(10,0)→(10,10)→(0,10)→(0,0). Total = 10+10+10+10 = 40. Optimal is (0,0)→(10,0)→(10,10)→(0,10)→(0,0) = 40 (same here, but in general nearest-neighbor can be much worse than optimal).

Better counterexample: Cities at (0,0), (1,0), (2,0), (100,0), (100,1), (0,1). Nearest-neighbor from (0,0) goes along to (100,0), then must backtrack — producing terrible tour. Q3: Prove that Gale-Shapley produces a man-optimal stable matching.

Answer: Proof by contradiction: Suppose some man m is rejected by a valid partner w in some execution. Consider the first time this happens. m proposes to w and is rejected because w prefers m' (who also proposed). Since m hasn't been rejected by any valid partner before, m' is also a valid partner for w (otherwise w would not be matched to m' in any stable matching). But then (m,w) would be a blocking pair for the matching where m' is matched to w and m is matched to someone else — contradiction. Therefore no man is rejected by a valid partner, so each man gets his best valid partner. Q4: Files of lengths [3, 7, 2, 5] need to be stored on tape. What's the optimal order?

Answer: Sort by length ascending: [2, 3, 5, 7]. Access times: 2, 2+3=5, 2+3+5=10, 2+3+5+7=17. Total = 2+5+10+17 = 34. Any other order (e.g., [7,5,3,2]: 7+12+15+17=51) is worse. Shortest-first is optimal. Q5: For the following preferences, run Gale-Shapley with men proposing: m1: w1>w2>w3, m2: w2>w1>w3, m3: w3>w2>w1. Women: w1: m2>m1>m3, w2: m1>m2>m3, w3: m1>m2>m3.

Answer:

Step 1: m1 proposes to w1 → w1 accepts (tentative: m1-w1) Step 2: m2 proposes to w2 → w2 accepts (tentative: m2-w2) Step 3: m3 proposes to w3 → w3 accepts (tentative: m3-w3) Result: {m1-w1, m2-w2, m3-w3}. Stable? Check blocking pairs:

• w1 prefers m2 over m1, but m2 is matched to w2. m2 prefers w2 over w1? m2's pref: w2>w1>w3. m2 prefers w2 to w1 → OK.
• w3 prefers m1/m2 over m3, but m1 prefers w1 to w3 and m2 prefers w2 to w3 → OK. Matching is stable. Q6: Give an exchange argument for the optimality of shortest-first for tape storage.

Answer: Consider any optimal ordering. If two adjacent files have lengths l₁ > l₂ (larger before smaller), swapping them reduces total cost by l₁ - l₂ > 0 (as shown in 3.3). Repeatedly swapping adjacent inversions produces the shortest-first ordering while reducing (or keeping same) the total cost. Therefore shortest-first is optimal. Q7: Does greedy work for the minimum spanning tree problem? If so, which greedy?

Answer: Yes — MST has optimal substructure and the greedy choice property. Two greedy algorithms: (1) Kruskal's: sort edges by weight, add if no cycle (uses union-find). (2) Prim's: grow tree from starting vertex, always add cheapest edge connecting tree to non-tree vertex. Both are optimal because MST defines a matroid structure (graphic matroid). Q8: Design a greedy algorithm for the coin change problem. When does it fail?

Answer: Greedy: at each step, use the largest coin ≤ remaining amount. Works for US coin systems (25, 10, 5, 1) because each coin value is at least twice the next smaller one. Fails for systems like {1, 3, 4}: greedy for 6 uses 4 + 1 + 1 = 3 coins, but optimal is 3 + 3 = 2 coins. Greedy works for canonical coin systems where the locally optimal choice is globally optimal.

9. 🔗 Cross-References

• Week 2 - Matroid Theory: Formalizing when greedy works
• Week 3 - Dynamic Programming: When greedy fails
• BSCS4022 (OS): Scheduling algorithms Join Discord NextMatroid Theory