GATE CSE 2017 | Set 1 | Question: 05

Question

Consider the following table:

$$\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.

• 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

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..,