Match the following: (P) Prim’s algorithm for minimum spanning tree (i)…
2015
Match the following:
(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 |
- A.
P-iii, Q-ii, R-iv, S-i
- B.
P-i, Q-ii, R-iv, S-iii
- C.
P-ii, Q-iii, R-iv, S-i
- D.
P-ii, Q-i, R-iii, S-iv
Attempted by 199 students.
Show answer & explanation
Correct answer: C
Correct matching: Prim's → Greedy; Floyd–Warshall → Dynamic programming; Mergesort → Divide and conquer; Hamiltonian circuit → Backtracking.
Prim's algorithm — Greedy: it builds the minimum spanning tree by repeatedly choosing the smallest edge that connects a vertex in the tree to a vertex outside it (a locally optimal choice).
Floyd–Warshall algorithm — Dynamic programming: it finds all-pairs shortest paths by combining solutions for paths using intermediate vertices and updating distances iteratively.
Mergesort — Divide and conquer: it recursively splits the list into halves, sorts each half, and merges the sorted halves.
Hamiltonian circuit — Backtracking: finding a Hamiltonian cycle generally requires exploring permutations/paths and backing up when a partial path cannot be completed.
A video solution is available for this question — log in and enroll to watch it.