ANALYSIS OF ALGORITHMS (AOA) MAY 2009 COMPUTER AND SCIENCE SEMESTER 4
Con.3546-09 (REVISED COURSE) VR-3783(3 Hours) [Total Marks :- 100]
N.B.: (1) Question No.1 is compulsory.
(2) Attempt any four questions out of remaining six questions.
(3) Assumptions made should be clearly stated.
(4) Figures to the right indicate full marks.
(5) Assume suitable data wherever required but justify the same.
1. (a) An algorithm takes 0.5 ms for input size 100. How long it will take for input size 500 if the
running time is - [5 Marks]
(i) Quadratic (ii) NlogN
(b) Explain strassen's matrix multiplication. [5 Marks]
(c) State advantages and disadvantages of recursion. [5 Marks]
(d) prove that worst case efficiency of quick sort is O(n2). [5 Marks]
2. (a) Explain Radix sort algorithm with example. Give its complexity. [10 Marks]
(b) Explain Boyer-Moore method. Give its advantages over Brute-Force method. [10 Marks]
3. (a) Explain how branch and bound method can be applied to 15 puzzle problem using LC search.
Write it's algorithm. [10 Marks]
(b) Explain graph coloring algorithm with backtracking. [10 Marks]
4. (a) Explain Merge sort algorithm. Sort following numbers with merge sort. Give output of
each pass. [10 Marks]
84, 25, 36, 15, 48, 09, 17, 55, 92, 36
(b) Explain 8-queen problem. Write a algorithm using backtracking to solve this
problem. [10 Marks]
approach. [10 Marks]
6. (a) What is branch and bound method? Discuss the solution to Travelling salesman problem using
branch and bound method. [10 Marks]
(b) What is multistage graph problem? Discuss its solution based on dynamic programming
approach. [10 Marks]
7. (a) Write note on "Tries" [10 Marks]
(b) (i) Compare Greedy method and Dynamic programming. [5 Marks]
(ii) Write in brief about 'Divide and Conquer' strategy. [5 Marks]
No comments:
Post a Comment