2011 Kannur University B.Tech Computer Science and Engineering VII Semester B.Tech. (Reg/Suppl./Imp. - Including Part Time) Degree Examination: DESIGN AND ANALYSIS OF ALGORITHMS Question paper

VII Semester B.Tech. (Reg/Suppl./Imp. - Including Part Time) Degree
Examination, November 2011
(2007 Admn.)
2K6 CS 702 : DESIGN AND ANALYSIS OF ALGORITHMS 

Time : 3 Hours Max. Marks : 100



I. 1. Write short notes on Big O Notation. [Marks 5]

2. Use the master method to give tight asymptotic bounds for the recurrences problem. [Marks 5]
3. How do you construct a Huffman code ? [Marks 5]
4. Write short notes on elements of dynamic programming. [Marks 5]
5. What are the ways of solving NP complete problems ? [Marks 5]
6. Compare Euler tour with Hamiltonian cycle. [Marks 5]
7. Write short notes on probabilistic analysis. [Marks 5]
8. What are indicator random variables ? [Marks 5]

ll. A) Discuss the performance of quick sort algorithm with regards to partitioning. [Marks 15]

OR

B) Explain any two most common techniques used in amortized analysis. [Marks 15]
III. A) Explain the Divide-and-Conquer approach with a suitable example. [Marks 15]
OR

B) Discuss in detail about Back Tracking. [Marks 15]
IV. A) Show that the Hamiltonian-path problem is NP complete. [Marks 15]

OR

B) Show that the subset-sum problem is solvable in polynomial time if the target

value t is expressed in unary. [Marks 15]

V. A) Discuss randomized algorithm for n-Queen problem. [Marks 15]

OR

B) Bring out the importance of Dixons integer factorization algorithm with a real

life example. [Marks 15]