retagged by
6,925 views
25 votes
25 votes

Given below are some algorithms, and some algorithm design paradigms.$$\begin{array}{ll|ll}\hline \text{1.} & \text{Dijkstra's Shortest Path} & \text{i.} & \text{Divide and Conquer} \\\hline  \text{2.} & \text{Floyd-Warshall algorithm to compute} & \text{ii.}& \text{Dynamic Programming} \\& \text{ all pairs shortest path} \\\hline   \text{3.}& \text{Binary search on a sorted array} & \text{iii.}  & \text{Greedy design} \\\hline  \text{4.} & \text{Backtracking search on a graph} &\text{iv.}  & \text{Depth-first search} \\\hline  &  &\text{v.}  & \text{Breadth-first search}  \\\hline \end{array}$$
Match the above algorithms on the left to the corresponding design paradigm they follow.

  1. $\text{1-i, 2-iii, 3-i, 4-v}$
  2. $\text{1-iii, 2-iii, 3-i, 4-v}$
  3. $\text{1-iii, 2-ii, 3-i, 4-iv}$
  4. $\text{1-iii, 2-ii, 3-i, 4-v}$
retagged by

3 Answers

Best answer
23 votes
23 votes
Option C.

Dijkstra's Shortest path algorithm uses greedy design (always chosing the shortest neighbour) while Floyd Warshall Algorithm to compute all shortest paths uses Dynamic Programming.
Binary search uses Divide and Conquer (though we eliminate one part at each time) and Back tracking traversal to a graph uses Depth First Search (DFS) (in DFS we have to backtrack to a node after searching through all its descendant nodes if the searched node is not found).
selected by
21 votes
21 votes
Answer: C
0 votes
0 votes
I feel its D. We start with the destination node and backtrack in breadth First manner. We don't reach to the starting node in Depth first manner... But evaluating the shortest Path at each level. Which is BFS clearly.
IDK why everybody.. ACE, ME and GateCse wrote that as C...!
Open for criticism.
Answer:

Related questions

25 votes
25 votes
7 answers
1
khushtak asked Feb 14, 2017
6,937 views
Consider the following table:$$\begin{array}{|l|}\hline \textbf {Algorithms} & \textbf{Design Paradigms } & \\\hline \text{P. Kruskal} & \text{i. Divide and Conquer} \...
11 votes
11 votes
1 answer
2
makhdoom ghaya asked Nov 19, 2016
5,829 views
Match the pairs in the following questions:$$\begin{array}{|ll|ll|}\hline (a) & \text{Strassen's matrix multiplication algorithm} & (p) & \text{Greedy method} \\\hline (...
21 votes
21 votes
3 answers
3
Kathleen asked Sep 29, 2014
4,970 views
The correct matching for the following pairs is$$\begin{array}{ll|ll}\hline \text{A.} & \text{All pairs shortest path} & \text{1.} & \text{Greedy} \\\hline \text{B.} & \...
26 votes
26 votes
4 answers
4
makhdoom ghaya asked Feb 12, 2015
5,506 views
Match the following:$$\begin{array}{|ll|ll|}\hline \text{P.} & \text{Prim's algorithm for minimum spanning tree} & \text{i.} & \text{Backtracking} \\\hline \text{Q.}...