DAA Important Questions

(1) (1)Write an algorithm for a given number n to generate the n’th number of the Fibonacci sequence.

-----May/June 2007

(2) (2) (A) what is pseudo code? Explain with an example [ 8 marks ]

(B) Find the complexity C(n) of the algorithm for the worst, best and average case

{ evaluate average case complexity for n=3, where n is the number of inputs } [ 8 marks ]

(3) Write a recursive function to find the factorial of a number n ---> 2 mark
April/May 2008

(4) How does computing the limit help in comparing the order of growth of 2 specific function?
Compare the orders of growth of n+nlogn and n.n^(1/2)
April/May 2008

(5) Write an algorithm to find the number of binary digits in n's binary representation and analyse the same
---> 8 mark

(6) write an algorithm to search linearly for an element X in an ordered list of ‘n’ entries. What is the best , worst, average case analysis and justify your answer?

(7) Write an algorithm that finds the product of 2 matrices

-->2marks Nov/Dec 2004

(8) Solve the following recursive relation

Q(n) = n-1 + 2Q(n/2) and given Q(1) =0. Assume that Q is defined for all powers of 2

(9) Find the order of n^2 + logn

->2marks April/May 2005

(10) Consider the following algorithm

Mystery(n)

//Input: A non-negative integer n

S<-0

For i<-1 to n do

s<- s + i*i

return s

a) What does this algorithm compute?

b) What is its basic operation?

c) How many times is the basic operation executed ?

d) What is the efficiency class of this algorithm ?

e) Suggest improvements for this algorithm and justify your improvement by analysing its efficiency

May/June2009