Project ForgeMatch 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
- AP-iii, Q-ii, R-iv, S-i
- BP-i, Q-ii, R-iv, S-iii
- P-ii, Q-iii, R-iv, S-i
- DP-ii, Q-i, R-iii, S-iv
Explanation
Prim's algorithm is a classic GREEDY method (always picks the cheapest edge extending the tree). Floyd-Warshall is DYNAMIC PROGRAMMING (builds up all-pairs shortest paths via intermediate-vertex subproblems). Mergesort is DIVIDE AND CONQUER (splits, recursively sorts, merges). Finding a Hamiltonian circuit is a classic BACKTRACKING search problem. So P-ii, Q-iii, R-iv, S-i.
Source: GATE CS 2015 (Session 1 / 7th Feb Shift 1) (2015)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.