Algorithm MCQs

1. What is the time complexity of the Closest-Pair problem using the Divide and Conquer approach?

a) O(n) b) O(n log n) c) O(n²) d) O(log n)

2. What is the main idea behind the Convex-Hull problem using Divide and Conquer?

a) To recursively divide the set of points into smaller subsets and merge the hulls. b) To use brute force to find the convex hull. c) To sort the points and find the hull in linear time. d) To use dynamic programming to solve the problem.

3. What is the time complexity of Insertion Sort in the worst case?

a) O(n) b) O(n log n) c) O(n²) d) O(log n)

4. Which of the following is true about Depth-First Search (DFS)?

a) It uses a queue for traversal. b) It explores as far as possible along each branch before backtracking. c) It is used to find the shortest path in an unweighted graph. d) It has a time complexity of O(n²).

5. Which of the following is true about Breadth-First Search (BFS)?

a) It uses a stack for traversal. b) It explores all neighbors at the present depth before moving to the next level. c) It is used to find the longest path in a graph. d) It has a time complexity of O(n log n).

6. What is the time complexity of DFS and BFS for a graph with \( V \) vertices and \( E \) edges?

a) O(V) b) O(E) c) O(V + E) d) O(V log E)

7. What is the purpose of finding Connected Components in a graph?

a) To find the shortest path between two nodes. b) To identify subgraphs where every pair of vertices is connected by a path. c) To sort the vertices in topological order. d) To find the minimum spanning tree.

8. Which of the following is true about Topological Sort?

a) It is only applicable to undirected graphs. b) It is used to sort vertices in a Directed Acyclic Graph (DAG). c) It has a time complexity of O(V²). d) It is used to find the shortest path in a graph.

9. What is the time complexity of Topological Sort using DFS?

a) O(V) b) O(E) c) O(V + E) d) O(V log E)

10. Which of the following algorithms is used to find Connected Components in an undirected graph?

a) Dijkstra's Algorithm b) Kruskal's Algorithm c) DFS or BFS d) Prim's Algorithm

11. What is the space complexity of DFS?

a) O(V) b) O(E) c) O(V + E) d) O(V log E)

12. Which of the following is true about BFS?

a) It is used to detect cycles in a graph. b) It is used to find the shortest path in an unweighted graph. c) It uses a stack for traversal. d) It has a space complexity of O(V log E).

13. What is the time complexity of the brute-force Convex-Hull algorithm?

a) O(n) b) O(n log n) c) O(n²) d) O(n³)

14. Which of the following is a disadvantage of the Divide and Conquer approach for the Closest-Pair problem?

a) It requires sorting the points by x-coordinate. b) It has a higher constant factor compared to brute force. c) It cannot handle large datasets. d) It is not applicable to 2D points.

15. Which of the following is true about Insertion Sort?

a) It is a divide-and-conquer algorithm. b) It is an in-place sorting algorithm. c) It has a time complexity of O(n log n) in the worst case. d) It is not suitable for small datasets.

Divide and Conquer, Decrease and Conquer, Graph Algorithms MCQs

Your Score: /15