Algorithm MCQs

1. What is the first step in the Divide-and-Conquer strategy?

a) Combine solutions of smaller instances b) Divide the problem into smaller instances c) Solve the problem directly d) Sort the input data

2. Which of the following is NOT a step in the Divide-and-Conquer technique?

a) Divide the problem into smaller subproblems b) Solve the subproblems recursively c) Combine the solutions of subproblems d) Iterate through all possible solutions

3. What is the first step in the Closest-Pair algorithm using Divide-and-Conquer?

a) Sort the points by x-coordinate b) Divide the points into two subsets c) Find the closest pair recursively d) Combine the results

4. In the Closest-Pair algorithm, how many points in the vertical strip need to be inspected for each point?

a) At most 4 b) At most 6 c) At most 8 d) All points in the strip

5. What is the time complexity of the Closest-Pair algorithm (excluding sorting)?

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

6. What is the Convex Hull of a set of points?

a) The smallest convex set that includes all the points b) The largest convex set that includes all the points c) The set of all points lying inside the polygon d) The set of all points lying on the boundary of the polygon

7. What is the worst-case time complexity of the brute-force Convex Hull algorithm?

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

8. Which of the following is true about the Convex Hull algorithm?

a) It requires sorting the points by x-coordinate b) It has a worst-case time complexity of O(n log n) c) It uses a Divide-and-Conquer approach d) All of the above

9. What is the key operation in Insertion Sort?

a) Swapping adjacent elements if they are in the wrong order b) Dividing the array into two halves c) Merging two sorted subarrays d) Selecting the minimum element and placing it at the beginning

10. After the ith iteration of Insertion Sort, what is true about the array?

a) The first i elements are sorted b) The last i elements are sorted c) The entire array is sorted d) The first i+1 elements are sorted

11. What is the worst-case time complexity of Insertion Sort?

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

12. Which algorithm design strategy is used in both the Closest-Pair and Convex Hull problems?

a) Greedy b) Dynamic Programming c) Divide-and-Conquer d) Backtracking

13. What is the time complexity of sorting points by x-coordinate in the Closest-Pair algorithm?

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

14. Which of the following problems can be solved using Divide-and-Conquer?

a) Closest-Pair b) Convex Hull c) Insertion Sort d) Both a and b

15. What is the purpose of the vertical strip in the Closest-Pair algorithm?

a) To divide the points into two subsets b) To limit the search for the closest pair c) To sort the points by y-coordinate d) To combine the solutions of subproblems

Divide-and-Conquer, Closest Pair, Convex Hull, and Insertion Sort MCQs

Your Score: /15