Reg No.:

Name:
APJ ABDUL 1:11 ‏و و سو‎ भर] UNIVERSITY

Sixth Semester B.Tech Degree Regular and Supplementary Examination July 2021

Course Code: CS302
Course Name: DESIGN AND ANALYSIS OF ALGORITHMS

Max. Marks: 100 Duration: 3 Hours
PART A
Answer all questions, each carries 3 marks. Marks
1 Define the terms Best case, Worst case and Average case time complexities. (3)
2 Analyse the complexity of the following function: (3)

3

4

5 2)
0)

6 ஐ
b)

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 [= 1; k<=n; k= k * 2)

countt+;
|
List out the properties of red-black tree. (3)
What is meant by height balanced tree? Give examples. (3)
PART ‏تا‎
‎Answer any two full questions, each carries 9 marks.

Solve using iteration method. (4)

1) 10562 T(n/2)+n

1) T(n) = 2 7/2) + ‏ثم‎
‎Solve the recurrence using recursion tree method: (5)
1(1) = 1
T(n) = 31൩4) cn?
State Master’s theorem. (3)
Solve using Masters theorem: (6)

i) T(n)=3 T (1/4) + 1 logn
ii) T(n) = 9 T(n/3) + 7

Page 1 of 3