A solid reason would be helpful. Couldn't find much through a Google search..

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

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

18 votes

Best answer

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

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

21 votes

3

There is no algorithm called as a backtracking search on a graph as far as I know. However DFS backtracks to a node before exploring a particular depth. But such backtracking(similar not same) happens in BFS as well.(please refer BFS article from Wikipedia )

A solid reason would be helpful. Couldn't find much through a Google search..

A solid reason would be helpful. Couldn't find much through a Google search..

1

I dont find that command useful ... fr me Going to another tab while solving a question is irritating ...

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.

IDK why everybody.. ACE, ME and GateCse wrote that as C...!

Open for criticism.