Osmania University (OU) 2007-2nd Sem M.Sc Computer Science ister SUB: DAA - Question Paper

SECTION-A

1.What is algorithm? describe Time Complexity and Space Complexity of Algorithms.
2.Explain hashing with examples.
3.Explain binary search tree with example.
4.Find minimum and maximum merge sort.
5.Explain reliability design issue.
6.Explain travelling salesman issue.
7.Define Back travelling . discuss 8-queens issue.
8. What is NP-hard and NP-completeness?

SECTION-B

9. (a) What is data structure ? discuss sorting and searching algorithms for a heap sort with example.
OR
(b) discuss sets representation,UNION,FIND operations in detail.

10. (a) define divide- and - conquer method
11,2,9,13,57,25,17,1,90,30 sort the provided elements using selection sort and write the complexity of selection sort.
OR
(b) explain a minimum spanning tree with example. List its advantages.

11. (a) What is O/I knapsack ? explain game trees in detail.
OR
(b) What is multistage graph? discuss difference ranging from disconnected components and depth-first search with example.

12. (a) define Coole's theorem.
OR
(b) discuss the subsequent with example:
(i) Graph coloring
(ii) Hamitonian cycles

Earning:   Approval pending.