Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Chapter: 1
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
Correct Answer:
B
Chapter: 1
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
Correct Answer:
A
Chapter: 1
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)
Correct Answer:
C
Chapter: 1
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
Correct Answer:
B
Chapter: 1
Q25:
The plane-sweep algorithm primarily uses which data structure to store maximal points?
A. Queue
B. List
C. Array
D. Stack
Correct Answer:
D
Chapter: 1
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
Correct Answer:
A
Chapter: 1
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
Correct Answer:
C
Chapter: 1
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
Correct Answer:
B
Chapter: 1
Q29:
The overall time complexity of the plane-sweep algorithm is:
A. Θ(n)
B. Θ(n log n)
C. Θ(n^2)
D. Θ(log n)
Correct Answer:
B
Chapter: 1
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
Correct Answer:
C
Chapter: 1
Q31:
When advancing the sweep line, what operation is performed if a point is dominated?
A. Insert into stack
B. Pop from stack
C. Update y-coordinate
D. Insert at beginning
Correct Answer:
B
Chapter: 2
Q32:
What does Θ(g(n)) represent in asymptotic notation?
A. Upper bound
B. Lower bound
C. Exact growth rate
D. Average case
Correct Answer:
C
Chapter: 2
Q33:
Which function represents the fastest growth rate as n becomes large?
A. 4n^2
B. (8n^2 + 2n - 3)
C. n(n - 3)
D. √(n) - 10 log n
Correct Answer:
A
Chapter: 2
Q34:
In asymptotic notation, what is required for f(n) ∈ Θ(g(n))?
A. Only an upper bound
B. Both upper and lower bounds
C. Exact growth match
D. Only a lower bound
Correct Answer:
B
Chapter: 2
Q35:
Which of these functions is NOT asymptotically equivalent to Θ(n^2)?
A. 4n^2
B. 8n^2 + 2n - 3
C. 7n^2 + √n - log n
D. n^3
Correct Answer:
D
Chapter: 2
Q36:
If f(n) ∈ O(g(n)), which statement is correct?
A. f(n) has a strict lower bound only
B. f(n) has a strict upper bound only
C. f(n) has both lower and upper bounds
D. f(n) has neither bound
Correct Answer:
B
Chapter: 2
Q37:
What is the smallest asymptotic class of time complexity commonly used in algorithms?
A. Θ(1)
B. Θ(log n)
C. Θ(n)
D. Θ(n log n)
Correct Answer:
A
Chapter: 2
Q38:
In Θ-notation, which condition applies to two functions f(n) and g(n)?
A. They have exact growth rates
B. They have asymptotically equivalent growth rates
C. g(n) grows faster
D. They both approach infinity equally
Correct Answer:
B
Chapter: 2
Q39:
Which function would likely fall into Θ(log n) time complexity?
A. Finding an element in a list
B. Sorting an unsorted array
C. Inserting into a binary tree
D. Reversing an array
Correct Answer:
C
Chapter: 2
Q40:
Fill in the blank: For f(n) ∈ Ω(g(n)), the function f(n) has an asymptotic ______ bound.
A. lower
B. upper
C. exact
D. middle
Correct Answer:
A