Reg. No.
B.E. B.Tech. DEGREE EXAMINATION, MAY 2017
Fourth Semester
Information Technology
01UIT402 ANALYSIS AND DESIGN OF ALGORITHMS
(Regulation 2013)
Duration: Three hours Maximum: 100 Marks
Answer ALL Questions.
PART A (10 x 2 20 Marks)
1. What is meant by linear search?
2. Define Big O notation.
3. Differentiate time complexity from space complexity.
4. What are the two principal variations of algorithm visualization?
5. What is the quick sort?
6. What is divide and conquer technique?
7. Differentiate greedy method and dynamic programming.
8. What is a Huffman code and tree?
9. Define sum of subset problem.
10. Define state space tree.
PART B x 16 80 Marks)
11. What is an algorithm? With a neat diagram, explain the various stages of algorithm design and analysis process.
Question Paper Code: 31842
2
31842
Or
What are asymptotic notations? Explain in detail.
12. What is the mathematical analysis of recursive algorithms? Explain about the tower of Hanoi problem.
Or
Write a recursive algorithm to find sum of the first n cubes and obtain its time complexity.
13. What are the differences between DFS and BFS? Solve topological sorting problem using DFS algorithm with an example.
Or
Give a suitable example and explain the depth first search algorithm.
14. Define the three variations of transform and conquer algorithms. Construct an AVL tree for the list by successive insertions. State four rotation types used in the construction of the AVL tree and explain the same.
Or
Explain the Prim's algorithm and Kruskal's algorithm with suitable example to obtain minimum spanning tree.
15. Explain how traveling salesman problem can be solved using branch and bound method.
Or
How is dynamic programming applied to solve the traveling salesman problem? Explain in detail with an example.