Consider the following table: P. Kruskal i. Divide and Conquer Q. Quicksort…
2017
Consider the following table:
P. Kruskal | i. Divide and Conquer |
Q. Quicksort | ii. Greedy |
R. Floyd–Warshall | iii. Dynamic Programming |
Match the algorithms to the design paradigms they are based on.
- A.
\((P) \leftrightarrow (ii), (Q) \leftrightarrow (iii), (R) \leftrightarrow (i)\) - B.
\((P) \leftrightarrow (iii), (Q) \leftrightarrow (i), (R) \leftrightarrow (ii)\) - C.
\((P) \leftrightarrow (ii), (Q) \leftrightarrow (i), (R) \leftrightarrow (iii)\) - D.
\((P) \leftrightarrow (i), (Q) \leftrightarrow (ii), (R) \leftrightarrow (iii)\)
Attempted by 236 students.
Show answer & explanation
Correct answer: C
Correct matching: P. Kruskal → Greedy; Q. Quicksort → Divide and Conquer; R. Floyd–Warshall → Dynamic Programming.
P. Kruskal — Greedy: Kruskal builds a minimum spanning tree by repeatedly choosing the smallest-weight edge that does not create a cycle. Each local choice is greedy and leads to an optimal global solution.
Q. Quicksort — Divide and Conquer: Quicksort partitions the array around a pivot and then recursively sorts the partitions, combining results to get the sorted array.
R. Floyd–Warshall — Dynamic Programming: Floyd–Warshall computes all-pairs shortest paths by considering intermediate vertices and using previously computed subproblems (it relies on a recurrence to build up solutions).
Therefore, the correct mapping is: P → Greedy, Q → Divide and Conquer, R → Dynamic Programming.
A video solution is available for this question — log in and enroll to watch it.