GATE CS 2015 Set 1 Q.16 (CS Q.6): Greedy Algorithms

Match the following:

	Algorithm		Design Paradigm
(P)	Prim's algorithm for minimum spanning tree	(i)	Backtracking
(Q)	Floyd-Warshall algorithm for all pairs shortest paths	(ii)	Greedy method
(R)	Mergesort	(iii)	Dynamic programming
(S)	Hamiltonian circuit	(iv)	Divide and conquer

P-iii, Q-ii, R-iv, S-i

P-i, Q-ii, R-iv, S-iii

P-ii, Q-iii, R-iv, S-i

P-ii, Q-i, R-iii, S-iv

Official answer and solution

Solution

Classify each standard computer science algorithm into its foundational algorithmic design strategy.

Matching each algorithm:

(P) Prim's algorithm: Grows a minimum spanning tree edge by edge by choosing the minimum-weight crossing edge at each step. This is a Greedy method (ii).
(Q) Floyd-Warshall algorithm: Computes all-pairs shortest paths using subproblems with intermediate vertices up to $k$ . This is Dynamic programming (iii).
(R) Mergesort: Recursively splits an array into halves, sorts them, and merges the sorted halves. This is Divide and conquer (iv).
(S) Hamiltonian circuit: Finds a tour visiting every vertex exactly once by searching state space trees and pruning invalid paths. This is Backtracking (i).

Correct matching: P-ii, Q-iii, R-iv, S-i (option C).

Final answer

Common trap

Classifying Floyd-Warshall as greedy or divide-and-conquer rather than dynamic programming.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.