Greedy Algorithms

What is Greedy?

Greedy algorithms make the locally best choice at each step without looking back. Think of a person who, at every intersection, always takes the road that seems shortest right now — without planning the full route.

Sometimes this works perfectly (Dijkstra, Prim, Huffman). Sometimes it fails catastrophically (0/1 knapsack with bad denominations).

Two properties needed for greedy to work correctly: 1. Greedy Choice Property: A globally optimal solution can be reached by making locally optimal choices. 2. Optimal Substructure: Optimal solution to the problem contains optimal solutions to subproblems.

---

Activity Selection — When to Schedule Meetings

Problem: You have a meeting room. Given n activities with start and finish times, select the maximum number of non-overlapping activities.

Greedy strategy: Always pick the activity that finishes earliest (leaves maximum time for future activities).

Activities: [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14)]
Sort by finish time: [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14)]

Select (1,4): finish=4. ✓
Skip (3,5): starts at 3, overlaps with (1,4) since 3 < 4.
Skip (0,6): starts at 0, overlaps.
Select (5,7): starts at 5 ≥ 4. ✓
Skip (3,9), (5,9): overlap.
Select (6,10)? Wait — starts at 6 < 7. Skip.

Actually: select (8,11): starts at 8 ≥ 7. ✓
Done: 3 activities selected.

Why finish-earliest works: Choosing the earliest-finishing activity leaves the maximum remaining time for other activities. Proof by exchange argument: if optimal solution uses activity B instead of earlier-finishing A, swapping A for B doesn't reduce the count (A finishes no later than B).

---

Huffman Coding — Optimal Data Compression

Problem: Assign binary codes to characters so frequently used characters get shorter codes, minimising total encoded length.

Greedy strategy: Always merge the two nodes with the lowest frequency.

Characters and frequencies:
a:5, b:9, c:12, d:13, e:16, f:45

Step 1: Merge a(5) and b(9) → new node (14)
Step 2: Merge (14) and c(12) → new node (26)
Step 3: Merge d(13) and e(16) → new node (29)
Step 4: Merge (26) and (29) → new node (55)
Step 5: Merge f(45) and (55) → root (100)

Huffman tree:
          (100)
         /     \
       f(45)   (55)
              /    \
           (26)    (29)
           /  \   /  \
         (14) c  d   e
         / \
        a   b

Codes: f=0, c=101, d=110, e=111, a=1000, b=1001

Frequently used f gets shortest code (1 bit), rarely used a and b get longer codes (4 bits). Total encoded length is minimised.

Time: O(n log n) with a min-heap.

---

Fractional Knapsack — Greedy Works Here

Problem: Items with weights and values. Can take fractions of items. Maximise value in capacity W.

Greedy: Sort by value/weight ratio (descending). Take items greedily; if last item doesn't fit, take the fraction that fits.

Items: (w=10, v=60), (w=20, v=100), (w=30, v=120)
Capacity: W=50
Ratios: 60/10=6, 100/20=5, 120/30=4

Take full item 1 (w=10, v=60). Remaining W=40.
Take full item 2 (w=20, v=100). Remaining W=20.
Take 2/3 of item 3 (w=20, v=80). Remaining W=0.
Total value = 60 + 100 + 80 = 240

Why greedy works: Taking more of higher value-density always improves or maintains the objective. Formal proof by exchange argument.

---

When Greedy FAILS — 0/1 Knapsack

You CANNOT take fractions. A greedy approach (take highest value-density first) fails.

Items: (w=10, v=60), (w=20, v=100), (w=30, v=120)
Capacity: W=50

Greedy by ratio: Take item 1 (v=60, w=10). Take item 2 (v=100, w=20). Now W=20 left.
Item 3 needs w=30 — doesn't fit. Nothing else fits.
Greedy total: 60 + 100 = 160

But OPTIMAL is: Take items 2 and 3 (w=20+30=50, v=100+120=220).
Optimal total: 220 > 160

Greedy failed! 0/1 Knapsack requires Dynamic Programming.

---

Greedy vs DP — Decision Table

Problem	Greedy?	Why
Activity selection	✓	Exchange argument works
Huffman coding	✓	Locally best merge is globally optimal
Fractional knapsack	✓	Can take fractions → greedy choice is always valid
0/1 knapsack	✗	Cannot take fractions — need to try all combinations
Coin change (standard: 1,5,10,25)	✓	Canonical coin systems are greedy-safe
Coin change (arbitrary: 1,3,4)	✗	Example: sum=6 → greedy gives {4,1,1}, DP gives {3,3}

---

Quick Check

Q1. Activities: (0,3), (1,4), (2,5), (3,6). Select maximum non-overlapping.

Sort by finish: (0,3), (1,4), (2,5), (3,6)
Select (0,3). Skip (1,4) — overlap. Skip (2,5) — overlap.
Select (3,6) — starts at 3 ≥ 3. ✓
Answer: **2 activities**.

Q2. Is Dijkstra's algorithm a greedy algorithm?

Answer: Yes — at each step, Dijkstra greedily picks the vertex with the smallest current distance. It works because edge weights are non-negative (greedy choice property holds).