Match list I with II \(\begin{array}{llll} & \text{List I} && \text{List II}…
2020
Match list I with 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.
A-I, B-III, C-IV, D-II
- B.
A-III, B-I, C-IV, D-II
- C.
A-III, B-I, C-II, D-IV
- D.
A-I, B-III, C-II, D-IV
Attempted by 86 students.
Show answer & explanation
Correct answer: C
Correct time complexities:
Topological sort of a DAG: Θ(V+E).
Kruskal’s MST algorithm: O(E log E) (often written O(E log V)). Sorting edges dominates; union-find adds near-linear overhead.
Bellman–Ford single-source shortest path: O(VE).
Floyd–Warshall all-pairs shortest path: Θ(V^3).
Assessment of the provided choices: None of the given answer choices exactly matches all correct mappings because the Kruskal complexity is not listed correctly in any choice.
If you list the correct matching in the problem's notation, it should be: A → Θ(V+E), B → O(E log E) (not one of the listed options), C → O(VE), D → Θ(V^3). Among the given choices, the string "A-III, B-I, C-II, D-IV" matches three of the four algorithms (topological sort, Bellman–Ford, Floyd–Warshall) but incorrectly maps Kruskal to O(V+E), so no choice is fully correct.
A video solution is available for this question — log in and enroll to watch it.