Reg No.:

Max. Marks: 100

b)

A6810 Pages: 4

Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
SIXTH SEMESTER B.TECH DEGREE EXAMINATION, APRIL 2018

Course Code: CS302
Course Name: DESIGN AND ANALYSIS OF ALGORITHMS (CS)

PART A
Answer all questions, each carries 3 marks.

Is 281 = 0(2") 9 Is 27 = O(2")? Justify your answer.
State Master’s Theorem. Find the solution to the following recurrence equation
using Master’s theorem.

2) T(n)=2T (n/2)+nlogn

b) T (೧) = 277 (n/2) +n"
Analyse the complexity of the following program

main ( )

{

for ( inti=1; i<=n;i=i*2)
sum =sum+i+func(i )

}

void func(m )

0
१

for ( int j=1; j<=m; j++)
Statement with O(1 ) complexity

}

State weighted rule (union by rank) and collapsing rule (path compression)
applied in the disjoint set union and find operation respectively. How these
rules will improve the efficiency of disjoint set operations.

PART B
Answer any two full questions, each carries 9 marks.

Using iteration solve the following recurrence equation
T(n)=2 if n=1 else T(n)= 2T(n/2)+2n+3
Using Recursion Tree method, solve.
Assume constant time for small values of n.
T(n)= 2T(n/10)+ T(9n/10)+n
Construct a red-black tree by inserting the keys 41, 38,31,12,19,8 into an
initially empty tree. Then show the red-black trees that result from the

Page 1of 4

Duration: 3 Hours

Marks
(3)
(3)

(3)

(3)

(5)

(4)

(9)