retagged by
5,506 views
26 votes
26 votes

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.} & \text{Floyd-Warshall algorithm for all pairs shortest path} & \text{ii.}& \text{ Greedy method} \\\hline  \text{R.} & \text{ Merge sort  } & \text{iii.} & \text{ Dynamic programming} \\\hline  \text{S.}&  \text{Hamiltonian circuit  } & \text{iv.} & \text{  Divide and conquer} \\\hline \end{array}$$

  1. $\text{P-iii, Q-ii, R-iv, S-i}$
  2. $\text{P-i, Q-ii, R-iv, S-iii}$
  3. $\text{P-ii, Q-iii, R-iv, S-i}$
  4. $\text{P-ii, Q-i, R-iii, S-iv}$
retagged by

4 Answers

Best answer
16 votes
16 votes
1 votes
1 votes
(1) Prim's algo for mst is application of greedy which give optimal solution as mst .

(2) Floyd warshall algo for all pair shortest path is application of dynamic programming because it covers all possibilities from every vertex

(3)merge sort --divide and conquer

(4) Hamiltonian circuit is application of backtracking because we have to find cycle again and again until we didn't get cycle of all vertices without repetition of vertices except source vertex.
0 votes
0 votes

A)P. Prim's algorithm for minimum spanning tree  ----->ii.  Greedy method

Q. Floyd-Warshall algorithm for all pairs shortest paths------>iii. Dynamic programming

R. Mergesort ----->iv.  Divide and conque.

S. Hamiltonian circuit    ---->i.   Backtracking

0 votes
0 votes

C is answer

Explanation

Prim's algo. always chooses minimum adj. edge using greedy techneque.

Floyd is a dynamic programming techneque.

Merge is a divide & conqure as we first divide the given array till single element and then merge them in single sorted array.

Hamiltoninan uses back tracking.

P-2

Q-3

R-4

S-1

Answer:

Related questions

25 votes
25 votes
3 answers
1
go_editor asked Feb 12, 2015
6,927 views
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 a...
21 votes
21 votes
3 answers
2
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.} & \...
25 votes
25 votes
7 answers
3
khushtak asked Feb 14, 2017
6,938 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
4
makhdoom ghaya asked Nov 19, 2016
5,830 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 (...