Anna university chennai’s latest question papers of Design and Analysis of Algorithms is free download for 2nd year engineering students. This DAA May/June 2012 question paper is for Common to all computer science and engineering and B.Tech information technology students.
Question Paper Code : 10263
B.E/B.Tech. DEGREE EXAMINATION, MAY/JUNE 2012
Computer Science and Engineering
CS 2251/141401/CS 41/CS 1251/10144 CS 402/0802300013 – DESIGN AND ANALYSIS OF ALGORITHMS
Time : Three Hours Maximum: 100 marks
Answer ALL questions.
PART A – ( 10 x 2 = 20 marks )
- Define Big ‘Oh’ notation.
- What is meant by linear search?
- What is the drawback of greedy algorithm?
- What is the time complexity of binary search?
- State principle of optimality.
- Differentiate greedy method and dynamic programming.
- What is the difference between explicit and implicit constraints?
- Define the basic principles of back tracking.
- What is an articulation point in a graph?
- What is the difference between BFS and DFS methods?
PART B – ( 5 x 16 = 80 marks )
- (a) Discuss in detail all the asymptotic notations with examples.
(b) with a suitable example, explain the method of solving recurrence equations.
2. (a) Explain divide – and – conquer method with merge sort algorithm. Give an example.
(b) Explain how greedy method can be applied to solve the Knapsack problem.
3. (a) With a suitable example, explain all – pair shortest paths problem.
(b) How is dynamic programming applied to solve the traveling salesperson problem? Explain in detail with an example.
4. (a) Explain the algorithm for finding all m-colorings of a graph.
(b) Write down and explain the procedure for tackling the 8 – queens problem using a backtracking approach.
5. (a) Discuss in detail about the biconnected components of a graph.
(b) Compare and contrast FIFO and LC branch – and – bound search techniques.