Reg No.:

Max. Marks: 100

1

2

3

4

5 a)
b)

6 a)

7 2)

03000CS302052001

Pages: 3

Name:
APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY

Sixth semester B.Tech examinations (S), September 2020

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

PARTA
Answer all questions, each carries3 marks.
Express the return value of the function “mystery” in 6 — notation.
intmystery(int n) {
int j=0,total=0;
for (int i=1;j<=n;i++){
++total;
jt=2*i;
}
return total;
}
Is 2°*'=0(2")? Is 2"=0(2")? Justify
Define a B-tree. Give an example.

Implement UNION using linked list representation of disjoint sets.

PART ‏تا‎
‎Answer any two full questions, each carries9 marks.
Solve T(n)=2T(n/2)+2 if n>2
=lifn=2 Using iteration method.
Solve T(n)=2T(Vn)+logn
Show the red-black tree that result after successively inserting the keys
41,38,31,12,19,8 into an initially empty red-black tree.
Consider the following C function
intcheck(int n){
1111];

for (i=1;i<=n;i++){

Page 1 of 3

Duration: 3 Hours

Marks
(3)

(3)
(3)
(3)

(4)

(5)
(9)

(4)