Coursera Answers

Problem Set #2 Quiz Answer

In this article i am gone to share Coursera Course Divide and Conquer, Sorting and Searching, and Randomized Algorithms Week 2 | Problem Set #2 Quiz Answer with you..

Divide and Conquer, Sorting and Searching, and Randomized Algorithms Week 2  

Problem Set #2 Quiz Answer

Question 1)

This question will give you further practice with the Master Method. Suppose the running time of an algorithm is governed by the recurrence T(n) = 7 ✳ T(n / 3) +n2. What’s the overall asymptotic running time (i.e, the value of T(n))?

  • Ө(n2 log n) 
  • Ө(n2)
  • Ө(n2.81)
  • Ө(n log n)

 

Question 2)

This question will give you further practice with the Master Method. Suppose the running time of an algorithm is governed by the recurrence T(n) = 9✳T(n / 3) +n2. What’s the overall asymptotic running time (i.e, the value of T(n))?

  • Ө(n2 log n) 
  • Ө(n2)
  • Ө(n3.17)
  • Ө(n log n)

 

Question 3)

This question will give you further practice with the Master Method. Suppose the running time of an algorithm is governed by the recurrence T(n) = 5✳T(n / 3) +4n. What’s the overall asymptotic running time (i.e, the value of T(n))?

  • Ө(n2.59)
  • Ө(n2)
  • Ө(nlog 3 / log 5)
  • Ө(n5/3)
  • Ө(n log (n))
  • Ө(nlog 3 / (5))

 

Question 4)

Consider the following pseudocode for calculating a where a and bare positive integers)  

FastPower(a,b) : 

    if b = 1 

       return a 

else 

    c : = a*a

   ans := Fast Power(c,[b/2]) 

if b is odd 

      return a*ans 

else return ans 

end 

Here [x] denotes the floor function, that is, the largest integer less than or equal to x.

Now assuming that you use a calculator that supports multiplication and division (Le.. you can do multiplications and divisions in constant time), what would be the overall asymptotic running time of the above algorithm (as a function of b)? 

  • Ө(b log(b)) 
  • Ө(log(b)) 
  • Ө(b)
  • Ө(√b)
 

Question 5)

Choose the smallest correct upper bound on the solution to the following recurrence T(1) = 1 and T (n) ≤ T( [√n]) +1 for n > 1. Here [x] denotes the “floor” function, which rounds down to the nearest integer. (Note that the Master Method does not apply.) 

  • 0(log n)
  • 0(√n)
  • 0(1)
  • 0(log log n )