Design And Analysis of Algorithms 4th ND11 CS2251

Reg. No. : 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. ANNA UNIVERSITY SYLLABUS - Click Here Other Links: TANCET Papers – Click Here PSU Exam Papers - Click Here Gate Exam papers – Click Here Jobs & Placement papers – Click Here Other Departments Papers: Click Here Download PDF File - Click Here For More Question paper of CSE -  CLICK HERE 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)

URL: http://feedproxy.google.com/~r/blogspot/iusl/~3/K-LrPvihaDw/design-and-analysis-of-algorithms-4th.html