Greedy Algorithms for GATE CS: Concepts, Worked Examples, and Where Greedy Fails

Greedy looks like the easiest algorithm design idea: just pick the best option at every step. Yet that shortcut produces wrong answers whenever the local best choice blocks a better final combination. A greedy algorithm commits to the locally optimal choice at each step, so its correctness depends on whether that choice can appear in an optimal solution.

What actually makes an algorithm greedy

A greedy algorithm builds a solution one piece at a time. At each step, it commits irrevocably to the locally optimal available choice and never revisits that decision.

Brute force enumerates complete possibilities. Dynamic programming solves overlapping subproblems while preserving alternatives.

For greedy to be correct, not merely fast, the problem needs two properties:

1. Greedy-choice property: Some optimal solution contains the first greedy choice. An exchange argument usually proves this by replacing the first choice in another optimal solution without making that solution worse.

2. Optimal substructure: After making the greedy choice, the remaining work is a smaller instance whose optimal solution completes the original one.

Greedy is a proof obligation, not a vibe. Its code is often short, but the correctness argument separates understanding from pattern matching.

The core greedy problem set for GATE CS

Hold these six problems and their selection rules cold:

• Activity selection: Choose the compatible activity with the earliest finish time.

• Fractional knapsack: Take the item with the highest value per unit weight first.

• Job sequencing with deadlines: Consider jobs by descending profit and place each in its latest free slot.

• Huffman coding: Repeatedly merge the two lowest frequencies.

• Kruskal and Prim MST: Add the lightest edge that is safe for the growing forest or tree.

• Dijkstra shortest paths: Settle the closest unsettled vertex, with non-negative edge weights only.

Consider fractional knapsack with capacity W = 50 and items A(10, 60), B(20, 100), and C(30, 120). Their value-to-weight ratios are 6, 5, and 4. Take all of A and B, using 30 units of capacity, then take 20/30 of C. The value is 60 + 100 + (20/30 x 120) = 60 + 100 + 80 = 240, which is optimal for the fractional version.

These complexities and selection rules both appear in direct questions.

Worked example 1: Kruskal's algorithm end to end

Take vertices {A, B, C, D, E} and seven undirected edges: A-B = 1, D-E = 2, B-E = 3, B-D = 4, B-C = 5, C-E = 6, and A-C = 7.

Sort the edges by increasing weight, then process them in that order:

1. Take A-B (1). The new component is {A, B}.

2. Take D-E (2). The new component is {D, E}.

3. Take B-E (3). It merges the two components into {A, B, D, E}.

4. Reject B-D (4). B and D are already connected, so adding it would close the cycle B-E-D.

5. Take B-C (5). This brings C into the tree.

The MST edges are A-B, D-E, B-E, and B-C. Its total weight is 1 + 2 + 3 + 5 = 11, and it has exactly V - 1 = 4 edges.

The cut property explains why each selected edge is safe: the lightest edge crossing a cut belongs to some MST. Prim starting from A selects A-B (1), B-E (3), E-D (2), and B-C (5), reaching the same total weight of 11.

Worked example 2: where greedy fails

Greedy coin change fails for denominations {1, 3, 4} and target 6. Choosing the largest coin first gives 4 + 1 + 1, which uses three coins. The optimum is 3 + 3, which uses only two. Largest-first greedy works for canonical systems such as Indian currency, but the general coin-change problem needs dynamic programming.

For the 0/1 knapsack variant, the items are A(10, 60), B(20, 100), and C(30, 120), the capacity is W = 50, and fractions are forbidden. Ratio-greedy takes A and B, producing weight 30 and value 160. C cannot fit in the remaining capacity because it weighs 30. The optimal 0/1 choice is B + C, with weight 20 + 30 = 50 and value 100 + 120 = 220. Greedy loses 220 - 160 = 60 units of value.

For state design, memoization, tabulation, and a cell-by-cell 0/1 table, use Dynamic Programming in Algorithms: Complete Guide with Worked Examples for GATE and Interviews. Greedy reasoning asks a different question: can the local choice survive an exchange argument?

Use this decision rule: if choices are irrevocable and an exchange argument proves that the local choice can appear in an optimal solution, greedy is justified. If a locally attractive choice can block a better combination, keep alternatives and use dynamic programming.

How GATE and interviews test greedy algorithms

The official GATE 2027 Computer Science and Information Technology syllabus lists greedy algorithms under Algorithms. Questions commonly ask for an MST weight or the number of distinct MSTs, the correct activity-selection criterion, a Huffman code length, or Dijkstra's settled order.

Huffman coding can be worked through by repeatedly merging the two lowest frequencies. Let frequencies be a = 45, b = 13, c = 12, d = 16, e = 9, and f = 5, totalling 100. The merge order is 5 + 9 = 14, 12 + 13 = 25, 14 + 16 = 30, 25 + 30 = 55, and 45 + 55 = 100. The resulting depths are 1 for a, 3 for b, c, and d, and 4 for e and f. Therefore:

Weighted average length = (45 x 1 + 13 x 3 + 12 x 3 + 16 x 3 + 9 x 4 + 5 x 4) / 100 = 224 / 100 = 2.24 bits per symbol.

Interviewers often ask you to justify the greedy choice with an exchange argument or construct a failure case. Interval scheduling and meeting-room variants test whether you understand the criterion instead of sorting by a familiar field.

Greedy algorithm traps that cost marks

• Wrong activity order: Earliest start time or shortest duration is not the activity-selection rule. One long activity can begin first yet overlap two shorter compatible activities, so earliest finish time wins.

• Negative edges in Dijkstra: Its correctness is guaranteed only for non-negative edge weights. A negative edge can make a settled distance improve later.

• Assuming every MST is unique: Distinct edge weights guarantee a unique MST. Repeated weights can permit multiple MSTs.

• Mixing knapsack variants: Fractional knapsack supports the ratio proof and gives 240 above. In 0/1 knapsack, the same ratio rule gives 160 when the optimum is 220.

• Ignoring union-find: Quoting O(E log E) for Kruskal while checking connectivity with a slow full scan describes a different implementation. Union-find keeps cycle checks efficient.

The short version, and your next step

Greedy means committing to the local best choice without revisiting it. It is correct only when the greedy-choice property and optimal substructure hold. Remember the canonical six problems, the MST weight 11, and the 0/1 knapsack contrast of 160 versus 220. When unsure, try to make the exchange argument precise. If it breaks, dynamic programming is the safer direction.

Revise greedy within the full Algorithms coverage of Zero to Hero: Complete CS Course, then pressure-test it with topic-wise algorithm mocks in the GATE Test Series: Mocks & Topic-wise Tests. Use the GATE CS subject weightage guide to budget revision time. The binary trees and binary search trees guide is a useful next read because heaps and tree structures underpin Huffman and Prim.