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

Matching the algorithms to their corresponding design paradigm:

• (P) Prim's algorithm for minimum spanning tree: It iteratively selects the minimum-weight edge connecting the tree to a vertex outside the tree, which is a Greedy method$\rightarrow$(ii).

• (Q) Floyd-Warshall algorithm for all pairs shortest paths: It computes shortest paths by systematically considering all intermediate vertices via Dynamic programming$\rightarrow$(iii).

• (R) Mergesort: It divides the array into two halves, sorts them recursively, and merges the sorted halves using the Divide and conquer paradigm $\rightarrow$ (iv).

• (S) Hamiltonian circuit: Finding a Hamiltonian circuit is an NP-complete problem, commonly solved systematically via state-space search with Backtracking$\rightarrow$(i).

Thus, the correct matching is P-ii, Q-iii, R-iv, S-i, which corresponds to option (C).