Osmania University (OU) 2010-2nd Sem M.C.A ii year, / design and analysis of algorithms - Question Paper

Code No. : 6816

FACULTY OF INFORMATICS

M.C.A. II Year, II Semester ( Main/Backlog) Examination, July 2010

DESIGN AND ANALYSIS OF ALGORITHMS

 

Time : 3 Hours ] [ Max. Marks : 80

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

UNIT-I

1.       (a) What is an algorithm ? What are the criteria to be satisfied by an algorithm ?

(b) What are the factors on which the execution time of a program depends ?

(c) Explain the big-o notation and its significance. (5+3+8)

OR

2.       (a) What are randomized algorithms ? Explain with the help of an example.

(b) What is a priority queue? Explain with the help of an example. (10+6)

 

UNIT-II

 

3.       Write an algorithm for merge sort. Also, find its time complexity. (16)

OR

4.       (a) Define the (Greedy) Knapsack problem. What is the trivial case of the problem ? Explain. (b) Explain how the Greedy Knapsack problem can be solved. Write the algorithm used.

(c) Define the problem Job sequencing with deadlines. (6+6+4)

 

UNIT-III

 

5.       What is Dyanamic Programming ? Explain ( with the help of an example) how an optimal binary search tree can be constructed using the technique of dyanamic programming. Derive the formulae used. (16)

OR

6.       Explain (with the help of an example) how the travelling salesman problem can be solved using the technique of dynamic programming. (16)

 

 

 

(This paper contains 2 pages) 1 P.T.O

 

UNIT-IV

 

7.       (a) Explain the technique of backtracking.

(b) Write an algorithm to find all solutions to the n-queens problem. (6+10)

OR

8.       (a) Explain the branch-and-bound method with the help of an example.

(b) What is a Hamlitonian Cycle ? Give an example. (12+4)

 

UNIT-V

 

9.       Distinguish between deterministic and non-deterministic algorithm. Write a non-deterministic algorithm for sorting n postive integers. (16)

OR

10.   (a) Distinguish between NP-hard and NP-complete problems giving one example for each. (b) Explain the satisfiability problem.

(c) Explain the clique decision problem. (6+6+4)

 

____________