UGC NET CSE | December 2018 | Part 2 | Question: 27

Question

Match $\text{List I}$ with $\text{List II}$ and choose the correct answer from the code given below.

$\begin{array} {clcl}   & \textbf{List I} &  & \textbf{List II} \\ & \textbf{(Graph Algorithm)} & & \textbf{(Time Complexity)} \\ \text{(a)} & \text{Dijkstra’s algorithm} & \text{(i)}& O(E \: lg \: E) \\ \text{(b)}& \text{Kruskal’s algorithm} & \text{(ii)}& \Theta(V^3) \\ \text{(c)} & \text{Floyd-Warshall algorithm} & \text{(iii)} & O(V^2) \\ \text{(d)} & \text{Topological sorting} & \text{(iv)}& \Theta(V+E) \\ \end{array}$

where $V$ and $E$ are the number of vertices and edged in graph respectively.

$\textbf{Code :}$

• A. $\text{(a)-(i), (b)-(iii), (c)-(ii), (d)-(iv)}$
• B. $\text{(a)-(iii), (b)-(i), (c)-(ii), (d)-(iv)}$
• C. $\text{(a)-(i), (b)-(iii), (c)-(iv), (d)-(ii)}$
• D. $\text{(a)-(iii), (b)-(i), (c)-(iv), (d)-(ii)}$

Answer 1

Answer B

Dijjkstra    v^2

Kruskals    Eloge

Floyd warshall .  V^3