CS 1201 - DESIGN AND ANALYSIS OF ALGORITHMS QUESTION PAPERS

B. E.lB.Tech" DEGREE EXAMINATION, MAY/JUNE 2007 .
Third Semester
(Regulation 2004)
Computer Science and Engineering
CS 1201 - DESIGN AND ANALYSIS OF ALGORITHMS
(Common to B.E. Part Time, Second Semester-Regulation 2005)
Time : Three hours Maximum : 100 marks

Answer ALL questions.
PARTA-(10 x2=20 marks)
1. Defrne an algorithm.
2. Define order of an algorithm.
3. Define loop.
4. What is recursive call?
5. What are the objeciives of sorting algorithms?
6. Why is bubble sort called by that name?
7. Define AVL tree.
8. What is a minimum cost spanning tree?
9. What is meant by optimal solution?
10. What do you mean by row major and column major?

PARTB-(5x16=80marks)
11. (a) Describe briefly the notions of complexity of an algorithm. (16)
(b) (i)What is pseudo-code? Explain with an example. (8)

(ii)Find the complexity (C(n)) of the algorithm for the worst case, best
case and average case. (evaluate average case complexity for n = 3,
where n is number of inputs)(8)
12. (a) Write an algorithm for a given numbers n to generate the nth number of
the Fibonacci sequence. (16)
Or
(b)Explain the pros and cons of the empirical analysis of algorithm. (16)
13. (a)(i) Write an algorithm to sort a set of " M "numbers using insertion sort.(8)
(ii) Trace the algorithm for the following set of numbers : 20,35, 18, 8,L4,4L,3, 39. (8)
14. (a) Write the Dijikstra's algorithm.(16)
Or
(b) Explain KRUSKAL'S algorithm.(16)
15. (a) What is back tracking? Explain in detail.(16)
Or
(b)What is branch and bound? Explain in detail. (16)

FEEL USEFUL PLEASE GIVE +1