The GATE Grind

GATE 2017 CS – Question 15

Algorithms · Greedy Techniques · 1 mark · Multiple choice

Consider the following table:

AlgorithmsDesign Paradigms
(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.

  1. (P) $\leftrightarrow$ (ii), (Q) $\leftrightarrow$ (iii), (R) $\leftrightarrow$ (i)
  2. (P) $\leftrightarrow$ (iii), (Q) $\leftrightarrow$ (i), (R) $\leftrightarrow$ (ii)
  3. (P) $\leftrightarrow$ (ii), (Q) $\leftrightarrow$ (i), (R) $\leftrightarrow$ (iii)
  4. (P) $\leftrightarrow$ (i), (Q) $\leftrightarrow$ (ii), (R) $\leftrightarrow$ (iii)

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) (P) $\leftrightarrow$ (ii), (Q) $\leftrightarrow$ (i), (R) $\leftrightarrow$ (iii)

Explanation

Kruskal's algorithm repeatedly takes the cheapest safe edge, so it is greedy. Quicksort splits the array around a pivot and sorts the parts, so it is divide and conquer. Floyd-Warshall builds shortest paths from smaller subproblems, so it is dynamic programming.