Reg No.:

Max. Marks: 100

F1008 Pages: 4

Name:

APJ ABDUL KALAM TECHNOLOGICAL UNIVERSITY
SIXTH SEMESTER B.TECH DEGREE EXAMINATION(R&S), MAY 2019

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

PARTA
Answer all questions, each carries3 marks.

1 Define the terms Best case, Worst case and Average case time complexities.

2 What is the smallest value of n such that an algorithm whose running times is 100൩ runs faster

than an algorithm whose running time is 2" on the same machine?

State Master Theorem.

4 Explain the UNION and FIND-SET operations in the linked-list representation of disjoint sets.

Discuss the complexity.

b)

PART B
Answer any two full questions, each carries9 marks.

Determine the time complexities of the following two functions fun1() and fun2():

int पि] (int n)

{
if (n <= 1) return n;
return 2*funl(n-1);

}

int fun2(int n)
{

if (n <= 1) return n;
return fun2(n-1) + fun2(n-1);

}

Find the solution to the recurrence equation using iteration method:
T(2*) = 3 1021) + 1,
T()=1

Solve the recurrence using recursion tree method:
Td)=1
T(n) = 3T(n/4) + cn?

Determine the best case and worst-case time complexity of the following function:

void fun(int ‏به‎ int arr[])
{
int 15 0, ] 5 0;
for(; i > ‏بم‎ ++i)
while(j > n && arr[i] < ೫01)
j++;
Page 1 of 4

Duration: 3 Hours

Marks

(3)
(3)

(3)
(3)

(2)

(3)

(4)

(3)