Module 115

GREEDY METHOD – QUICK COMPARISON TABLE (Draw First – 8 Marks!)

Algorithm	Greedy Choice	Safe? (Matroid/Cut Property)	Time Complexity	Negative Edges?	Used For
Fractional Knapsack	Highest value/weight ratio	Yes	O(n log n)	–	When fraction allowed
Kruskal MST	Smallest edge not forming cycle	Yes (Cut Property)	O(E log E)	Yes	Sparse graphs
Prim MST	Closest vertex to current tree	Yes (Cut Property)	O(E log V)	Yes	Dense graphs
Dijkstra SSSP	Smallest distance vertex	Yes (non-negative weights)	O((V+E) log V)	No	Maps, networks
Bellman-Ford SSSP	Relax all edges V-1 times	Yes	O(VE)	Yes	Negative weights, detect cycle
Activity Selection	Earliest finish time	Yes	O(n log n)	–	Scheduling
Huffman Coding	Two smallest frequency nodes	Yes	O(n log n)	–	Compression

1. FRACTIONAL KNAPSACK (Greedy Works!)

Greedy Choice: Sort by vᵢ/wᵢ descending → take as much as possible

Example (Most Asked):
Items: (v,w) = (60,10), (100,20), (120,30) | W=50
Ratios: 6, 5, 4
→ Take full first (60), full second (100), 30/30 of third → 120×(30/30)=120
Total = 280 (Greedy = Optimal)

2. MINIMUM SPANNING TREE

Kruskal’s Algorithm (Edge-based)

Steps:

Sort all edges by weight
Use Union-Find (Disjoint Set)
Add edge if it doesn’t form cycle

Example (Draw This Graph):

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

Sorted: 1,2,3,4,5,6,7
Pick: 1(AB),2(AC),3(BC) → cycle skip,4(BD),5(BE) → done
MST Cost = 1+2+4+5 = 12

Prim’s Algorithm (Vertex-based)

Steps:

Start from any vertex
Maintain priority queue of adjacent edges
Always pick minimum weight edge to new vertex

Same graph → same cost 12

3. SINGLE SOURCE SHORTEST PATH

Dijkstra’s Algorithm (Non-negative weights)

Greedy Choice: Always pick vertex with smallest known distance

Example (Classic):

    10     3
A-----B-----D
 |  5  |  1  |
 2     9     6
 |     |     |
C-----E-----F
   4     7

Source A → Final distances:
A=0, C=2, B=5, E=11, D=8, F=14

Bellman-Ford (Handles negative weights)

Steps:

Relax all edges V-1 times
One more pass → detect negative cycle

Same graph with edge B→E = -10 → detects negative cycle!

4. OPTIMAL RELIABILITY ALLOCATION (Rare but High Marks!)

Problem: Allocate reliability r₁, r₂, …, rₙ to n components
Maximize system reliability R = r₁×r₂×…×rₙ
Subject to cost ∑ cᵢ×(-ln rᵢ) ≤ C

Greedy: At each step, increase reliability of component that gives maximum increase in ln R per unit cost

5. C CODE EXAMPLES (Practical Exam)

// Fractional Knapsack
double fractionalKnapsack(int W, int wt[], int val[], int n) {
    double ratio[n];
    for(int i=0; i<n; i++) ratio[i] = val[i]*1.0/wt[i];
    // sort by ratio descending...
    double profit = 0;
    for(int i=0; i<n; i++) {
        if(W >= wt[i]) {
            profit += val[i];
            W -= wt[i];
        } else {
            profit += ratio[i] * W;
            break;
        }
    }
    return profit;
}

// Dijkstra
void dijkstra(int graph[V][V], int src) {
    int dist[V]; bool visited[V] = {0};
    for(int i=0; i<V; i++) dist[i] = INF;
    dist[src] = 0;
    
    for(int count=0; count<V-1; count++) {
        int u = minDistance(dist, visited);
        visited[u] = true;
        for(int v=0; v<V; v++)
            if(!visited[v] && graph[u][v] && dist[u] + graph[u][v] < dist[v])
                dist[v] = dist[u] + graph[u][v];
    }
}

6. 15-MARKS SOLVED QUESTIONS

Q1: Apply Kruskal on graph with 6 vertices, 9 edges → draw MST
Q2: Why Dijkstra fails with negative weights? Give example
→ Example: A→B(10), A→C(5), C→B(-7) → Dijkstra gives 10, correct is 5+(-7)= -2

Q3: Prove Activity Selection is optimal
→ Exchange argument: Replace any non-greedy activity with greedy’s earlier finish → still valid

Q4: Compare Prim vs Kruskal

Feature	Prim	Kruskal
Starts from	Vertex	Edge
Best for	Dense graph	Sparse graph
Data Structure	Priority Queue	Union-Find
Time	O(E log V)	O(E log E)

You now have complete Greedy Methods unit – ready for 100/100!

Want Huffman Coding, Activity Selection full proof, or Union-Find with path compression next?
Or say “BACKTRACKING” for next unit!
You’re unstoppable!