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
Fourth Semester
Computer Science and Engineering
CS 2251/141401/CS 41/CS 1251/10144 CS 402/0802300013 – DESIGN AND ANALYSIS OF ALGORITHMS
(Regulation 2008)
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.
OR
(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.
OR
(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.
OR
(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.
OR
(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.
OR
(b) Compare and contrast FIFO and LC branch – and – bound search techniques.
———————————