Osmania University (OU) 2008-2nd Year M.C.A Computer Aplications II SEMESTER (OLD) DESIGN AND ANALYSIS OF ALGORITHMS - Question Paper

Code NO.3821/O
FACULTY OF INFORMATICS
MCA II YEAR II SEMESTER (OLD) exam
May 2008
DESIGN AND ANALYSIS OF ALGORITHMS

[TIME:3 Hours] [Max.Marks:80]

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

UNIT -I
1.Define the 3 asymptotic measures used ti specify the time and space complexity of algorithms and provide a brief of every.
List a few time complexity specifications in the order of their merit.
OR
2.What is a Heap. provide insertion and deletion algorithm for a heap.Illustrate ADJUST with an example.
UNIT-II
3.What is devide-and-conquer strategy.How is it applied in quick sort.
Apply quick sort algorithm to sort the subsequent list of keys.
(28,12,30,45,20,70,15,60)
OR
4.Write greedy optimal merge trend algorithm and discuss the identical with an example.
UNIT-III
5.(a) Formulate reliability design issue as a dynamic programming issue.
(b) discuss about game trees. Use an example.
OR
6. Briefly argue how principle of optimality holds for 0/1 knapsack issue.
Generate the sets s(i) ,0<=i<=1 where (w1,w2,w3,w4)=(10,15,6,9) and (p1,p2,p3,p4)=(2,5,8,1).
State the purging rules used.If knapsack capacity is m=25, what is the optimal solution.
UNIT-IV
7. discuss 8-Queens issue and write an algorithm to solve identical.
OR
8.Following cost matrix is described for a travelling salesperson issue.Obtain decreases cost matrix and state tree generated by LCBB method. tag every node with cost estimate.
- seven 13 12 8
three - six 14 9
five eight - six 18
nine three five - 11
18 14 nine eight -

(- infinite symbol)
UNIT-V
9.(a) describe P.NP,NP-complete and NP-hard issues.Draw Venn diagramm illustrating the common believed among them.
(b) State Cook's theorem and prove the identical.
OR
1. what is decision problem?Show that CNF-Satisfiablity decreases to clique decision issue.

Earning:   Approval pending.