Log In
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.

  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}$
in Algorithms
edited by

3 Answers

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

selected by
21 votes
Answer: C
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..
backtracking happens for DFS , not for BFS
I dont find that command useful ... fr me Going to another tab while solving a question is irritating ...

@srestha could you please provide standard reference to your answer. It will really be helpful  coz I am not getting it HOW

U can follow any standard book, will get  it
ya got it. Didn't read the que properly. It is asked just for graph search and I was thinking about all algorithms using bfs and dfs. Thank you.
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.

read this link may be it will help you DFS is actually a backtracking..a kind of subset you can say..


Related questions

40 votes
6 answers
An unordered list contains $n$ distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is $\Theta(n \log n)$ $\Theta(n)$ $\Theta(\log n)$ $\Theta(1)$
asked Feb 12, 2015 in Algorithms jothee 7k views
14 votes
2 answers
Consider two decision problems $Q_1, Q_2$ such that $Q_1$ reduces in polynomial time to 3-SAT and 3-SAT reduces in polynomial time to $Q_2$. Then which one of the following is consistent with the above statement? $Q_1$ is in NP, $Q_2$ is NP hard. $Q_2$ is in NP, $Q_1$ is NP hard. Both $Q_1$ and $Q_2$ are in NP. Both $Q_1$ and $Q_2$ are in NP hard.
asked Feb 12, 2015 in Theory of Computation jothee 2.6k views
22 votes
4 answers
Match the following: ... $\text{P-ii, Q-iii, R-iv, S-i}$ $\text{P-ii, Q-i, R-iii, S-iv}$
asked Feb 12, 2015 in Algorithms makhdoom ghaya 2.3k views
37 votes
4 answers
In a connected graph, a bridge is an edge whose removal disconnects the graph. Which one of the following statements is true? A tree has no bridges A bridge cannot be part of a simple cycle Every edge of a clique with size $\geq 3$ is a bridge (A clique is any complete subgraph of a graph) A graph with bridges cannot have cycle
asked Feb 13, 2015 in Graph Theory jothee 4.8k views