Skip to content
GATETECH
Official PYQ · 2015Set 1 · Q6Algorithm Design: Greedy TechniquesMCQ1 mark

GATE CS 2015 Set 1 Q6 — Algorithm Design: Greedy Techniques

Explain with AI

Match the following:
P.Prim’s algorithm for minimum spanning treei.BacktrackingQ.Floyd-Warshall algorithm for all pairs shortest pathii. Greedy methodR. Merge sort iii. Dynamic programmingS.Hamiltonian circuit iv. Divide and conquer\begin{array}{|ll|ll|}\hline \text{P.} & \text{Prim's algorithm for minimum spanning tree} & \text{i.} & \text{Backtracking} \\ \hline \text{Q.} & \text{Floyd-Warshall algorithm for all pairs shortest path} & \text{ii.}& \text{ Greedy method} \\ \hline \text{R.} & \text{ Merge sort } & \text{iii.} & \text{ Dynamic programming} \\ \hline \text{S.}& \text{Hamiltonian circuit } & \text{iv.} & \text{ Divide and conquer} \\ \hline \end{array}

Choose one option
View worked solution

Answer: C

To find the correct match, let us analyze the design paradigm used by each algorithm:

  • P. Prim's algorithm for minimum spanning tree: It grows the minimum spanning tree by greedily choosing the cheapest edge that connects a vertex in the tree to a vertex outside the tree.
    →\rightarrow ii. Greedy method
  • Q. Floyd-Warshall algorithm for all-pairs shortest path: It computes shortest paths between all pairs of vertices by utilizing solutions to smaller subproblems (using intermediate vertices 11 to kk).
    →\rightarrow iii. Dynamic programming
  • R. Merge sort: It recursively splits the array into two halves, sorts each half, and then merges the sorted halves.
    →\rightarrow iv. Divide and conquer
  • S. Hamiltonian circuit: Finding a Hamiltonian circuit is an NP-complete problem. The standard systematic search space exploration involves trying paths and backtracking when a dead end is reached.
    →\rightarrow i. Backtracking

Combining these matches, we get:

P-ii, Q-iii, R-iv, S-i\text{P-ii, Q-iii, R-iv, S-i}

Hence, the correct option is C.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Algorithm Design: Greedy Techniques questions