Greedy algorithms

ACompressed recap

🧾

Greedy: locally best, never undone; prove with the greedy-choice property, optimal substructure and an exchange argument. Activity selection: earliest finish, Θ(n log n). Fractional knapsack: best ratio first, last item fractional; 0/1 knapsack: greedy fails. Job sequencing (unit jobs): profit descending, latest free slot ≤ deadline. Huffman: merge the two smallest, cost = Σ merges, average = cost/Σf; prefix-free codes. Optimal merge pattern = Huffman on file sizes. Greedy fails for 0/1 knapsack and non-canonical coin change.

BMerged rule card

4.2.1 The greedy method; activity selection

• Greedy: locally best choice, never undone; needs greedy-choice property + optimal substructure; prove by exchange.
• Activity selection: sort by finish; pick if start ≥ last finish; Θ(n log n).
• Shortest-first, earliest-start, fewest-conflicts can fail.

4.2.2 Fractional knapsack; job sequencing with deadlines

• Fractional knapsack: sort by v/w; fill greedily; last item fractional; optimal; Θ(n log n).
• 0/1 knapsack: greedy fails → DP.
• Job sequencing (unit jobs): profit descending; latest free slot ≤ deadline; optimal.

4.2.3 Huffman coding

• Prefix-free code ↔ binary tree; length = depth.
• Huffman: repeatedly merge the two smallest weights; Θ(n log n); optimal.
• Cost = Σ f·len = Σ merge weights; average = cost / Σ f.
• Ties: different codes, same cost.

4.2.4 Optimal merge pattern; when greedy fails

• Optimal merge: repeatedly merge the two smallest (min-heap); cost = Σ merges; = Huffman.
• Greedy fails: 0/1 knapsack, coin change with non-canonical coins, shortest-first activities, nearest-neighbour paths.
• Canonical coin systems: greedy works.

CInterleaved GATE-style questions

Q1NAT1 markActivities

Activities (s, f): (1, 3), (2, 4), (3, 5), (4, 6), (5, 7). Maximum compatible set size?

Numerical answer: ________

Q2NAT2 marksFractional

Capacity 10; items (value, weight): (10, 2), (12, 4), (18, 6). Fractional knapsack value?

Numerical answer: ________

Q3NAT2 marksJobs

Jobs (deadline, profit): (1, 3), (2, 5), (2, 20), (3, 18), (3, 1), (4, 6), (4, 30). Maximum profit?

Numerical answer: ________

Q4NAT2 marksHuffman

Frequencies 8, 3, 2, 1, 1 (five symbols). Total Huffman cost?

Numerical answer: ________

Q5MCQ1 markHuffman property

In a Huffman tree, the two least frequent symbols:

• (A) get the shortest codes
• (B) can be siblings at the deepest level
• (C) must have different lengths
• (D) are always at depth 1

Q6NAT2 marksMerge

Optimal merge cost for files of sizes 10, 20, 30, 40?

Numerical answer: ________

Q7NAT1 markCoins

Coins {1, 3, 4}, amount 10: coins used by largest-first?

Numerical answer: ________

Q8MSQ2 marksFacts

Which are true?

• (A) The optimal merge pattern merges the two smallest files first.
• (B) Greedy coin change is optimal for every coin system.
• (C) Huffman coding runs in Θ(n log n) with a heap.
• (D) 0/1 knapsack can be solved optimally by greedy value/weight.

DAnswer Vault