10cs43 DAA UNIT 1 QUESTION BANK

UNIT 1

INTRODUCTION

QUESTION BANK

1. With the help of flow chart , Explain the various steps of design and analysis process?

2.If f₁(n)€O(g₁(n)) and If f₂(n)€O(g₂(n)) prove that f₁(n)+ f₂(n) €O(max{g₁(n),g₂(n)})

3.What is algorithm? What are properties of Algorithm?.Explain with example.

4.Explain briefly various Asymptotic Notation?

5. Design a recursive Algorithm for solving Tower of Hanoi problem and give general plan of analyzing that algorithm. Show that time complexity of tower of Hanoi algorithm is exponential in nature.

6.Write an algorithm for computing GCD.

              a)Using Euclid Algorithm.

             b)Repetitive subtraction

            c) Consecutive Integer Checking

7.Explain the Sieve of Eratosthenes Alogrithm to generate prime factor?

8.Write general plans for non recursive algorithm for analyzing time efficiency?Explain with algorithm Element Uniqueness problem.Show that time efficiency is Quadratic in nature.

9.Explain non recursive algorithm to find Maximum of n-elements .Also provide time efficiency

10.Explain  non recursive algorithm for matrix multiplication.Also provide time efficiency

11. Explain non recursive algorithm to count the number of binary digits.Also provide time efficiency.

12. Write general plans for  recursive algorithm for analyzing time efficiency?Explain time efficiency of factorial of a given number with algorithm.

13.Write a recursive algorithm for fibonaaci number.Also provide the Explicit formula to obtain n^th Fibonacci number.

14. Write an algorithm for selection sort and show that time complexity of this algorithm is quadratic.Is Selection sort Stable?.Sort the list 89,45,68,90,29,34,17 using selection sort

15.Explain Brute force method for design and analysis .Explain the brute force string matching algorithm with its efficiency.

16. Write an algorithm for Bubble sort .Explain briefly time efficiency of Bubble sort?Sort the list E,X,A,M,P,L,E in alphabetical order using Bubble sort

17.Write an algorithm for sequential Search(linear search).Explain Best Case,Worst Case and Average Case time efficiency .

18.Express using Aysmptotic Notation i) N! ii) 6 * 2ⁿ+n²

19. Algorithm X(int N)

     {

     int P;

    for i←1 to N

   { printf(“\n %d \t * \t %d=%d”,N,i,p);

    P=P+N;

}

}

i)What does this algorithm computes?

ii)What is the basic operation?

iii)How many time the basic operation is executed?

iv)What is efficiency of algorithm?

20.Solve the recurrence relation

  i)   F(n)=0                             if n=0

                f(n-1)+n                   if n>0

ii)f(n)=3f(n-1) for n>1,f(1)=4

iii)f(n)=f(n/2)+n   for n>1,f(1)=1 n=2^k