search
Log In
21 votes
2.2k 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.} & \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}$
in Algorithms
edited by
2.2k views
14
option c is correct ..
1

Answer C its  Basic General Queston

4 Answers

14 votes
1 vote
(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

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

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

19 votes
3 answers
1
1.8k views
The correct matching for the following pairs is ... $\text{A-3 B-4 C-1 D-2}$ $\text{A-3 B-4 C-2 D-1}$ $\text{A-4 B-1 C-2 D-3}$
asked Sep 29, 2014 in Algorithms Kathleen 1.8k views
38 votes
3 answers
2
4.3k views
Let a$_{n}$ represent the number of bit strings of length n containing two consecutive $1$s. What is the recurrence relation for $a_{n}$? $a_{n - 2} + a_{n - 1} + 2^{n - 2}$ $a_{n - 2} + 2a_{n - 1} + 2^{n - 2}$ $2a_{n - 2} + a_{n - 1} + 2^{n - 2}$ $2a_{n - 2} + 2a_{n - 1} + 2^{n - 2}$
asked Feb 13, 2015 in Algorithms makhdoom ghaya 4.3k views
30 votes
8 answers
3
6.5k views
Let $G = (V, E)$ be a simple undirected graph, and $s$ be a particular vertex in it called the source. For $x \in V$, let $d(x)$ denote the shortest distance in $G$ from $s$ to $x$. A breadth first search (BFS) is performed starting at $s$. Let $T$ ... of $G$ that is not in $T$, then which one of the following CANNOT be the value of $d(u) - d(v)$? $-1$ $0$ $1$ $2$
asked Feb 13, 2015 in Algorithms makhdoom ghaya 6.5k views
53 votes
5 answers
4
7.4k views
The graph shown below has $8$ edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight $36$ and contains the edges: $\{(A, C), (B, C), (B, E), (E, F), (D, F)\}$. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all $8$ edges of this graph is_______________.
asked Feb 13, 2015 in Algorithms makhdoom ghaya 7.4k views
...