10CS43 Design and Analysis of Algorithm Question Bank-Unit 1
Design and Analysis of Algorithm(10cs43)
UNIT
1
INTRODUCTION
QUESTION
BANK
1.What is algorithm? What are properties of Algorithm?
1.What is algorithm? What are properties of Algorithm?
2.If f1(n)€O(g1(n)) and If f2(n)€O(g2(n))
prove that f1(n)+ f2(n) €O(max{g1(n),g2(n)})
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 nth Fibonacci number.
18.Express using Aysmptotic Notation i) N! ii) 6 * 2n+n2
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
F(n-1)+n n>0
i) F(n)= 0 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=2k
