Design and Analysis of Algorithms MCQs - Unit 1
A
Ambiguity
B
Definiteness
C
Finiteness
D
Effectiveness
Correct Answer
Ambiguity
A
constant part only
B
variable part
C
hidden part
D
compile-time part
Correct Answer
variable part
A
step count (frequency count)
B
the color of the output
C
the size of the source file
D
the programmer's experience
Correct Answer
step count (frequency count)
A
lower bound
B
exact bound only
C
average bound only
D
upper bound
Correct Answer
upper bound
A
upper bound
B
lower bound
C
loose upper bound
D
constant bound
Correct Answer
lower bound
A
upper bound only
B
lower bound only
C
no bound
D
tight bound (both upper and lower)
Correct Answer
tight bound (both upper and lower)
A
asymptotically tight
B
a lower bound
C
not asymptotically tight
D
always constant
Correct Answer
not asymptotically tight
A
O(1)
B
O(log n)
C
O(n²) only and not O(n)
D
O(n)
Correct Answer
O(n)
A
n < log n < n² < n log n
B
log n < n < n log n < n²
C
n² < n log n < n < log n
D
n log n < n < log n < n²
Correct Answer
log n < n < n log n < n²
A
O(log n)
B
O(n)
C
O(n log n)
D
O(1)
Correct Answer
O(log n)
A
a sorted list
B
an unsorted list
C
a linked list only
D
a list of strings only
Correct Answer
a sorted list
A
O(n²)
B
O(n)
C
O(log n)
D
O(n log n)
Correct Answer
O(n log n)
A
O(1)
B
O(n)
C
O(log n) only
D
O(n²)
Correct Answer
O(n)
A
O(n) and O(n log n)
B
O(n log n) and O(n²)
C
O(n²) and O(n²)
D
O(log n) and O(n)
Correct Answer
O(n log n) and O(n²)
A
the array is already sorted and the first or last element is the pivot
B
the pivot is always the median
C
the array has one element
D
the array is randomly shuffled
Correct Answer
the array is already sorted and the first or last element is the pivot
A
divide-and-conquer technique
B
greedy technique
C
dynamic programming
D
backtracking
Correct Answer
divide-and-conquer technique
A
O(n³)
B
O(n²)
C
O(n log n)
D
O(n^2.81)
Correct Answer
O(n^2.81)
Correct Answer
7
A
T(n) = 2T(n/2) + n
B
T(n) = T(n ā 1) + n
C
T(n) = T(n/2) + 1
D
T(n) = 7T(n/2) + n²
Correct Answer
T(n) = 2T(n/2) + n
A
T(n) = 2T(n/2) + n
B
T(n) = T(n ā 1) + 1
C
T(n) = T(n/2) + 1
D
T(n) = 2T(n ā 1)
Correct Answer
T(n) = T(n/2) + 1
A
sort, search and delete
B
read, write and print
C
push, pop and peek
D
divide, conquer and combine
Correct Answer
divide, conquer and combine
A
O(1)
B
O(log n)
C
O(n)
D
O(n log n)
Correct Answer
O(1)
A
Quick sort
B
Heap sort
C
Selection sort
D
Merge sort
Correct Answer
Merge sort
A
T(n) = 7T(n/2) + O(n²)
B
T(n) = 8T(n/2) + O(n²)
C
T(n) = 2T(n/2) + n
D
T(n) = T(n/2) + 1
Correct Answer
T(n) = 7T(n/2) + O(n²)
A
only above by g(n)
B
only below by g(n)
C
both above and below by constant multiples of g(n)
D
by no function
Correct Answer
both above and below by constant multiples of g(n)
Fill in the Blanks
26
The space complexity of an algorithm is the sum of a fixed part and a ______ part.
Correct Answer
variable
27
Big-oh notation gives an asymptotic ______ bound.
Correct Answer
upper
28
Omega notation gives an asymptotic ______ bound.
Correct Answer
lower
29
Theta notation gives an asymptotic ______ bound.
Correct Answer
tight
30
Binary search can be applied only to a ______ list.
Correct Answer
sorted
31
The worst-case time complexity of binary search is ______.
Correct Answer
O(log n)
32
The worst-case time complexity of merge sort is ______.
Correct Answer
O(n log n)
33
The worst-case time complexity of quick sort is ______.
Correct Answer
O(n²)
34
In quick sort, the element used to partition the array is called the ______.
Correct Answer
pivot
35
Strassen's method multiplies two 2 Ć 2 matrices using ______ multiplications.
Correct Answer
7
36
The time complexity of Strassen's matrix multiplication is O(n^______) approximately.
Correct Answer
2.81
37
The three steps of divide and conquer are divide, conquer and ______.
Correct Answer
combine
38
The recurrence relation of merge sort is T(n) = 2T(n/2) + ______.
Correct Answer
n
39
______ notation represents an upper bound that is not asymptotically tight.
Correct Answer
Little-oh
40
Merge sort needs ______ additional space.
Correct Answer
O(n)