Solution for NPTEL, Introduction to Algorithm and Analysis Week 2 MCQs

Algorhithm and Analysis assignment 2

1. If T(n)=9T(n/3)+n, then by master method T(n)=

A. Θ(n).

B. Θ(n²).

C. Θ(n³).

D. Θ(1).

 B.Θ(n^2)

 

2. If T(n)=T(2n/3)+1, then by master method T(n)=

A. Θ(logn).

B. Θ(n²).

C. Θ(n³).

D. Θ(1).

 A. Θ(nlogn)

 

3.If T(n)=2T(n/2)+ Θ(n), then by master method T(n)=

A. Θ(n).

B. Θ(n²)

C. Θ(n³).

D. Θ(nlogn).

 D.Θ(nlogn)

4.Consider the polynomial p(x) = a₀ + a₁x + a₂x² +a₃x³, where ai≠ 0, for all i. The minimum number of multiplications needed to evaluate p on an input x is:

A. 3

B. 4

C. 5

D. 6

 A. 3

5. Naive matrix multiplication of two N×N matrices has running time

A. Θ(N).

B. Θ(N²).

C. Θ(N³).

D. Θ(1).

 C. Θ(N^3)

6.Strassen’s method has running time (for multiplying two n×n matrices)

A. Θ(n).

B. Θ(n²).

C. Θ(n³).

D. None of the above

 D. None of the above

7.Divide and conquer consists of

A. Divide and Combine

B. Divide,Conquer and Combine

C. Divide and Conquer

D. None of the above

 B. Divide,Conquer and Combine

 

8.If T(n) = T(n/4) + T(n/2) +n2 , then using recursion tree method

A. T(n)= Θ(n).

B. T(n)= Θ(n²).

C. T(n)= Θ(n³).

D. None of the above

 B. T(n)=Θ(n^2)

9.Recurrence relation for binary search

A. T(n) = 2T(n/2) + Θ(1)

B. T(n) = T(n/2) + Θ(1)

C. T(n) = 2T(n/2) + Θ(n)

D. T(n) = 2T(n/2) + Θ(n²)

 T(n)=T(n/2)+Θ(1)

10. Strassen’s algorithm needs____ many multiplications to multiply two 2×2 matrices

A. 8

B. 9

C. 7

D. 3

 C. 7