DESIGN AND ANALYSIS OF ALGORITHMS CS2251 ANNA UNIVERSITY PREVIOUS YEAR QUESTION PAPER | CS 2251 DAA NOVEMBER/DECEMBER 2011 QUESTION PAPER

B.E./B.Tech. DEGREE EXAMINATION, NOVEMBER/DECEMBER 2011.

Fourth Semester

Computer Science and Engineering

CS 2251 — DESIGN AND ANALYSIS OF ALGORITHMS

(Regulation 2008)

Time : Three hours Maximum : 100 marks

Answer ALL questions.

PART A — (10 × 2 = 20 marks)

1. What do you mean by linear search?
2. What is the properties of big-Oh notation.
3. What greedy algorithms?
4. What Knapsack problem?
5. What is traveling salesperson problem?
6. What do you mean by multistage graphs?
7. State the general backtracking method?
8. What is graph cloning?
9. What is spanning tree? Give an example.
10. What is NP Completeness?

PART B — (5 × 16 = 80 marks)

11. (a) (i) Define Asymptotic notations. Distinguish between Asymptotic notation and conditional asymptotic notation. (10)
(ii) Explain how the removing condition is done from the conditional Asymptotic notation with an example. (6)

Or

(b) (i) Explain how analysis of linear search is done with a suitable illustration. (10)
(ii) Define recurrence equation and explain how solving recurrence equations are done. (6)
12. (a) What is divide and conquer strategy and explain the binary search with suitable example problem.

Or

(b) Distinguish between Quick sort and Merge sort, and arrange the following numbers in increasing order using merge sort. (18, 29, 68, 32, 43,37, 87, 24, 47, 50)
13. (a) (i) Explain the multistage graph problem with an example. (8) 
          (ii) Find an optimal solution to the knapsack instance n = 7, m= 15 (p1, p2, p3, ….p7) = (10, 5, 15, 7, 6, 18, 3) and (w1, w2, w3, ... w7) (2, 3, 5, 7, 1, 4, 1) (8)

Or

(b) Describe binary search tree with three traversal patterns? Give suitable example with neat diagram for all three traversal of binary search tree.. (16)
14. (a) (i) How does backtracking work on the 8 Queens problem with suitable example? (8)
(ii) Explain elaborately recursive backtracking algorithm? (8)

Or

(b) What is Hamiltonian problem? Explain with an example using backtracking. (16)


15. (a) Write a complete LC branch-and-bound algorithm for the job sequencing with deadlines problem. Use the fixed tuple size formulation. (16)

Or

(b) Write a non-deterministic algorithm to find whether a given graph contains a Hamiltonian cycle. (16)