Anna University Chennai 2011-4th Sem B.E Computer Science and Engineering /B.Tech, EMR/EMR ,CS 2251--DESIGN AND ANALYSIS OF ALGORITHMS (Regulation 2008) , . - 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 : 3 hours Maximum : 100 Marks


Answer ALL ques..

PART A--(10 x two = 20 marks)

1. What do you mean by linear search?

2. What is the properties of big-Oh notation.

3. What is greedy algorithms?

4. What Knapsack problems?

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? provide an example.

10. What is NP Completeness?


PART B--(5 x 16 = 80 marks)


11. (a) (i) describe Asymptotic notations.Distinguish ranging from Asymptotic notation and conditional lasymptotic notation . (10)
(ii) discuss how the removing condition is done from the conditional Asymptotic notation with an example. (6)

Or
(b) (i) discuss how analysis of linear search is done with a suitable illustration. (10)
(ii) describe recurrance formula and discuss how solving recurrence equations are done (6)


12. (a) What is divide and conquer strategy and discuss the binary search with suitable example issue. (16)
Or
(b) Distinguish ranging from Quick Sort and Merge Sort, and organize the subsequent numbers in increasing order using merge sort. (18,29,68,32,43,37,87,24,47,50) (16)


13. (a) (i) discuss the multistage graph issue with an example. (8)
(ii) obtain 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) define binary search tree with 3 traversal patterns? provide suitable examples with neat diagram for all 3 traversal of binary search. (16)


14. (a) (i) How does backtracking work on the eight Queens issue with suitable example? (8)
(ii) discuss elaborately recursive backtracking algorithm? (8)

Or
(b) what is Hamiltonian problem? discuss with an example using backtracking.(16)


15. (a) write a complete LC branch-and -bound algorithm for the job sequencing with dadlines issue. Use the fixed tuple size formulation (16)
Or
(b) Write a non- deterministic algorithm to obtain whether a provided graph contains a Hamiltonian cycle. (16)

-----------------

Earning:   Approval pending.