Anna University Resultssss

Welcome to Engineering Website where you can get all the stuffs related to anna university

Research Papers

All national conference research papers are at your finger tips. ...

Acadamic Information

All acadamic information for all years and all semester

Distance Education

DODE: Distant education is not so far its too close .....

Board Of Members

Information of all the important peoples on the game at this site. updated regularly.

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

Posted by NaveeN - - 0 comments



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)

Leave a Reply