Skip to content
GATETECH
Official PYQ · 2017Set 1 · Q05Algorithm Design: Greedy TechniquesMCQ1 mark

GATE CS 2017 Set 1 Q05 — Algorithm Design: Greedy Techniques

Explain with AI

Consider the following table:

AlgorithmsDesign Paradigms(P)Kruskal(i)Divide and Conquer(Q)Quicksort(ii)Greedy(R)Floyd-Warshall(iii)Dynamic Programming\begin{array}{|ll|ll|}\hline & \textbf{Algorithms} & & \textbf{Design Paradigms} \\ \hline \text{(P)} & \text{Kruskal} & \text{(i)}& \text{Divide and Conquer} \\ \hline \text{(Q)}& \text{Quicksort} & \text{(ii)} & \text{Greedy} \\ \hline \text{(R)} & \text{Floyd-Warshall} &\text{(iii)} & \text{Dynamic Programming} \\ \hline \end{array}

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

Choose one option
View worked solution

Answer: C

To find the correct match, let us analyze the design paradigm of each algorithm:

  • (P) Kruskal's Algorithm: This algorithm finds the Minimum Spanning Tree (MST) of a connected, weighted graph by greedily selecting the minimum weight edge that does not form a cycle.
      ⟹  (P)↔(ii) Greedy\implies \text{(P)} \leftrightarrow \text{(ii) Greedy}

  • (Q) Quicksort: This sorting algorithm works by partitioning an array into two sub-arrays around a pivot element, and then recursively sorting the sub-arrays. This is a classic example of splitting a problem into smaller subproblems.
      ⟹  (Q)↔(i) Divide and Conquer\implies \text{(Q)} \leftrightarrow \text{(i) Divide and Conquer}

  • (R) Floyd-Warshall Algorithm: This algorithm computes the shortest paths between all pairs of vertices in a weighted graph. It builds the solution bottom-up by utilizing optimal substructure and overlapping subproblems.
      ⟹  (R)↔(iii) Dynamic Programming\implies \text{(R)} \leftrightarrow \text{(iii) Dynamic Programming}

Combining these matches, we get:

(P)↔(ii),(Q)↔(i),(R)↔(iii)\text{(P)} \leftrightarrow \text{(ii)}, \quad \text{(Q)} \leftrightarrow \text{(i)}, \quad \text{(R)} \leftrightarrow \text{(iii)}

Hence, the correct option is C.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Algorithm Design: Greedy Techniques questions