Classic Greedy Algorithms — Algorithms Course

What you'll learn

Greedy shines on a surprising range of real problems. Here are its classics — packing a knapsack by value density, building optimal compression codes, and scheduling jobs — plus a preview of the greedy graph algorithms coming in Phase 7.

By the end you'll be able to:

Solve fractional knapsack greedily
Explain how Huffman coding compresses data optimally
Recognize greedy scheduling problems
See why MST and Dijkstra are greedy at heart

Fractional knapsack

You have a knapsack of capacity W and items with values and weights. In the fractionalversion you may take fractions of items. The greedy rule is optimal here: sort by value-to-weight ratio and take the densest first, splitting the last item to fill the bag:

Language

fractional_knapsack.py

def fractional_knapsack(items, capacity):   # items: (value, weight)
    items.sort(key=lambda it: it[0] / it[1], reverse=True)  # value/weight
    total = 0.0
    for value, weight in items:
        if capacity >= weight:
            total += value; capacity -= weight       # take all of it
        else:
            total += value * (capacity / weight)     # take a fraction
            break
    return total

Watch out

This works only because items are divisible. The 0/1 knapsack (whole items only) breaks the greedy-choice property and needs dynamic programming — you'll build it in Module 17.

Huffman coding

Huffman coding produces an optimal prefix code for compression: no code is a prefix of another, so a bit-stream decodes unambiguously. The greedy build: put every symbol in a min-priority-queue by frequency, then repeatedly merge the two least-frequent nodes into a parent until one tree remains. Frequent symbols end up near the root with short codes:

Huffman codes for a sample text

Frequent symbols get short codes, rare ones get long codes — built by repeatedly merging the two lowest-frequency nodes:

freq 45

freq 12

100

freq 13

101

freq 5

1100

freq 9

1101

freq 16

111

Key idea

Merging the two rarest symbols first is the greedy choice, and an exchange argument proves it yields the minimum total encoded length. It's the backbone of formats like JPEG, MP3, and ZIP.

Scheduling problems

Job sequencing with deadlines: to maximize profit, consider jobs by decreasing profit and place each in the latest free slot before its deadline.
Interval partitioning: to schedule all intervals in the fewest rooms, sort by start time and assign each to any free room — the number of rooms equals the maximum overlap.

Greedy on graphs

Two of the most important graph algorithms are greedy. Minimum spanning tree (Kruskal/Prim) repeatedly adds the cheapest safe edge. Dijkstra's shortest paths repeatedly finalizes the nearest unvisited vertex. Both are provably optimal by exchange-style arguments — you'll build them in Phase 7.

Problem	Greedy rule	Optimal?
`Fractional knapsack`	Highest value/weight first	Yes
`Huffman coding`	Merge two rarest symbols	Yes
`MST`	Add cheapest safe edge	Yes
`0/1 knapsack`	Highest value/weight first	No — use DP

Recap & quick check

Key takeaways

Fractional knapsack: take items by value/weight ratio — greedy is optimal because items are divisible.
Huffman coding builds an optimal prefix code by merging the two least-frequent nodes.
Job sequencing and interval partitioning are greedy scheduling classics.
MST (Kruskal/Prim) and Dijkstra are greedy graph algorithms.
0/1 knapsack looks greedy but isn't — it needs DP.

Quick check

1. The greedy rule for fractional knapsack is to take items by:

2. How does Huffman coding build its tree?

3. Why does greedy work for fractional but not 0/1 knapsack?

4. Which is a greedy graph algorithm?

When greedy isn't enough, the most powerful technique in the course takes over. Next up: Module 15 — Introduction to Dynamic Programming.