CS2251 DESIGN AND ANALYSIS OF ALGORITHMS NOV/DEC 2014 EXAMINATION - REGULATION 2008

CS 2251 DESIGN AND ANALYSIS OF ALGORITHMS

NOV/DEC 2014 EXAMINATION

4TH SEMESTER CSE

REGULATION 2008

PART A - (10 x 2 = 20 marks)

1. Define theta notation.
2. What is meant by substitution method?
3. Differentiate linear search and binary search techniques.
4. Define knapsack problem.
5. What is meant by principle of optimality?
6. Define cost of a tour.
7. Differentiate live and dead nodes.
S-. What is a Hamiltonian cycle?
9. State the difference between FIFO and LC branch-and-bound algorithms.
10. Where do you apply problem reduction method?

PART B (5 x 16 = 80 marks)

11. (a) DISCUSS the properties of big Oh notation.

Or

(b) With an example, explain how recurrence equations are solved.

12. (a) Explain binary search algorithm with an example. (16)

Or

(b) Write down the algorithm for merge sorting. Explain how the following elements get sorted. (16)
(310, 285, 179: 652, 351, 423, 861, 254, 450, 520)

13.(a) (i) Explain multistage graphs with an example. (8)
(ii) Write notes on optimal binary search trees. (8)

Or

(b) Consider the Travelling Salesperson instance defined by the following cost matrix.
(Download the Question Paper to view the Image)

Draw the state space tree and show the reduced matrices corresponding to each of the. node. (16)

14. (a) Explain 8 Queens problem, with an example. (16)

Or

(b) Explain graph coloring with the following graph. (16)

15. (a) Write notes on Connected components and Spanning trees (16)

Or

(b). Consider the knapsack iristance n = 3, (w l, w2, w3) = (2,3,4), (p1, p2, p3) = (1,2,5) and m = 6. Explain 0/1 knapsack algorithm to solve the above
instance. (16)