GATE CS 2017 Set 1 Q.5 (CS Q.5): Greedy Algorithms

Consider the following table:

Match the algorithms to the design paradigms they are based on.

(P) - (ii), (Q) - (iii), (R) - (i)

(P) - (iii), (Q) - (i), (R) - (ii)

(P) - (ii), (Q) - (i), (R) - (iii)

(P) - (i), (Q) - (ii), (R) - (iii)

Official answer and solution

Solution

Identify the foundational algorithmic design paradigm used by each of the given classic algorithms.

Examine the algorithms one by one:

Kruskal's algorithm: It finds a Minimum Spanning Tree (MST) by sorting all edges by weight and greedily picking the smallest edge that does not form a cycle. Hence, Kruskal is based on the Greedy design paradigm $\implies$ (P) matches (ii).
Quicksort: It picks a pivot element, partitions the array into sub-arrays of elements smaller and larger than the pivot, and recursively sorts the sub-arrays. Hence, Quicksort is based on the Divide and Conquer paradigm $\implies$ (Q) matches (i).
Floyd-Warshall algorithm: It computes all-pairs shortest paths by iteratively considering each intermediate vertex as a possible shortcut, storing and reusing solutions to subproblems in a matrix. Hence, Floyd-Warshall is based on Dynamic Programming $\implies$ (R) matches (iii).

Combining these matches gives (P) - (ii), (Q) - (i), (R) - (iii), which is Option C.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.