B.E "/B.Tech. DEGREE EXAMINATION, MAY/JUNE 2006.
Third Semester Computer Science and Engineering
CS 1201 - DESIGN AND ANALYSIS OF ALGORITHMS
(Common to B.E. (P.T.) R 2005 Second Semester Computer Science and Engineering) (Regulation 2004)
Time : Three hours Maximum : 100 marks
Answer ALL questions.
PARTA-(10 x2=20 marks)
1. Define algorithm.
2. What is Big'Oh'notation?
3. What is an activation frame?
4. Define external path length.
5. Give the recurrence equation for the worst case behavior of merge sort.
6. Name any two methods for pattern matching.
7. When do you say a tree as minimum spanning tree?
8. How will you construct an optimal binary search tree?
9. Define backtracking.
10. What is Hamiltonian cycle in an undirected graph?
PARTB-(5x16=80marks)
11. (i) Explain the various criteria used for analyzingalgorithms. (10)
(ii) List the properties of various asymptotic notations. (6)
12. (a) (i)Explain the necessary steps for analyzing the efficiency of recursive algorithms.
(10)
(ii)Write short notes on alsorithm visualization. (6)
Or
(b) (i)Explain the activation frame and activation tree for finding the fibonacci series.(10)
(ii)What are the pros and cons of the empirical analysisof algorithm?(6)
13 a(i) Sort the following set of elements using Quick Sort. (10)
L2,24,8,71, 4,23,6
(ii) Give a detailed note on divide and conquer techniques. (6)
Or
(b)(i) Write an algorithm for searching an element using binary search
method. Give an example. (I2)
(ii) Compare and contrast BFS and DFS. (.4)
14 (a)Explain the method of finding the minimum spanning tree for a
connected graph using Prim's algorithm. (16)
Or
(b)How will you find the shortest path between two given vertices using
Dijkstra's algorithm? Explain. (16)
15. (a) (i) Describe the travelling salesman problem and discuss how to solve
it using dynamic programming. (10)
(ii) Write short notes on n-Queen's problem. (6)
Or
(b) Discuss the use of Greedy method in solving Knapsack problem and
subset-sum problem. (16)
0 comments:
Post a Comment