Osmania University (OU) 2007 M.C.A Computer Design And Analysis Of Algorithms - Question Paper

DESIGN AND ANALYSIS OF ALGORITHMS
UNIT -1
1. a) discuss how do you translate a recursive procedure to a non
Recursive equivalent procedure.
b) Write an algorithm for performing binary search for any element in an array.
2. a) Write an algorithm which computes the sum of 'n' fibonacci
numbers. find its time complexity.
b) Write an algorithm for a Boolean function which takes an array A(l : n),n > 1, of zeros and ones and determines if the size of every sequence of consecutive ones in even. What is the computing time of the algorithm ?
UNIT - n
3. a) Write an algorithm which uses divide and conquer method for
finding the maximum and minimum items in a set of an elements. -
b) Write an algorithm which multiplies 2 nx.n matrices using 0(n3) operations. Determine the precise number of multiplications, additions and array olomont accossos. .
4. n) Write an algorithm for tho iterative version of quick sort, explain
its time and space complexity.2
b) On what input data does quick sort exhibit its worst case behaviour. discuss your ans.



UNIT - III
5. a) Write an algorithm for 0/1-knapsack issue.
b) Do the analysis of the above algorithm.
6. H) Write a solution for the traveling salesmen issue. explain the time complexity of the solution.
b) find that the computing time of the algorithm for optimal binary search-tree
UNIT - IV
7. a) Write an algorithm for finding Hamiltonian cycles of a graph.
b) provide a backtracking solution to the 0/1 Knapsack issue.
8. a) Write an algorithm which provide all solutions to the n— queens
problem.
b) Determine the order of magnitude of the worst case computing time for the back tracking procedure which obtains all Hamiltonian Cycles.
UNIT - V
9. Obtain a non-deterministic algorithm of complexity 0 (n) to determine
whether or not there is a subset of the n number ai,1<=i<=n that
sums to M.
10. Briefly discuss the subsequent problems:
a) Node cover issue.
b) NP-hard and NP-complete issues.

Earning:   Approval pending.