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]
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]
No comments:
Post a Comment