GATE CSE 2017 Set 1 | Question: 05

Question

Consider the following table:

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

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)$

Answer 1

Answer will be Option C .

Quicksort is a divide and conquer technique.
while Kruskal algorithms work to find the minimum weight so it takes a greedy approach .
Floyd Warshell for all-pair shortest path uses Dynamic programming with a time complexity o(n3).

Answer 2

(P) Kruskal’s and Prim’s algorithms for finding Minimum Spanning Tree(MST). To find MST we are using greedy technique.
(Q) QuickSort is a Divide and Conquer algorithm.
(R) Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem using Dynamic Programming.

Answer 3

Some important points regarding Greedy Vs Dynamic Programming
Greedy: →
It always gives polynomial time complexity
→ It is not an optimal
→ It always selects only either minimum or maximum among all possibilities
→ Ex: Dijkstra’s algorithm for SSSP, Optimal Merge Pattern, Huffman coding, Fractional knapsack problem, etc..,
Dynamic Programming:
→ It gives either polynomial or exponential time complexity.
→ It gives always an optimal result.
→ It checks all possibilities of a problem.
→ Ex: Longest Common sequence, Matrix chain Multiplication, Travelling sales Problem, etc..,