GATE CS 2017 Set 1 — Question 5
Go beyond PYQs with Success TrackerAI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply.MCQ+1 / -0.33EasyKruskal's MSTGreedy AlgorithmsAlgorithmsFloyd-WarshallDynamic ProgrammingQuick Sort (D&C)Divide & Conquer
Algorithms → Divide & Conquer → Floyd-Warshall
Last updated
Question
Consider the following table:
Match the algorithms to the design paradigms they are based on.
| Algorithms | Design Paradigms |
|---|---|
| (P) Kruskal | (i) Divide and Conquer |
| (Q) Quicksort | (ii) Greedy |
| (R) Floyd-Warshall | (iii) Dynamic Programming |
Correct answer
(C) (P) rightarrow (ii), (Q) rightarrow (i), (R) rightarrow (iii)
Solution
The correct matching is based on the design paradigms of the algorithms:
1.(P) Kruskal's Algorithm: This algorithm is used for finding the Minimum Spanning Tree (MST) of a graph. It works by sorting edges by weight and iteratively adding the smallest edge that doesn't form a cycle. This local optimal choice at each step characterizes the Greedy approach. Hence, (P) matches with (ii).
2.(Q) Quicksort: This sorting algorithm works by selecting a pivot element and partitioning the array into two sub-arrays (elements less than the pivot and elements greater than the pivot), then recursively sorting the sub-arrays. This breaking down of a problem into sub-problems is the Divide and Conquer paradigm. Hence, (Q) matches with (i).
3.(R) Floyd-Warshall Algorithm: This algorithm finds all-pairs shortest paths in a weighted graph. It constructs the solution bottom-up by considering shortest paths using an increasing set of intermediate vertices. This approach of solving sub-problems and storing their results is Dynamic Programming. Hence, (R) matches with (iii).
Thus, the correct correspondence is (P) (ii), (Q) (i), (R) (iii).Continue learning with Success Tracker
A step still unclear? Work through it with support
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.
More questions on Divide & Conquer
2026 Set 1 Q17Consider the following recurrence relations: For all ,…2026 Set 2 Q24Consider the following functions, where is a positive integer.…2026 Set 2 Q25Which of the following can be recurrence relation(s) corresponding to an algorithm with time…2026 Set 2 Q32Consider an array . Suppose the merge sort algorithm is…2026 Set 2 Q37Let be a weighted directed acyclic graph with edges and vertices. Given and a…