Part A (2 marks each)

Q1. Define the Greedy method. An algorithmic paradigm that builds a solution incrementally by making the locally optimal choice at each step — never revising past decisions.

Q2. What two properties must a problem satisfy for greedy to be correct?

1. Greedy-choice property — local optimal choice leads to global optimum.
2. Optimal substructure — an optimal solution contains optimal solutions to its sub-problems.

Q3. Give an example where greedy fails. 0/1 Knapsack. Greedy by value/weight ratio is sub-optimal — sometimes a less efficient combination of items fills capacity better. Dynamic Programming is needed for the optimal solution.

---

Part B (20 marks)

Q. Explain the Greedy algorithm-design technique. State its required properties, illustrate with examples (Kruskal's MST, Huffman coding, Activity selection) and discuss its limitations vs Dynamic Programming.

Greedy paradigm.

Build a solution one piece at a time, always picking the locally best choice, without backtracking. Fast and intuitive — but correct only when the problem has special structure.

Required structure.

1. Greedy-choice property — a global optimum can be constructed by making locally optimal choices.
2. Optimal substructure — an optimal solution to the problem contains optimal solutions to its sub-problems.

If either fails, greedy may produce sub-optimal answers.

Example 1 — Activity selection.

Given $n$ activities with start $s_i$ and finish $f_i$, schedule the maximum number that don't overlap.

Strategy: sort activities by finish time. Iterate; pick each whose start ≥ last selected finish.

Complexity. $O(n \log n)$.

Why optimal. Suppose some optimum picks activity $j$ instead of greedy's choice $g$. Since $f_g \le f_j$, swap $j \to g$ — still a valid schedule with the same count. So some optimum begins with $g$. Apply induction.

Example 2 — Kruskal's MST.

Build a minimum spanning tree of a weighted connected graph.

Strategy.

sort edges by weight
for each edge (u, v) in ascending order:
    if u and v are in different components (Union-Find):
        add (u, v) to MST

Complexity. $O(E \log E)$.

Why optimal. Cut property — the lightest edge crossing any cut is part of some MST. Each greedy step adds such a lightest edge across the cut separating its components.

Worked. Graph with edges $(A,B,4), (A,C,1), (B,C,2), (B,D,5), (C,D,8), (D,E,2), (C,E,10)$: Sorted: $(A,C,1), (B,C,2), (D,E,2), (A,B,4), (B,D,5), (C,D,8), (C,E,10)$.

• Add (A,C) 1; (B,C) 2; (D,E) 2; skip (A,B) [cycle]; add (B,D) 5. Done — 4 edges.
• MST weight = 10.

Example 3 — Huffman coding.

Optimal prefix code for $n$ symbols with frequencies.

Strategy. Put each symbol in a min-heap by frequency. Repeatedly extract the two smallest, combine into a new node whose frequency is the sum, insert back. Continue until one node remains — the Huffman tree.

Complexity. $O(n \log n)$.

Why optimal. Provable by exchange argument: in any optimal prefix tree, the two least-frequent symbols are sibling leaves at the deepest level. The greedy choice respects this.

Application. JPEG, MP3, ZIP all use Huffman (or its variant arithmetic coding).

When greedy fails — 0/1 Knapsack.

Take or leave each item; maximise value within capacity.

Greedy by ratio fails: items $\{(w_1=10, v_1=60), (w_2=20, v_2=100), (w_3=30, v_3=120)\}$, capacity $W = 50$. Ratios 6, 5, 4. Greedy picks 1, 2 → value 160 with weight 30. Optimum picks 2, 3 → value 220 with weight 50.

Reason. No greedy-choice property here; need to consider all combinations. DP solves in $O(nW)$.

Greedy vs DP comparison.

Aspect	Greedy	DP
Builds solution	Incrementally, no revisits	Solves all sub-problems
Memory	Low	High (table)
Speed	Often $O(n \log n)$	Often $O(n^2)$ or $O(nW)$
Correctness	Only if greedy property holds	Always (if applicable)
Examples	MST, Huffman, Activity, Dijkstra	LCS, 0/1 Knapsack, edit distance

Take-away. Greedy is elegant and fast — but correctness must be proven. When in doubt, DP is the safer fallback.