Design and Analysis of Algorithms Questions and Answers | DAA| MCQ

In this DAA Quiz , we will cover these topics such as daa, algorithm analysis and design, design of algorithm, design and analysis of algorithm, algorithm design and analysis, analysis and design of algorithms and so on.

1.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. f3, f2, f1, f4
b. f2, f3, f1, f4
c. f2, f3, f4, f1
d. f3, f2, f4, f1 Correct
Show Answer

2.Steps of Divide and Conquer approach
Select one:
a. Divide, Conquer and Combine Correct
b. Combine, Conquer and Divide
c. Combine, Divide and Conquer
d. Divide, Combine and Conquer
Show Answer
3.The complexity of searching an element from a set of n elements using Binary search algorithm is
Select one:
a. O(n log n)
b. O(log n)
c. O(n2) Incorrect
d. O(n)
Show Answer

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

5.If length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6.
length | 1 2 3 4 5 6 7 8
——————————————–
price | 1 5 8 9 10 17 17 20
What is the worst case running time for the above problem
Select one:
a. O(2n)
b. O(log n)
c. O(n2) Correct
d. O(n log n)
Show Answer
6.The number of operations in Matrix multiplications M1, M2, M3, M4 and M5 of sizes 5X10, 10X100, 100X2, 2X20 and 20X50
Select one:
a. 5830
b. 4600 Correct
c. 6900
d. 12890
Show Answer
7.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 3
b. Case 1
c. Master’s theorem is not applicable Correct
d. Case 2
Show Answer
8. ______ is a condition that is always true at a particular point in an algorithm.
Select one:
a. assertion
b. constant
c. exception
d. invariant Correct
Show Answer
9.Division Pattern of Problems in Divide and Conquer approach
Select one:
a. Iterative
b. Recursive Correct
c. Parallel
d. Random
Show Answer



10.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( n2)
b. O(ln n)
c. O( n)
d. O(n log n) Incorrect
Show Answer
11.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(n3)
b. O(n2) Incorrect
c. O(n)
d. O(n ln n)
Show Answer
12.The running time of quick sort depends on the selection of.
Select one:
a. Selection of pivot elements Correct
b. Number of input
c. Number of passes
d. Arrangements of the elements
Show Answer
13. 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(n ln n)
c. T(n2)
d. T(n) Incorrect
Show Answer
14.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 n!
c. Probability n2 Incorrect
d. Probability n
Show Answer

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

16.Merge Sort divides the list in
Select one:
a. N equal parts Incorrect
b. Two equal parts
c. Two parts, may not be equal
d. N parts, may not be equal
Show Answer
17.Time complexity of matrix chain multiplication
Select one:
a. O(n2)
b. O(n)
c. O(nlogn) Incorrect
d. O(n3)
Show Answer
18.A sort which relatively passes through a list to exchange the first element with any elementless than it and then repeats with a new first element is called________.
Select one:
a. Quick sort
b. heap sort
c. Insertion sort Correct
d. Bubble sort
Show Answer
19.Apply Master theorem to T(n)=3.T(n/2)+n^2 and write what is f(n)
Select one:
a. f(n)=n/2+n^2 Incorrect
b. f(n)=n/2
c. f(n)=n^2
d. f(n)=3n/2
Show Answer



20.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) computes
Select one:
a. a uniform deliberate permutation
b. a different random permutation
c. a different deliberate permutation
d. a uniform random permutation Correct
Show Answer
21.Run Time of Merge Sort is
Select one:
a. BIG O of N log N Incorrect
b. Gamma of n log N
c. Theta of N log N
d. Omega of N log N
Show Answer
22.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) Incorrect
Show Answer
23.Time Complexity of Optimal binary search tree.
Select one:
a. O(logn)
b. O(n) Incorrect
c. O(n!)
Show Answer

24.Data Structure used for the Merge Sort
Select one:
a. Two Pointers
b. Two pointers and N Extra Arrays
c. 2N/2 pointers and N/2 Extra Arrays Incorrect
d. Two Pointers and an Extra Array
Show Answer

25.In dynamic programming, the output to stage n become the input to
Select one:
a. stage n-1 Correct
b. stage n+1
c. stage n itself
d. stage n-2
Show Answer

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

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

28.Master theorem applies to recurrences of the form (a=1 and b>1) are two constants.
Select one:
a. T(n)=a.T(n/b)+f(n)
b. T(n)=n.T(n/2)+b.f(n)
c. T(n)=a.T(n-1)+b
d. T(n)=n.T(n-3)+b Incorrect
Show Answer

29.Time complexity of LCS
Select one:
a. O(m!)
b. O(mn) Correct
c. O(n!)
Show Answer