UPPCL AE 2018:12

Question

Given below are some famous algorithms and some algorithm design paradigms

$$\begin{array} {|l|l|} \hline \qquad \qquad  \qquad \textbf{Algorithms} & \textbf{Design Paradigms} \\\hline \text{1. Dijkstra’s shortest path algorithm} & \text{(a) Greedy design} \\\hline \text{2. Floyd Warshall’s all-pair-shortest path algorithm} & \text{(b) Divide and conquer} \\\hline \text{3. Kruskal’s minimum spanning tree algorithm} & \text{(c) Dynamic programming} \\\hline \text{4. Merge Sort algorithm} & \\\hline \end{array}$$

Which of the following correspondence is correct?

• A. $\text{1-(a), 2-(c), 3-(a), 4-(b)}$
• B. $\text{1-(a), 2-(b), 3-(a), 4-(c)}$
• C. $\text{1-(a), 2-(b), 3-(c), 4-(c)}$
• D. $\text{1-(c), 2-(b), 3-(a), 4-(b)}$

Answer 1

• Dijkstra’s shortest path $\rightarrow$  greedy approach. (Greedy algorithm)
• Floyd warshall all pair shortest path $\rightarrow$  dynamic programming.
• Kruskal’s minimum spanning tree $\rightarrow$  greedy algorithm.
• merge sort $\rightarrow$ divide and conquer technique.

Option $(A)$ is correct.