Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Multiple Choice Questions
Q21: In the 2-dimensional maxima problem, what is a point ppp dominated by?
- A: Another point with equal coordinates
- B: A point with higher x & y
- C: Any point in the plane
- D: A point with lower x & y
View Answer
B
Q22: What is the primary drawback of the brute-force algorithm in 2D maxima problems?
- A: It lacks efficiency
- B: It's complex
- C: Uses extensive memory
- D: Doesn't compare points
View Answer
A
Q23: What is the time complexity of the brute-force algorithm for 2D maxima problems?
- A: Θ(n)
- B: Θ(n log n)
- C: Θ(n^2)
- D: Θ(log n)
View Answer
C
Q24: What technique improves the efficiency of finding maximal points in 2D space?
- A: Stack sorting
- B: Plane sweep
- C: Grid method
- D: Graph traversal
View Answer
B
Q25: The plane-sweep algorithm primarily uses which data structure to store maximal points?
- A: Queue
- B: List
- C: Array
- D: Stack
View Answer
D
Q26: How are points sorted in the plane-sweep algorithm?
- A: By x-coordinate
- B: By y-coordinate
- C: By distance from origin
- D: Randomly
View Answer
A
Q27: What does a "maximal point" in 2D space mean in terms of dominance?
- A: Dominated by at least one other point
- B: Dominates all points
- C: Not dominated by any point
- D: Dominates itself
View Answer
C
Q28: After sorting, the sweep line moves across points in which direction?
- A: Bottom to top
- B: Left to right
- C: Right to left
- D: Random direction
View Answer
B
Q29: The overall time complexity of the plane-sweep algorithm is:
- A: Θ(n)
- B: Θ(n log n)
- C: Θ(n^2)
- D: Θ(log n)
View Answer
B
Q30: In terms of computational efficiency, asymptotic analysis is most useful for:
- A: Small inputs
- B: Moderate inputs
- C: Large inputs
- D: All input sizes
View Answer
C