Greedy Algorithms

Activity Selection, Huffman Codes, Minimum Spanning Trees

Greedy Strategy Overview

Key Concepts:

  • Greedy Choice Property: Optimal solution contains greedy choice
  • Optimal Substructure: Optimal solution contains optimal solutions to subproblems
  • Proof Pattern: Show greedy choice is safe (exchange argument), then prove optimal substructure
  • vs Dynamic Programming: Greedy makes one choice and never reconsiders, DP tries all choices

When Greedy Fails:

Greedy doesn't always work! Example: Making change with arbitrary coin denominations, or finding shortest path in graphs with negative weights.

Activity Selection Problem

Key Concepts:

  • Problem: Select maximum number of non-overlapping activities
  • Greedy Choice: Always pick activity with earliest finish time
  • Time Complexity: O(n log n) for sorting + O(n) for selection
  • Why it works: Early finish leaves most room for remaining activities

Algorithm:

  1. Sort activities by finish time
  2. Select first activity
  3. For each remaining activity: if start ≥ last finish, select it

Huffman Codes

Key Concepts:

  • Purpose: Optimal prefix-free binary encoding
  • Greedy Choice: Merge two lowest-frequency nodes repeatedly
  • Time Complexity: O(n log n) with min-heap
  • Result: Variable-length codes, frequent chars get shorter codes
  • Optimality: Produces minimum average code length

Video Recommendations:

🎥 Abdul Bari - Huffman Coding (23 min) 🎥 Tom Scott - Huffman Codes (9 min - quick overview)

Algorithm Steps:

  1. Create leaf node for each character with its frequency
  2. Build min-heap with all nodes
  3. While heap has > 1 node:
    • Extract two minimum nodes
    • Create new internal node with frequency = sum of two nodes
    • Make extracted nodes children, insert new node into heap
  4. Remaining node is root of Huffman tree
  5. Assign codes: left=0, right=1 (or vice versa)

Minimum Spanning Trees (MST)

Key Concepts:

  • MST: Connects all vertices with minimum total edge weight, no cycles
  • Properties: Tree with V-1 edges, unique if edge weights are distinct
  • Generic MST: Grow tree by adding safe edges (edges that maintain MST property)
  • Cut Property: Light edge crossing cut is safe to add

Kruskal's Algorithm

Key Concepts:

  • Strategy: Edge-based - sort edges, add if doesn't create cycle
  • Data Structure: Union-Find (Disjoint Set) for cycle detection
  • Time Complexity: O(E log E) or O(E log V) - dominated by sorting
  • Greedy Choice: Always add minimum weight edge that doesn't form cycle

Video Recommendations:

🎥 Abdul Bari - Kruskal's Algorithm (12 min)

Algorithm:

  1. Sort all edges by weight (ascending)
  2. Initialize: Each vertex in its own set (Union-Find)
  3. For each edge (u,v) in sorted order:
    • If u and v in different sets: add edge to MST, union sets
    • Else: skip (would create cycle)
  4. Stop when MST has V-1 edges

Prim's Algorithm

Key Concepts:

  • Strategy: Vertex-based - grow tree from single vertex
  • Data Structure: Min-heap (priority queue) for selecting minimum weight edge
  • Time Complexity: O((V+E) log V) with binary heap, O(E + V log V) with Fibonacci heap
  • Greedy Choice: Add minimum weight edge connecting tree to non-tree vertex
  • Similar to: Dijkstra's algorithm (both use priority queue, grow from source)

Video Recommendations:

🎥 Abdul Bari - Prim's Algorithm (14 min) 🎥 William Fiset - Prim's MST (13 min)

Algorithm:

  1. Start with arbitrary vertex, add to MST
  2. Initialize: key[v] = ∞ for all vertices, key[start] = 0
  3. While MST doesn't include all vertices:
    • Extract min key vertex u from heap (not yet in MST)
    • Add u to MST
    • For each neighbor v of u: if v not in MST and weight(u,v) < key[v], update key[v]

Greedy Algorithms Comparison

Algorithm Problem Greedy Choice Time Complexity
Activity Selection Max non-overlapping activities Earliest finish time O(n log n)
Huffman Optimal prefix codes Merge two min frequencies O(n log n)
Kruskal's MST Minimum spanning tree Min weight edge (no cycle) O(E log E)
Prim's MST Minimum spanning tree Min edge to new vertex O((V+E) log V)
Dijkstra's Shortest paths Min distance unvisited vertex O((V+E) log V)

Interactive MST Practice - Fill in the Blanks!

Click edges in the order they would be added to the MST. Test your understanding of both algorithms!

Exercise 1: Prim's Algorithm (Starting from vertex A)

Instructions: Click edges in the order Prim's algorithm would add them to the MST. Start from vertex A.

4 2 5 1 7 3 6 8 9 A B C D E F
Your selections: None yet

Correct Order for Prim's Algorithm (from A):

  1. A-C (weight 2): Start from A, minimum edge from A is A-C
  2. C-E (weight 3): Tree is {A,C}. Min edge to new vertex is C-E
  3. A-B (weight 4): Tree is {A,C,E}. Min edge to new vertex is A-B
  4. B-D (weight 1): Tree is {A,B,C,E}. Min edge to new vertex is B-D
  5. D-F (weight 8): Tree is {A,B,C,D,E}. Only option to reach F is D-F

Total MST weight: 2 + 3 + 4 + 1 + 8 = 18

Note: Prim's grows the MST from a single vertex, always choosing the minimum-weight edge that connects the tree to a new vertex.

Exercise 2: Kruskal's Algorithm (Same Graph)

Instructions: Click edges in the order Kruskal's algorithm would add them. Remember: sort by weight, add if no cycle!

4 2 5 1 7 3 6 8 9 A B C D E F
Your selections: None yet

Correct Order for Kruskal's Algorithm:

Step 1: Sort all edges by weight:

B-D(1), A-C(2), C-E(3), A-B(4), B-C(5), D-E(6), B-E(7), D-F(8), E-F(9)

Step 2: Add edges in order, skipping those that create cycles:

  1. B-D (weight 1): Add (no cycle possible yet)
  2. A-C (weight 2): Add (connects new components)
  3. A-B (weight 4): Add (connects {A,C} and {B,D})
  4. C-E (weight 3): Add (E is new vertex)
  5. D-F (weight 8): Add (F is new vertex, now have 5 edges = V-1)

Skipped edges: B-C(5), D-E(6), B-E(7), E-F(9) - all would create cycles

Total MST weight: 1 + 2 + 4 + 3 + 8 = 18

Note: Kruskal's processes edges by weight globally, using Union-Find to detect cycles.

Key Observation:

Both algorithms produce the same MST (total weight 18) but add edges in different orders:

  • Prim's: Grows from vertex A: A-C, C-E, A-B, B-D, D-F
  • Kruskal's: Sorts by weight globally: B-D, A-C, A-B, C-E, D-F

Both are correct! The MST is the same, but the construction process differs.