UGC NET CSE | October 2020 | Part 2 | Question: 70

Question

Match $\text{list I}$ with $\text{List II}$

$\begin{array}{llll} & \text{List I} && \text{List II} \\ (A) & \text{Topological sort of DAG} & (I) & O(V+E) \\ (B) & \text{Kruskal’s MST algorithm} & (II) & O(VE) \\ (C) & \text{Bellman-Ford’s single-source shortest} & (III) & \theta (V+E) \\ & \text{path algorithm} \\ (D) & \text{Floyd-Warshall’s all pair shortest}  & (IV) & \theta (V^3) \\ & \text{path algorithm}  \end{array}$

Choose the correct answer from the options given below:

• A. $\text{A-I, B-III, C-IV, D-II}$
• B. $\text{A-III, B-I, C-IV, D-II}$
• C. $\text{A-III, B-I, C-II, D-IV}$
• D. $\text{A-I, B-III, C-II, D-IV}$

 

Answer 1

3 matches are straightforward 

• A. Topological sort of DAG :- θ(V+E) 

• A. Bellman-Ford’s single-source shortest path algorithm :- O(V*E)

100. Floyd-Warshall’s all pair shortest path algorithm :- θ($V^{3}$)

Now, Kruskal’s MST algo left in left side and in right side O(V+E) left. Can it possible ? 

Yes, How? Lets see..

The dominate term in Kruskal’s time complexity is O(ElogE) due to sorting the edges , But, if we can performing sorting in linear time or edges are already sorted then this problem will reduced to detecting if there is a cycle in the graph or not.

 Since edges are already sorted, take each edge one by one and add to MST (if no cycle is formed).

Now, detecting whether an undirected graph has a cycle or not can be done :- 

1) Either using DFT or BFT :- O(V+E)

2)Using Union-Find :- O(ElogV)

So,  Kruskal’s MST algorithm :-  O(V+E)

 Thus, Correct matching is A−III,B−I,C−II,D−IV. 

Option (C) is answer.

Comments

Yes, there was a typo. Thanks for pointing it out.

Answer 2

option c  cleaarly  matching