Greedy Algorithms: MST, Scheduling, Knapsack & Analysis

Core Idea: What is a Greedy Algorithm?

Greedy algorithms make locally optimal choices at each step, hoping these lead to a globally optimal solution. They are not guaranteed to work for all problems (e.g., 0/1 knapsack), but excel when:

• A problem has optimal substructure (optimal solution contains optimal solutions to subproblems).
• A greedy choice property holds: a global optimum can be built by combining local optima.

Key Limitation:

"Greedy algorithms fail when a locally optimal choice prevents a globally optimal solution later." (Example: Coin change with {1, 3, 4} pennies for 6¢.)

---

1. Minimum Spanning Tree (MST) Problems

MSTs connect all nodes with the least total edge weight, used in:

• Network design (e.g., NTC’s fiber-optic backbone).
• Cluster analysis (e.g., Daraz’s warehouse routing).
• Traffic optimization (e.g., Kathmandu’s ring road expansion).

Kruskal’s Algorithm (Union-Find + Sort)

Steps:

1. Sort all edges by weight.
2. Add edges one by one, skipping those that create cycles (checked via Disjoint Set Union (DSU)).

def kruskal(graph):
    edges = sorted(graph.edges, key=lambda x: x.weight)
    mst = []
    dsu = DSU(graph.nodes)
    for edge in edges:
        if not dsu.connected(edge.u, edge.v):
            mst.append(edge)
            dsu.union(edge.u, edge.v)
    return mst

Trace for Graph G (4 nodes, 5 edges):

Step  | Edge Added | DSU State (Sets)       | Cycle?
----- | ---------- | ---------------------- | ------
1     | AB (1)     | {A}, {B}, {C}, {D}     | No
2     | CD (2)     | {A}, {B}, {C,D}        | No
3     | BC (3)     | {A}, {B,C,D}           | No
4     | AD (4)     | {A,D}, {B,C}           | No  ← *Optimal MST*
5     | BD (5)     | Skipped (cycle A-D-B)  | Yes

Final MST Weight: 1 + 2 + 3 + 4 = 10

---

2. Prim’s Algorithm (Priority Queue + Greedy)

Starts at a node and grows the MST by adding the cheapest edge to the current tree.

Time Complexity:

Real-World Tie:

• NTC’s Internet Backbone: Uses Prim’s algorithm to minimize cable costs when expanding rural connectivity.
• Pathao’s Ride Routing: Greedily selects the shortest path segments to optimize driver earnings.

---

3. Scheduling Problems

Shortest-Job-First (SJF)

Goal: Minimize average waiting time for jobs. Greedy Choice: Schedule the shortest job next.

Example: Jobs with arrival times and durations:

Gantt Chart:

0----1----2----3----4----5----6----7
| A  | B  | C  | D  |     |

Total Waiting Time: (B waits 5, C waits 3, D waits 0) → 8 units.

---

4. Knapsack Problems

Fractional Knapsack (Greedy Works!)

Problem: Maximize value in a knapsack of capacity $W$, given items with weights and values. Greedy Choice: Sort items by value/weight ratio and take fractions.

Example:

Knapsack Capacity $W=5$ kg:

1. Take Item 2 (1 kg, value 10).
2. Take Item 4 (2 kg, value 15).
3. Take half of Item 1 (1 kg, value 6). Total Value: 10 + 15 + 6 = 31.

---

0/1 Knapsack (Greedy Fails!)

Problem: Items cannot be split. Greedy (highest ratio first) gives suboptimal results. Example:

• Greedy picks B (100) + A (60) → 160 (but optimal is C (120) + A (60) = 180).

Why Greedy Fails:

"The optimal solution may require sacrificing a high-ratio item to allow two lower-ratio items to fit together."

---

5. Huffman Coding (Greedy for Compression)

Goal: Assign shorter codes to frequent characters. Greedy Choice: Always combine the two least frequent nodes into a new tree.

Example: Frequencies = {A:5, B:9, C:12, D:13, E:16, F:45}

Step 1: Merge F(45) + E(16) → 61
Step 2: Merge D(13) + C(12) → 25
Step 3: Merge B(9) + A(5) → 14
Step 4: Merge 14 + 25 → 39
Step 5: Merge 39 + 61 → 100 (root)

Huffman Tree:

      100
     /  \
   61    39
  / \   / \
 45 16 25 14
    |   / \
   E  D  C  B
        |   |
        A   F

Codes:

• F: 0 (45)
• E: 10 (16)
• D: 110 (13)
• C: 1110 (12)
• B: 11110 (9)
• A: 11111 (5)

Real-World Tie:

• WhatsApp Compression: Uses Huffman-like algorithms to reduce message sizes.
• eSewa Data Storage: Compresses transaction logs to save cloud costs.

---

6. Correctness of Greedy Algorithms

Proof Techniques:

1. Exchange Argument: Show swapping a greedy choice with an optimal one doesn’t improve the solution.
2. Cut Property: For MST, the cheapest edge crossing any cut is in the MST.
3. Matroids: A problem is greedy-solvable if it satisfies independence and exchange properties.

Example for Fractional Knapsack:

"If an item’s ratio is higher than the remaining capacity’s average ratio, taking it cannot hurt optimality."

---

Comparison Table: Greedy vs. DP vs. Backtracking

---

In the Real World

1. eSewa’s Payment Routing:

   • Uses Prim’s algorithm to route payments between banks/financial institutions with minimal transaction fees.
   • Example: When you pay a bill via eSewa, the system greedily selects the cheapest path through the payment network (e.g., eSewa → NMB → NTC → Merchant).

2. Daraz’s Warehouse Order Picking:

   • Shortest-Job-First scheduling assigns pickers to orders based on proximity to items.
   • Example: If Order #123 has items in Zone A (5m walk) and Order #456 has items in Zone C (10m walk), #123 is picked first to minimize total travel time.

3. Ncell’s Network Optimization:

   • Kruskal’s MST designs the cheapest tower placement for 4G coverage in remote areas.
   • Example: For a village with 5 potential tower sites, Ncell uses MST to connect all sites with the least fiber cable (e.g., sites A-B-C-D-E with weights 3, 2, 4, 1 km).

4. Khalti’s Fraud Detection:

   • Greedy anomaly detection flags transactions with the highest "risk/value" ratio first.
   • Example: A ₹500 transfer to an unknown merchant in India might trigger alerts before a ₹50,000 transfer to a known bank.

---

Exam Tip

1. Always Prove Correctness:

   • For MST, state the cut property or exchange argument.
   • For knapsack, explain why greedy fails with a counterexample.

2. Pseudocode > Code:

   • Write clear steps (e.g., "Sort edges by weight" for Kruskal) rather than full implementations.
   • Example Answer Snippet:

     "Kruskal’s algorithm first sorts edges in $O(E\log E)$ time, then uses DSU to add edges in $O(E\alpha (V))$, where $\alpha$ is the inverse Ackermann function."

3. Time Complexity is Critical:

   • Memorize:
     • Kruskal: $O(E\log E)$
     • Prim (with heap): $O(E\log V)$
     • Huffman: $O(n\log n)$ for $n$ characters.

4. Real-World Links:

   • If asked about applications, name a Nepali company (e.g., "NTC uses Prim’s algorithm for...") and describe the greedy choice (e.g., "cheapest edge to expand coverage").

5. Trace Tables for Marks:

   • For scheduling or MST, show a step-by-step table with:
     • Action (e.g., "Add edge AB")
     • Data Structure State (e.g., DSU sets: {A,B}, {C}, {D})
     • Justification (e.g., "No cycle detected")

---

Practice Questions (Exam-Style)

1. Define the greedy choice property and give an example where it holds and where it fails.
2. Apply Kruskal’s algorithm to the following graph and prove your MST is optimal.

   A --3-- B
   | \      |
   1  2    4
   | /      |
   D --5-- C
   

3. Why does Prim’s algorithm use a priority queue? What happens if you use a linear scan instead?
4. Trace Huffman coding for the frequencies: A:7, B:5, C:2, D:4, E:3. What is the average code length?
5. Explain why the 0/1 knapsack problem cannot be solved greedily. Provide a counterexample.