B. Tech Degree VI Semester Examination, April 2009 CS/IT 604 ANALYSIS AND DESIGN OF ALGORITHMS - CUSAT

B. Tech Degree VI Semester Examination, April 2009

Cochin University Of Science and Technology

CS/IT 604 ANALYSIS AND DESIGN OF ALGORITHMS

(2006 Scheme)

Time : 3 Hours Maximum Marks : 100

PART - A

(Answer ALL questions)
(8 x 5 = 40)
(a) Briefly explain backtracking technique used in algorithm design.
(b) What are recursive procedures? How is their complexity expressed?
(c) What are the features of binomial heap data structure? Give an example.
(d) What are the features of Quicksort algorithm? Write expressions for its worst and average case complexity
(e) What is depth first traversal in a graph? Which data structure is used in depth first traversal? What do you mean by strongly connected components of a graph? Give an example.
(g) Explain bin-packing problem.
01) Explain Graph coloring problem.
PART - B

Explain the need for analyzing algorithms. Why time requirement for execution of an algorithm more important than space requirement?
Which are the basic asymptotic notations used to express complexity of an algorithm? OR
State Master theorem.
Explain Greedy strategy in designing an algorithm.
What is meant by divide and conquer technique? What are the basic steps involved in this technique?

IV. Write insertion sort algorithm and analyse it.

(b) What are the properties of Red-Black trees?

OR

V. (a) Write the procedure for insertion in Red-Black tree.

(b) Define amortized time analysis.

I. Explain transitive closure of a binary relation. Write an algorithm to find transitive

closure. (15)

OR

II. What are bi-connected components of a graph? Explain with an example. What is the

physical significance of bi-connected components in a graph? (15)

III. Define :

(i) 

(ii) NP 4

(iii) NP — complete classes of problem with an example for each. (15)

OR

Ix. (a) Explain travelling salesperson problem. (7)

(b) Explain first-fit strategy for Bin-packing problem. (8)