Design and Analysis of Algorithms Questions and Answers | DAA MCQ

Which of the following sorting algorithms does not have a worst case running time of O(n2) ?
Select one:
a. Bubble sort
b. Quick sort
c. Merge sort –
d. Insertion sort

Time Complexity of Optimal binary search tree.
Select one:
a. O(n)
b. O(logn) –
c. O(n!)

Time complexity of matrix chain multiplication
Select one:
a. O(n2)
b. O(n)
c. O(n3) –
d. O(nlogn)

Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3 and f4?
f1(n) = 2^n
f2(n) = n^(3/2)
f3(n) = nLogn
f4(n) = n^(Logn)
Select one:
a. f2, f3, f1, f4
b. f3, f2, f4, f1 –
c. f3, f2, f1, f4
d. f2, f3, f4, f1

______ is a condition that is always true at a particular point in an algorithm.
Select one:
a. constant
b. exception
c. assertion
d. invariant –
Run Time of Merge Sort is
Select one:
a. Omega of N log N
b. Gamma of n log N
c. Theta of N log N –
d. BIG O of N log N

71. PERMUTE-BY-SHORTING(A)
n=A.length
Let P[1…n] be a new array
For i=1 to n
P[i]=RANDOM(1,n3)
Sort A, using P as sort keys
The time complexity of above algorithm is
Select one:
a. T(n3)
b. T(n2)
c. T(n ln n) –
d. T(n)
Which case of Master’s theorem is applicable in the recurrence relation T(n)=0.5*T(n/2)+1/n?
Select one:
a. Case 2
b. Case 3
c. Master’s theorem is not applicable –
d. Case 1
Merge Sort divides the list in
Select one:
a. Two equal parts –
b. N equal parts
c. N parts, may not be equal
d. Two parts, may not be equal
Division Pattern of Problems in Divide and Conquer approach
Select one:
a. Parallel
b. Recursive –
c. Random
d. Iterative

Time complexities of three algorithms are given. Which should execute the slowest for large values of N?
Select one:
a. O(N) –
b. O(N ½)
c. O(log n)
RANDOMIZE-IN-PLACE(A)
n=A.length
For i=1 to n
Swap A[i] with A[RANDOM(I,n.]
The time complexity of above algorithm is
Select one:
a. O(n) –
b. O(n2)
c. O(n ln n)
d. O(n3)

If one was to apply Master theorem to recurrence equation T(n)=3.T(n/2)+n^2, what would be the values of a and b?
Select one:
a. A=2,b=2
b. a=3,b=2 –
c. a=3,b=3
d. a=2,b=3

RANDOMIZE-IN-PLACE(A)
n=A.length
For i=1 to n
Swap A[i] with A[RANDOM(I,n)]
The above procedure RANDOMIZE-IN-PLACE(A) permutation occurs with probability
Select one:
a. Probability 1/n! –
b. Probability n2
c. Probability n
d. Probability n!

Time complexity of LCS
Select one:
a. O(m!)
b. O(mn) –
c. O(n!)

RANDOMIZED-HIRE – ASSISTANT (n)
Randomly permute the list of candidates
Best=0
For i=1 to n
interview candidate i
If candidate I is better than candidate best
best=i
hire candidates i
The expected hiring cost of the procedure is.
Select one:
a. O( n)
b. O(n log n)
c. O( n2)
d. O(ln n) –

In the development of dynamic programming the value of an optimal solution is computed in
Select one:
a. In any way
b. Top up fashion
c. Bottom up fashion –

Apply Master theorem to T(n)=3.T(n/2)+n^2 and write what is f(n)
Select one:
a. f(n)=3n/2
b. f(n)=n/2+n^2
c. f(n)=n^2 –
d. f(n)=n/2

In dynamic programming, the output to stage n become the input to
Select one:
a. Decision stages –
b. Optimum solution
c. Objective function
d. Feasible solution

Time complexity of knapsack 0/1
where n is the number of items and W is the capacity of knapsack.
Select one:
a. O(nW) –
b. O(W)
c. O(n)