Design and Analysis of Algorithms - MCQS

Question

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=3,b=3
b. a=3,b=2
c. A=2,b=2
d. a=2,b=3

The correct answer is: a=3,b=2

Question 
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(n)
c. O(W)

The correct answer is: O(nW)

Question 
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(n2)
c. O(n)
d. O(log n)

The correct answer is: O(log n)

Question 
Time complexity of matrix chain multiplication

Select one:
a. O(n2)
b. O(nlogn)
c. O(n)
d. O(n3)

The correct answer is: O(n3)

Question 
Time complexity of LCS

Select one:
a. O(n!)
b. O(m!)
c. O(mn)

The correct answer is: O(mn)

Question 
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
b. f(n)=n/2+n^2
c. f(n)=n^2
d. f(n)=3n/2

The correct answer is: f(n)=n^2

Question
Data Structure used for the Merge Sort

Select one:
a. Two Pointers and an Extra Array
b. Two Pointers
c. 2N/2 pointers and N/2 Extra Arrays
d. Two pointers and N Extra Arrays

The correct answer is: Two Pointers and an Extra Array

Question 
Steps of Divide and Conquer approach

Select one:
a. Combine, Divide and Conquer
b. Divide, Combine and Conquer
c. Combine, Conquer and Divide
d. Divide, Conquer and Combine

The correct answer is: Divide, Conquer and Combine

Question 
Which of the following sorting algorithms does not have a worst case running time of O(n2) ?

Select one:
a. Quick sort
b. Bubble sort
c. Insertion sort
d. Merge sort

The correct answer is: Merge sort

Question 
Data Structure used for the Merge Sort

Select one:
a. Two pointers and N Extra Arrays
b. Two Pointers and an Extra Array
c. Two Pointers
d. 2N/2 pointers and N/2 Extra Arrays

The correct answer is: Two Pointers and an Extra Array

Question
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 different deliberate permutation
b. a uniform deliberate permutation
c. a uniform random permutation
d. a different random permutation

The correct answer is: a uniform random permutation

Question 
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)

The correct answer is: O(N)

Question 
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(log n)
b. O(n2)
c. O(n log n)
d. O(2n)

The correct answer is: O(n2)

Question 

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(n ln n)
b. T(n)
c. T(n3) In
d. T(n2)

The correct answer is: T(n ln n)

Question 
 ______ is a condition that is always true at a particular point in an algorithm.

Select one:
a. assertion
b. exception
c. constant
d. invariant

The correct answer is: invariant

Question 
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)

The correct answer is: O(n)

Question 
Merge Sort divides the list in

Select one:
a. Two parts, may not be equal
b. N parts, may not be equal
c. N equal parts
d. Two equal parts

The correct answer is: Two equal parts

Question 
Time Complexity of Optimal binary search tree.

Select one:
a. O(logn)
b. O(n!) In
c. O(n)

The correct answer is: O(logn)

Question 
Division Pattern of Problems in Divide and Conquer approach

Select one:
a. Random
b. Parallel
c. Recursive
d. Iterative

The correct answer is: Recursive

Question
In dynamic programming, the output to stage n become the input to

Select one:
a. stage n itself
b. stage n-1
c. stage n-2
d. stage n+1 In

The correct answer is: stage n-1

Question 
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 n
b. Probability n2
c. Probability n!
d. Probability 1/n!

The correct answer is: Probability 1/n!

Question 
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 2
c. Case 1
d. Master’s theorem is not applicable

The correct answer is: Master’s theorem is not applicable

Question 
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
c. In any way

The correct answer is: Bottom up fashion

Question 
Run Time of Merge Sort is

Select one:
a. BIG O of N log N
b. Theta of N log N
c. Gamma of n log N
d. Omega of N log N

The correct answer is: Theta of N log N

Question 
The number of operations in Matrix multiplications M1, M2, M3, M4 and M5 of sizes 5X10, 10X100, 100X2, 2X20 and 20X50

Select one:
a. 4600
b. 12890
c. 6900
d. 5830

The correct answer is: 4600

Question 
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, f1, f4
c. f3, f2, f4, f1
d. f2, f3, f4, f1

The correct answer is: f3, f2, f4, f1

Question 
The running time of quick sort depends on the selection of.

Select one:
a. Number of input
b. Arrangements of the elements
c. Selection of pivot elements
d. Number of passes

The correct answer is: Selection of pivot elements

Question 
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(n log n)
c. O(ln n)
d. O( n)

The correct answer is: O(ln n)

Question 
In dynamic programming, the output to stage n become the input to

Select one:
a. Objective function
b. Optimum solution
c. Feasible solution
d. Decision stages

The correct answer is: Decision stages

Question 
Master theorem applies to recurrences of the form (a=1 and b>1) are two constants.

Select one:
a. T(n)=n.T(n/2)+b.f(n)
b. T(n)=n.T(n-3)+b
c. T(n)=a.T(n-1)+b
d. T(n)=a.T(n/b)+f(n)

The correct answer is: T(n)=a.T(n/b)+f(n)

Question 
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. Insertion sort
b. Bubble sort
c. heap sort
d. Quick sort

The correct answer is: Insertion sort