Anna university chennai’s **latest question paper**s 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**.

———————————