# GATE1997-1.5

1.9k 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.} & \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}$$

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

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

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

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

edited
10

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

edited
0
We can find  MST using BFS /greedy not DFS but yes we can find connected components using DFS
0
please explain the concept of " connected component" ..?
0
1 vote
1- All pair shortest path ------> dynamic programing

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

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

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

A-3

B-4

C-1

D-2

## Related questions

1
2.3k views
Match the following: ... $\text{P-ii, Q-iii, R-iv, S-i}$ $\text{P-ii, Q-i, R-iii, S-iv}$
Consider the following function. Function F(n, m:integer):integer; begin If (n<=0 or (m<=0) then F:=1 else F:F(n-1, m) + F(n, m-1); end; Use the recurrence relation ... What is the value of $F(n, m)$? How many recursive calls are made to the function $F$, including the original call, when evaluating $F(n, m)$.
Consider a graph whose vertices are points in the plane with integer co-ordinates $(x,y)$ such that $1 \leq x \leq n$ and $1 \leq y \leq n$, where $n \geq 2$ is an integer. Two vertices $(x_1, y_1)$ and $(x_2, y_2)$ are adjacent ... ? Write only the answer without any explanations. What is the weight of a maximum weight-spanning tree in this graph? Write only the answer without any explanations.
Let $T(n)$ be the function defined by $T(1) =1, \: T(n) = 2T (\lfloor \frac{n}{2} \rfloor ) + \sqrt{n}$ for $n \geq 2$. Which of the following statements is true? $T(n) = O \sqrt{n}$ $T(n)=O(n)$ $T(n) = O (\log n)$ None of the above