Survival : BITS_Mtech_DataScience_DSAD_Quiz _2020

Quiz-1 

This Question is based on the following topic and there are no negative marks, the are total 10 Question for 5 marks 

• Analyzing Algorithms 
• Theoretical Foundation 
• Algorithms and its Specification
• Random Access Machine Model
• Counting Primitive Operations
• The notion of best case, average case and worst case
• Characterizing Run Time
• Use of asymptotic notation
• Big-Oh Notation, Little-Oh, Omega and Theta Notations
• Analyzing Recursive Algorithms
• Recurrence relations
• Master's Theorem 

Question 1

0.5 / 0.5 pts

The concept of order (Big O) is important because 

[hint: This is a multi answer question]

  

It is the lower bound of the growth rate of the algorithm

 

  

It can be used to decide the best algorithm that solves a given problem

 

  

It determines the maximum size of a problem that can be solved in a given system, in a given amount of time

 

  

None of them

 

 

Question 2

0.5 / 0.5 pts

Deducing time complexity using master’s theorem T(n) = 3T(n/4) +nlogn

  

θ(nlogn)

 

  

θ(n^2)

 

  

θ(logn)

 

  

θ(n)

 

 

IncorrectQuestion 3 -In Correct

0 / 0.5 pts

What is the time complexity of the following code:       

int i, j, k = 0;

for (i = n / 2; i<= n; i++) {

            for (j = 2; j <= n; j = j * 2) {

                        k = k + n / 2;

            }

}

  

O(nLogn)

 

  

O(n)

 

  

O(n^2Logn)

 

  

O(n^2)

 

 

Question 4

0.5 / 0.5 pts

What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

  

X will always be a better choice for small inputs

 

  

X will always be a better choice for large inputs

 

  

Y will always be a better choice for small inputs

 

  

X will always be a better choice for all inputs

 

 

IncorrectQuestion 5

0 / 0.5 pts

Deducing time complexity using master’s theorem T(n) = 4T(n/2) +n

  

θ(n^2)

 

  

θ(n)

 

  

θ(logn)

 

  

θ(nlogn)

 

 

Question 6

0.5 / 0.5 pts

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

  

θ(n)

 

  

θ(n^2)

 

  

θ(n^3)

 

  

θ(1)

 

 

Question 7

0.5 / 0.5 pts

For the following recurrences T(n) =2T(n/4) +n0.51, give an expression for the runtime T(n) if the recurrence can be solved with the master theorem.

[Hint: you can use T(n) =aT(n/b)+f(n) master theorem to solve the problem]

  

θ(n^2)

 

  

Master’s theorem not apply

 

  

θ(logn)

 

  

θ(n^0.51)

 

 

Question 8

0.5 / 0.5 pts

For the following recurrences T(n) = 3T(n/4) + O(logn) give an expression for the runtime.

  

θ(n^2 logn)

 

  

θ(√n)

 

  

θ (n^2)

 

  

θ(nlogn)

 

 

Question 9

0.5 / 0.5 pts

Give a tight asymptotic upper bound to the following recurrences T(n) = T(n/5)+log2n 

  

θ(√n)

 

  

θ(nlogn)

 

  

θ (n^2)

 

  

θ(log^3 n)

 

 

Question 10

0.5 / 0.5 pts

Deducing time complexity using master’s theorem T(n) = 4T(n/2)+n2

  

θ(n)

 

  

θ(nlogn)

 

  

θ(n^2 logn)

 

  

θ(n^2)