GATE CSE 1997 | Question: 1.5

Question

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.} & \text{Quick Sort} & \text{2.}& \text{Depth-First Search} \\\hline   \text{C.}& \text{Minimum weight spanning tree} & \text{3.}  & \text{Dynamic Programming} \\\hline  \text{D.} & \text{Connected Components} &\text{4.}  & \text{Divide and Conquer}  \\\hline \end{array}$$

• A. $\text{A-2 B-4 C-1 D-3}$

• B. $\text{A-3 B-4 C-1 D-2}$

• C. $\text{A-3 B-4 C-2 D-1}$

• D. $\text{A-4 B-1 C-2 D-3}$

Comments

answer B

Answer 1

Answer : (B) A-3 B-4 C-1 D-2$$\begin{array}{|ll|ll|}\hline \text{A.} & \text{All pairs shortest path} & \text{3.} & \text{Dynamic Programming} \\\hline  \text{B.} & \text{Quick Sort} & \text{2.}& \text{Divide and Conquer} \\\hline   \text{C.}& \text{Minimum weight spanning tree} & \text{1.}  & \text{Greedy} \\\hline  \text{D.} & \text{Connected Components} &\text{2.}  & \text{Depth-First Search}  \\\hline \end{array}$$

Reference: Read the Intro/Algo Sub-Heading.

• https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#History_and_naming
• https://en.wikipedia.org/wiki/Quicksort#Algorithm
• https://en.wikipedia.org/wiki/Minimum_spanning_tree#Algorithms
• https://en.wikipedia.org/wiki/Connected_component_(graph_theory)#Algorithms

Comments

We can find  MST using BFS /greedy not DFS but yes we can find connected components using DFS

---

please explain the concept of " connected component" ..?

---

air1ankit https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/

---

already done ... thanks ;

Answer 2

1- All pair shortest path ------> dynamic programing

2-quick sort --------> divide and conquer

3-MST ----------->Greedy technique

4- connected component ------>Depth-First search

 

*Answer will be "b"

Answer 3

A-3

B-4

C-1

D-2