Jawaharlal Nehru Technological University Kakinada 2009-1st Sem B.Tech Computer Science and Engineering Code No: V3123 / R07 IIIRegular s,– DESIGN AND ANALYSIS OF ALGORITHMS (Co

Code No: V3123 / R07

III B.Tech. I Semester Regular Examinations, November – 2009

DESIGN AND ANALYSIS OF ALGORITHMS
(Computer Science & Engineering)
Time: three hours Max. Marks: 80

ans Any 5 of the subsequent
All ques. carry equal marks
*****

1. (a) what is meant by algorithm? discuss about the criteria's for an algorithm.
(b) compute space and time complexity for matrix multiplication algorithm.[8+8]

2. (a) discuss about simple obtain and union algorithms with examples.
(b) What is meant by connected components? discuss.[10+6]

3. Write an algorithm for quick sort? obtain the best, avg. and worst case complexity for quick
sort.[16]

4. (a) write prim's algorithm for minimum spanning tree?
(b) obtain the time complexity for minimum spanning tree.[12+4]

5. Using algorithm OBST calculate W (i, j), R (i, j) and C (i, j), 0<=I < j <=4 for the
identifier Set (a1,a22,a3,a4)= (end, goto, print, stop) with P(1)=1/20,P(2)=1/5,
P(3)=1/10, P(4)=1/20, Q(0)=1/5,Q(1)=1/10,Q(2)=1/5,Q(2)=1/20,Q(4)=1/20.
Using the R (i, i) s construct the optimal binary search tree.[16]

6. (a) replace the general backtracking control abstraction, so that they obtain only a
Single solution rather than all solutions.
(b) What is meant by graph coloring? discuss with example. [8+8]

7. Write an algorithm for LC branch and bound to obtain minimum cost ans node. And also discuss
using an example.[16]

8. ans the subsequent
(a) Non deterministic algorithms
(b) NP-Hard issues
(c) NP-Complete issues [5+6+5]

Earning:   Approval pending.