Biju Patnaik University of Technology 2007-5th Sem B.Tech Computer Science and Engineering ANALYSIS AND DESIGN OF ALGORITHMS CLASS TEST-1 - Question Paper

ANALYSIS AND DESIGN OF ALGORITHMS 5TH SEM CLASS TEST-1 MAX. MARKS-10
ans all ques.. All ques. carry equal marks.

1.Arrange the function in increasing order according to their asymptotic growth rate:
n^2, n!, (lg n)!, n^3, lg(n!), 2^2^n
2.Solve the recurrence
T(n)=T(n/2)+1
3.Prove that (2^n)+(6n^5)+(7n^3)+3=O(2^n)
4.Solve the recurrence
T(n)=2T(sqrt. n)+1
5.How would you replace QUICKSORT to sort in non-increasing order.
6.If b>0, show that (n+a)^b=T(n^b)
7.Show that n!=w(2^n)
8.f(n)=O(g(n))=>g(n)=O(f(n)). actual or False. Justify.
9.f(n)=T(g(n))=>g(n)=T(f(n)). actual or False. Justify.
10.o(g(n)) intersection w(g(n))=?

Earning:   Approval pending.