** May - 2008 DESIGN & ANALYSIS OF ALGORITHMS Question paper****2008 OSMANIA UNIVERSITY M.C.A COMPUTER APPLICATIONS**MCA II YEAR II SEMESTER (New) MAIN EXAMINATION

May - 2008

DESIGN & ANALYSIS OF ALGORITHMS

CODE NO. : 3828/N

Time : 3 Hours

Max. Marks : 80

Note : Answer one question from each unit. All questions carry equal

marks.

UNIT - I

1. (a) Briefly explain how to analyze algorithms. [Marks 8]

(b) What is Heap ? How to delete an element from the Heap ? [Marks 8]

OR

2. (a) Define the following notations

(i) BigOh

(ii) Omega

(iii) Theta [Marks 8]

(b) Write an algorithm to add an element to a circular queue. [Marks 8]

UNIT - II

3. Write the quick sort algorithm using divide and conquer strategy. [Marks 16]

OR

4. What is minimum spanning tree ? Write Prim's algorithm for finding minimum

spanning tree. [Marks 16]

UNIT - III

5. Write BFS and DFS algorithms. Explain their working with suitable examples. [Marks

16]

OR

6. Write an algorithm to find an Optimal Binary Search tree using dynamic programming.

[Marks 16]

UNIT - IV

7. What is M-Colorability optimisation problem ? Write an algorithm that finds all MColorings

of a

Graph. [Marks 16]

OR

8. Explain how the branch and bound technique can be used to solve 0/1 Knapsack

problem. [Marks 16]

UNIT - V

9. State and prove Cook's Theorem. [Marks 16]

OR

10. What is Directed Hamiltonian Cycle ? Prove that CNF - Satisfiability reduces to

Directed Hamiltonian

Cycle. [Marks 16]