GATE CS 2015 Set 1 — Question 13

MCQ+1 / -0.33EasyPrim's MSTGreedy AlgorithmsAlgorithmsFloyd-WarshallDynamic ProgrammingMerge Sort (D&C)Divide & Conquer

Algorithms → Divide & Conquer → Floyd-Warshall

Last updated 5 September 2026

Question

Match the following: Algorithm Design Paradigm (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

Algorithm	Design Paradigm
(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

Correct answer (C) P-ii, Q-iii, R-iv, S-i Solution The correct matching is: Prim's algorithm uses the Greedy method to build a Minimum Spanning Tree (MST). Floyd-Warshall algorithm uses Dynamic programming to find all-pairs shortest paths. Mergesort is a classic example of the Divide and conquer paradigm. Finding a Hamiltonian circuit is an NP-complete problem often solved using Backtracking . Thus, the matching is P-ii, Q-iii, R-iv, S-i. Turn this into a strength. Explore AI-powered practice and doubt support with Success Tracker.

Review answer and solution without JavaScript

Interactive answer checking needs JavaScript. The published solution is available below.

Correct answer (C) P-ii, Q-iii, R-iv, S-i Solution The correct matching is: Prim's algorithm uses the Greedy method to build a Minimum Spanning Tree (MST). Floyd-Warshall algorithm uses Dynamic programming to find all-pairs shortest paths. Mergesort is a classic example of the Divide and conquer paradigm. Finding a Hamiltonian circuit is an NP-complete problem often solved using Backtracking . Thus, the matching is P-ii, Q-iii, R-iv, S-i.

Continue learning with Success Tracker

Use Success Tracker to ask about the reasoning, then try another GATE CS question to check your understanding.

AI-powered practice· Unlimited practice on eligible plans

PYQs with solutions: Attempt available previous-year questions, then compare your reasoning with the worked solution. Coverage varies by stream.
Practice that adapts: Choose a topic, work on weaker areas and bookmark questions to revisit. Your attempts feed your progress tracking.
AI doubt support: Ask follow-up questions about a step or concept while practising, instead of stopping at the final answer.

Unlimited practice is available on eligible plans. Free practice and AI usage have limits; check the current plan allowances before choosing.

This page stays readable without an account. AI responses can be wrong; check them against the solution and source material.