A F192010 Pages:4

Reg No.:_ Name:
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
SIXTH SEMESTER B.TECH DEGREE(S) EXAMINATION(S), DECEMBER 2019
Course Code: CS302
Course Name: DESIGN AND ANALYSIS OF ALGORITHMS

Max. Marks: 100 Duration: 3 Hours
PARTA
Answer all questions, each carries3 marks. Marks
1 Analyse the complexity of the following function (3)
void function(int n)
{ int count = 0;

for (int i=n/2; i<=n; i++)
for (int j=1; j<=n; | =2 * j)
for (int k=1; k<=n; k =k * 2)

count++;
}
2 Solve using Iteration method T(n)=2T(n/2)+n,T(1)=1 (3)
3 Define B-tree. Discuss the significance of B-tree (3)
4+ Explain Asymptotic notations in algorithm analysis (3)
PART B
Answer any two full questions, each carries9 marks.
5 93) Solve using Recursion Tree method (5)

T(n)=3T(n/4)+n?

b) Analyse the complexity of the following functions (4)
i)function(int n)
{ if (n==1) return;
for (int i=1; i<=n; i++)
{ for (int j=1; j<=n; j++)
{ printf("*"); break; }
}
}
ii) void function(int n)
{
1111 = 1, ऽ =1;
while (8 <= 0)
{ .
i++;
ऽ += |]
printf("*");
}
)

Page 1of 4