###
**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

## No comments:

## Post a Comment