Greedy Technique – GATE CSE AlgorithmsPractice Questions & PYQs

Kruskal's: greedy - always picks the cheapest edge not forming a cycle. Huffman: greedy - always merges the two nodes with smallest frequency. Dijkstra's: greedy - always selects the unvisited vertex with minimum distance estimate. Bellman-Ford: NOT greedy - it uses dynamic programming, relaxing all edges V-1 times in a systematic (non-greedy) fashion. It does not make a single locally optimal choice at each step.

Fractional Knapsack is solved optimally using greedy strategy.

The cut property states: for any cut (S, V-S) of a connected weighted graph with distinct edge weights, the minimum weight edge crossing the cut (having one endpoint in S and one in V-S) is in every MST. For non-distinct weights, it belongs to some MST. This property justifies both Prim's (each step adds the min-weight edge crossing the cut between visited and unvisited vertices) and Kruskal's (each accepted edge is the min-weight edge crossing some cut defined by the current forest components).

(i) FALSE: If edge weights are not unique, multiple MSTs may exist and the two algorithms may find different ones. (ii) TRUE: Prim's with adjacency matrix runs in O(V²) - efficient for dense graphs (E = O(V²)). Kruskal's runs in O(E log E) - efficient for sparse graphs where E << V². (iii) TRUE: Both are justified by the cut property - the minimum weight edge crossing any cut of the graph is in some MST. (iv) FALSE: Prim's does not need Union-Find (it uses a priority queue and visited array); Kruskal's uses Union-Find for cycle detection.

A: Correct - Huffman assigns longer codes to less frequent characters; merging the two smallest frequencies first pushes them deepest (longest code), minimizing total bits. B: Correct - the optimality proof uses an exchange argument: in any optimal tree, the two least frequent symbols can be assumed to be siblings at the deepest level (swapping only improves or maintains cost), validating the greedy choice. C: Correct - a direct consequence of the exchange argument proof. D: FALSE - Huffman trees are full binary trees (every internal node has exactly 2 children) but NOT necessarily complete binary trees.

0/1 Knapsack cannot be solved optimally by any greedy algorithm because it lacks the greedy choice property - taking the highest value-density item may prevent a better overall combination. A counterexample: items (v=10,w=5),(v=6,w=4),(v=6,w=4) with W=8. Greedy picks (v=10,w=5) then cannot fit others (total value 10), but optimal is (v=6)+(v=6)=12. All other options are solvable greedily: Activity Selection (earliest finish), Dijkstra's (minimum distance), Optimal Merge Pattern (always merge two smallest files).

The optimal greedy strategy for Activity Selection is to always pick the compatible activity with the earliest finish time. This leaves the maximum remaining time for future activities. Sorting by finish time and greedily picking the next compatible activity runs in O(n log n) and is provably optimal. Earliest start time and shortest duration are incorrect greedy choices that can fail to give the maximum number of activities.