Greedy Algorithms & Huffman Coding: Optimal Choices & Compression

TAKEAWAYS

• Greedy algorithms make locally optimal choices at each step (e.g., Kruskal’s MST picks the cheapest edge first) but do not guarantee global optimality unless proven correct.
• Huffman coding builds a binary tree where shorter codes go to frequent symbols, reducing file size by up to 50% for skewed data (e.g., English text).
• Proving correctness for greedy algorithms requires:
  1. A greedy-choice property (local choice leads to global optimum).
  2. An optimal substructure (optimal solution contains optimal sub-solutions).
• Applications:
  • eSewa/Khalti: Dynamic routing for payment confirmations (shortest-path greedy).
  • Daraz: Delivery scheduling (interval scheduling greedy).
  • WhatsApp: Huffman-like encoding for messages (though modern apps use arithmetic coding).
• Time complexity:
  • Greedy algorithms: O(n log n) for sorting (e.g., Kruskal’s with Union-Find).
  • Huffman coding: O(n) for tree construction (priority queue operations).
• Exam traps:
  • False positives: Not all problems with optimal substructure are greedy (e.g., 0/1 knapsack).
  • Implementation details: Priority queues (heaps) are critical for efficiency.

1. Greedy Algorithms: The Art of Making the Best Local Choice

Greedy algorithms solve problems by sequentially making the locally optimal choice at each step, without reconsidering past decisions. They are fast (often polynomial time) but not always correct—you must prove their validity for each problem.

1.1 How Greedy Algorithms Work

flowchart TD
    A["Problem Instance"] --> B["Step 1: Select the best immediate choice"]
    B --> C["Step 2: Fix that choice and remove its constraints"]
    C --> D["Step 3: Repeat on the reduced problem"]
    D --> E["Terminate when no choices left"]
    E --> F["Return the constructed solution"]

Key Idea:

"A greedy algorithm is like a chef who, at each step, picks the most delicious ingredient available—without tasting the full dish first. Sometimes it works (e.g., lasagna), sometimes it doesn’t (e.g., soup)."

1.2 When to Use Greedy Algorithms

Greedy algorithms work only if:

1. Greedy-choice property: A global optimum can be reached by making locally optimal choices.
2. Optimal substructure: The problem can be broken into smaller subproblems whose optimal solutions combine to solve the larger problem.

Example Problems Solved by Greedy Algorithms:

1.3 Worked Example: Interval Scheduling (Real-World Tie to Daraz Delivery Routes)

Problem: Daraz needs to schedule deliveries for 5 orders with the following start/end times (in minutes):

Goal: Maximize the number of deliveries completed (no overlapping).

Greedy Approach:

1. Sort by finish time (earliest first): A (10:30), B (11:00), E (12:30), C (11:30), D (12:00) → A, B, E, C, D.
2. Select A (9:00–10:30).
3. Next compatible: B (9:30–11:00) → select B.
4. Next compatible: E (11:00–12:30) → select E.
5. No more compatible (C and D overlap with E).

Optimal Solution: A, B, E (3 deliveries). Greedy Solution: A, B, E (correct!).

Why It Works:

• Greedy-choice: Picking the earliest-finishing job leaves the most room for others.
• Optimal substructure: The remaining problem (after selecting A) is still an interval-scheduling problem.

1.4 Worked Example: Coin Change Problem (eSewa Payment Simulation)

Problem: eSewa’s payment system uses coins of denominations 1, 5, 10, 25 (like Nepali rupees). For a payment of 36, what’s the minimum number of coins needed?

Greedy Approach (Fails Here!):

1. Take the largest coin ≤ 36 → 25 (remaining: 11).
2. Next largest ≤ 11 → 10 (remaining: 1).
3. Next largest ≤ 1 → 1. Total coins: 3 (25 + 10 + 1).

But the optimal solution is 4 coins: 10 + 10 + 10 + 5 + 1 (but wait, 10+10+10+5+1=36 uses 5 coins—actually, the greedy solution is optimal for canonical coin systems like US coins. For Nepali coins, it depends on the denominations!).

Correction: If denominations are 1, 2, 5, 10, 20, 50, greedy fails for 36:

• Greedy: 20 + 10 + 5 + 1 (4 coins).
• Optimal: 20 + 10 + 5 + 1 (same here, but for 31, greedy gives 20+10+1, optimal is 20+5+5+1).

Lesson:

"Greedy algorithms require problem-specific proof. The coin-change problem is greedy-only for certain coin systems (e.g., US coins)."

1.5 Minimum Spanning Tree (MST) with Kruskal’s Algorithm

Real-World Tie: NTC’s Fiber-Optic Network Expansion NTC wants to connect 5 cities (A, B, C, D, E) with the cheapest fiber-optic cables. Edge weights are costs in lakhs.

Kruskal’s Algorithm (Greedy MST):

1. Sort edges by weight: B-D (1), A-C (2), A-B (4), B-C (3), C-D (5), D-E (8).
2. Add edges without cycles:
   • Add B-D (1).
   • Add A-C (2).
   • Add A-B (4) → cycle detected (A-B-D) → skip.
   • Add B-C (3).
   • Stop (4 edges for 5 nodes).

MST Cost: 1 + 2 + 3 = 6 lakhs.

Why It’s Greedy:

• At each step, we pick the cheapest available edge that doesn’t form a cycle.
• Proven correct via the cut property (the cheapest edge crossing any cut is in the MST).

1.6 Proving Greedy Algorithms Correct

Example: Huffman Coding (covered later) uses a greedy approach to build the tree. To prove it’s correct:

1. Greedy-choice: The two least-frequent symbols should be merged next.
2. Optimal substructure: The remaining problem is a smaller Huffman tree.

General Proof Template:

2. Huffman Coding: Compressing Data Like a Pro

Huffman coding is a lossless compression technique that assigns variable-length codes to symbols based on their frequency. Shorter codes for frequent symbols, longer for rare ones.

2.1 How Huffman Coding Works

1. Build a frequency table for symbols (e.g., letters in a text file).
2. Construct a binary tree:
   • Start with leaves for each symbol (frequency = count).
   • Repeatedly merge the two least-frequent nodes into a new internal node.
3. Assign codes:
   • Traverse the tree: left = 0, right = 1.
   • The path from root to leaf gives the code.

Example: Compress the message "ABRACADABRA" (11 letters).

Step-by-Step Tree Construction:

Steps:

1. Merge C (1) and D (1) → new node (2).
2. Merge R (2) and B (2) → new node (4).
3. Merge A (5) and node (4) → root (9). (Wait, frequencies don’t add up—let’s correct this.)

Corrected Steps:

1. Merge C (1) + D (1) → node (2).
2. Merge R (2) + B (2) → node (4).
3. Merge node (2) + node (4) → node (6).
4. Merge A (5) + node (6) → root (11).

Final Tree:

Codes:

• A: 1 (5 occurrences)
• B: 010 (2)
• R: 0110 (2)
• C: 0111 (1)
• D: 00 (1)

Original size: 11 letters × 8 bits = 88 bits. Compressed size: 5×1 + 2×3 + 2×4 + 1×4 + 1×2 = 5 + 6 + 8 + 4 + 2 = 25 bits. Compression ratio: 71% reduction!

2.2 Huffman Coding in the Real World

2.3 Worked Example: Huffman Coding for Nepali Words

Problem: Compress the Nepali sentence "मेरो नाम नेपाल हो" (5 words, repeated letters). Assume frequencies (simplified):

Steps:

1. Merge ल (1) + हो (1) → node (2).
2. Merge म (2) + node (2) → node (4).
3. Merge र (2) + प (2) → node (4).
4. Merge node (4) + node (4) → root (8).
5. Merge न (3) + root (8) → final tree (11).

Tree:

Codes:

• न: 0 (3)
• म: 100 (2)
• र: 1010 (2)
• प: 1011 (2)
• ल: 1100 (1)
• हो: 1101 (1)

Compression: Original (Unicode): 5 words × avg. 4 bytes = 20 bytes. Compressed: 3×1 + 2×3 + 2×4 + 1×4 + 1×4 = 3 + 6 + 8 + 4 + 4 = 25 bits (~3 bytes). Savings: ~85%!

2.4 Advantages and Limitations of Huffman Coding

Example Entropy Calculation: For the Nepali example: $$H=-\left(\frac{3}{11}{\log }_2\frac{3}{11}+\frac{2}{11}{\log }_2\frac{2}{11}\times 3+\frac{1}{11}{\log }_2\frac{1}{11}\times 2\right)\approx 2.29\text{ bits/symbol}.$$ Our Huffman average code length: $25/11\approx 2.27$ bits/symbol → near-optimal!

In the Real World

1. eSewa/Khalti Payment Routing:

   • When you pay via eSewa, the system uses a greedy shortest-path algorithm (like Dijkstra’s) to route your transaction through the cheapest/fastest servers.
   • How: Each server has a "cost" (latency + fee). The algorithm picks the path with the minimum cumulative cost at each step.

2. Daraz Delivery Optimization:

   • Daraz’s delivery system schedules packages using interval scheduling (a greedy algorithm).
   • Example: If a courier has slots at 9–10 AM, 10–11 AM, and 11–12 PM, and orders arrive at 9:15 AM (10:45 delivery) and 10:30 AM (11:30 delivery), the greedy choice picks the 9:15 AM order first (earliest finish), leaving room for the 10:30 AM order.

3. WhatsApp Message Compression:

   • While WhatsApp now uses arithmetic coding (more advanced), Huffman coding was historically used to compress messages before encryption.
   • Example: The word "hello" (5 letters) in ASCII is 40 bits. Huffman might encode it in ~15 bits if h and e are frequent.

Exam Tip

What Examiners Love to Test

1. Greedy Algorithm Proofs:

   • Do: Show the greedy-choice property and optimal substructure.
   • Avoid: Assuming all greedy algorithms work—always prove correctness.
   • Example Question: "Prove that Kruskal’s algorithm for MST is correct using the cut property."

2. Huffman Coding Steps:

   • Must show:
     1. Frequency table.
     2. Tree construction (merge steps).
     3. Code assignment (left=0, right=1).
     4. Compression ratio calculation.
   • Common Mistake: Forgetting to sort frequencies before merging.

3. Real-World Applications:

   • Link greedy algorithms to:
     • MST: NTC fiber networks, Daraz delivery routes.
     • Interval Scheduling: Exam timetabling, courier scheduling.
   • Link Huffman coding to:
     • Message apps (WhatsApp), file storage (eSewa logs).

4. Time Complexity:

   • Greedy algorithms: Often O(n log n) due to sorting/heap operations.
   • Huffman coding: O(n) for tree construction (priority queue).

5. False Positives:

   • Not all problems are greedy:
     • 0/1 Knapsack: Greedy fails (take highest value first may not fit).
     • Traveling Salesman: NP-hard, no known greedy solution.

Sample Exam Questions & Answers

Q1: "Explain how Huffman coding compresses the string ABRACADABRA. Show the tree and calculate the compression ratio." Answer:

1. Frequency table: A(5), B(2), R(2), C(1), D(1).
2. Tree construction (as shown above).
3. Codes: A(1), B(010), R(0110), C(0111), D(00).
4. Compressed size: 5×1 + 2×3 + 2×4 + 1×4 + 1×2 = 25 bits.
5. Original: 11 × 8 = 88 bits → 71% compression.

Q2: "Why does the greedy algorithm fail for the coin-change problem with denominations {1, 3, 4} and amount 6?" Answer:

• Greedy picks 4 + 1 + 1 (3 coins).
• Optimal: 3 + 3 (2 coins).
• No greedy-choice property: Picking the largest coin first doesn’t guarantee optimality.

Q3: "Describe Prim’s algorithm for MST. How does it differ from Kruskal’s?" Answer:

• Prim’s:
  1. Start with any node.
  2. At each step, add the cheapest edge connecting a tree node to a non-tree node.
  3. Repeat until all nodes are included.
• Difference:

  Prim’s	Kruskal’s
  Works on connected components	Needs all edges sorted.
  Uses adjacency list	Uses edge list.
  O(E log V) (with priority queue)	O(E log E) (sorting).

Final Checklist for Full Marks

• Definitions: Greedy-choice property, optimal substructure, prefix-free codes.
• Algorithms: Kruskal’s, Huffman coding steps with visual tree.
• Proofs: Show why a greedy algorithm works (or fails).
• Real-world ties: eSewa (MST), Daraz (interval scheduling), WhatsApp (Huffman).
• Complexity: O(n log n) for greedy, O(n) for Huffman.
• Traces: Show state after each step (e.g., Huffman tree growth).