The GATE Grind

GATE 2015 CS – Question 13

Algorithms · Greedy Techniques · 1 mark · Multiple choice

Match the following:

(P) Prim's algorithm for minimum spanning tree

(Q) Floyd-Warshall algorithm for all pairs shortest paths

(R) Mergesort

(S) Hamiltonian circuit

(i) Backtracking

(ii) Greedy method

(iii) Dynamic programming

(iv) Divide and conquer

  1. P-iii, Q-ii, R-iv, S-i
  2. P-i, Q-ii, R-iv, S-iii
  3. P-ii, Q-iii, R-iv, S-i
  4. P-ii, Q-i, R-iii, S-iv

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) P-ii, Q-iii, R-iv, S-i

Explanation

Prim's algorithm repeatedly takes the cheapest edge, so it is greedy. Floyd-Warshall builds shortest paths from smaller subproblems, so it is dynamic programming. Mergesort splits and merges, so it is divide and conquer. Finding a Hamiltonian circuit is done by trying paths and backing out of dead ends, so it is backtracking.