Design and Analysis of Algorithms

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
Feedback
The correct answer is: f3, f2, f4, f1


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
Feedback
The correct answer is: Divide, Conquer and Combine


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)
Feedback
The correct answer is: O(log n)



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
Feedback
The correct answer is: Bottom up fashion


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)
Feedback
The correct answer is: O(n2)


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
Feedback
The correct answer is: 4600


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
Feedback
The correct answer is: Master’s theorem is not applicable


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
Feedback
The correct answer is: invariant


9.Division Pattern of Problems in Divide and Conquer approach

Select one:
a. Iterative
b. Recursive Correct
c. Parallel
d. Random
Feedback
The correct answer is: Recursive


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
Feedback
The correct answer is: O(ln n)


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)
Feedback
The correct answer is: O(n)


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
Feedback
The correct answer is: Selection of pivot elements


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
Feedback
The correct answer is: T(n ln n)




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
Feedback
The correct answer is: Probability 1/n!



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
Feedback
The correct answer is: Merge sort


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
Feedback
The correct answer is: Two equal parts


17.Time complexity of matrix chain multiplication


Select one:
a. O(n2)
b. O(n)
c. O(nlogn) Incorrect
d. O(n3)
Feedback
The correct answer is: O(n3)


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
Feedback
The correct answer is: Insertion sort


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
Feedback
The correct answer is: f(n)=n^2


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
Feedback
The correct answer is: a uniform random permutation


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
Feedback
The correct answer is: Theta of N log N


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
Feedback
The correct answer is: O(N)


23.Time Complexity of Optimal binary search tree.


Select one:
a. O(logn)
b. O(n) Incorrect
c. O(n!)
Feedback
The correct answer is: O(logn)



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
Feedback
The correct answer is: Two Pointers and an Extra Array



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
Feedback
The correct answer is: stage n-1


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
Feedback
The correct answer is: O(nW)



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
Feedback
The correct answer is: Decision stages



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
Feedback
The correct answer is: T(n)=a.T(n/b)+f(n)



29.Time complexity of LCS


Select one:
a. O(m!)
b. O(mn) Correct
c. O(n!)
Feedback
The correct answer is: O(mn)