K L University 2009 B.Tech Information Technology Model Design and Analysis of Algorithms - Question Paper

KONERU LAKSHMAIAH COLLEGE OF ENGINEERING (AUTONOMOUS)
DEPARTMENT OF info SCIENCE AND TECHNOLOGY
MODEL ques. PAPER
Year: III/IV B.Tech Max marks: 60M
Academic Year: 2008-09 Semester-II
Subject & Code: Design & Analysis of Algorithms, IT 321 Duration: three hr


UNIT-I
1. Sort the subsequent numbers according to Quick Sort {3,1,4,1,5,9,2,6,5,3,5,8,9} and write an algorithm for it.
(OR)
2. a)Write short notes on Randomized Algorithms
b) discuss about Binary Search with an example and write an algorithm for it.

UNIT-II
3.Explain about minimum cost spanning trees with examples and write the algorithms.
(OR)
4.a) Write short notes on Job Sequencing with deadlines.
b) What is the solution generated by the function Job Sequencing (JS) when n=7.
(p1,p2…p7)=(3,5,20,18,1,6,30) and (d1,d2…d7)=(1,3,4,3,2,1,2)?

UNIT-III
5. Write the algorithm for multistage graph using forward and backward approach with example.
(OR)
6. discuss the traveling salesperson issue with example.

UNIT-IV
7. discuss 8-Queens issue with an example and also write algorithm for it.
(OR)
8. a)Let n=4 and (a1,a2,a3,a4)=(cout,float,if,while) with p(1:4)=(1/20,1/5,1/10,1/20) and q(0:4)=(1/5,1/10,1/5,1/20,1/20).Draw the optimal Binary Search tree for the above issue.
b) define Connected Components and Spanning Trees with suitable example

UNIT-V
9. discuss 8-Queens issue with an example and also write algorithm for it.
(OR)
10. discuss about NP- hard graph issues.

Earning:   Approval pending.