Osmania University (OU) 2008-2nd Year M.C.A Computer Aplications II Sem (New) Design & Analysis Of Algorithms - Question Paper

Code No. : 3828/N

FACULTY OF INFORMATICS
MCA II YEAR II SEMESTER (New) Main exam
May - 2008
DESIGN & ANALYSIS OF ALGORITHMS

Time : three Hours] [Max. Marks : 80


Note : ans 1 ques. from every unit. All ques. carry equal marks.



UNIT - I

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

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


OR

2. (a) describe the subsequent 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. discuss their working with suitable examples. [Marks 16]

OR

6. Write an algorithm to obtain an Optimal Binary Search tree using dynamic programming. [Marks 16]


UNIT - IV

7. What is M-Colorability optimisation issue ? Write an algorithm that obtains all M-Colorings of a
Graph. [Marks 16]

OR

8. discuss how the branch and bound technique can be used to solve 0/1 Knapsack issue. [Marks 16]


UNIT - V

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

OR

10. What is Directed Hamiltonian Cycle ? Prove that CNF - Satisfiability decreases to Directed Hamiltonian
Cycle. [Marks 16]

Earning:   Approval pending.