The Gateway to Computer Science Excellence

+21 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}$$

- $\text{P-iii, Q-ii, R-iv, S-i}$
- $\text{P-i, Q-ii, R-iv, S-iii}$
- $\text{P-ii, Q-iii, R-iv, S-i}$
- $\text{P-ii, Q-i, R-iii, S-iv}$

+13 votes

Best answer

P. Prim - ii. Greedy

http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/

Q. Floyd Warshall - iii. Dynamic

http://www.geeksforgeeks.org/dynamic-programming-set-16-floyd-warshall-algorithm/

R. Merge Sort - iv. Divide & Conquer

http://www.geeksforgeeks.org/merge-sort/

S. Hamiltonian Circuit - i. Backtracking

http://www.geeksforgeeks.org/backtracking-set-7-hamiltonian-cycle/

Option is $C$.

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

(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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,321 answers

198,395 comments

105,145 users