Here is your complete, exam-topper notes for Greedy Methods – the most scoring part of the syllabus!
100% coverage | Diagrams | Proofs | Code | Comparison | Solved Questions

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

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:
1. Sort all edges by weight
2. Use Union-Find (Disjoint Set)
3. 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:
1. Start from any vertex
2. Maintain priority queue of adjacent edges
3. 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:
1. Relax all edges V-1 times
2. 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!