**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)**

## 0 comments:

Post a Comment