a knowledge trading engine...

Rajiv Gandhi Proudyogiki Vishwavidyalaya 2008-4th Sem M.C.A Computer Aplications .(ester) ,., - Question Paper

Monday, 28 January 2013 10:50Web

Page 1 of 5

MCA-404
M.C.A.(Fourth Semester) EXAMINATION,Dec.,2008
DESIGN AND ANALYSIS OF ALGORITHMS
(MCA-404)
Time : 3 Hours
Maximum Marks : 100
Minimum Pass Marks : 40

Note : ques. paper is divided into 5 Units. Attempt 1 ques. from every Unit. All ques.
carry equal marks.

Unit - I
1.(a) Write in brief about the significance of the subsequent notations :
(i) big 'O' (ii) ?
(iii) 'T' (iv) small 'o'
(v) 'w'
(b) Write an algorithm to evaluate a polynomial at point x0 using minimum number of multiplications.
(Use Horner's rule A(x0) = (....anx0 + an-1)x0 + (....a1) x0 + a0.
Or
2.(a) Write a detailed note on performance analysis and performance valuation.
(b) Write an alogrithm to delete an element x from a binary search tree. What is the time
complexity of your algorithm ?

Unit -II
3.(a) Prove that the recurrence relation T(n) = mT (n/2) + an2 is satisfied by T(n) = O(nlognm).
(b) Write a non-recursive algorithm for the preorder traversal of a binary tree t. elaborate the
time and space requirements of your algorithme ?
Or
4.(a) Using divide and conquer technique write recursive algorithm to obtain the maximum and minimum
elements in a provided array. Also obtain its time complexity.
(b) Using the idea of BFS devise an algorithm to obtain the shortest cycle containing a provided
vertex v. Prove that your algorithm obtains the shortest cycle.

Unit - III
5.(a) Applying Greedy method obtain an optimal solution to the knapsack instance n= 7, m = 15,
(p1,p2,p3...p7) = (10,5,15,7,6,18,3) and (w1,w2,w3....w7) = (2,3,5,7,1,4,1).
(b) What is Prism algorithm ? calculate a minimum cost spanning tree for graph provided beneath using
Prism algorithm :

Or
6.(a) Use algorithm shortest paths to find in non-decreasing order the lengths of the shortest
paths from vertex one to all remaining vertices in the digraph provided beneath.

(b) Write LC branch and bound algorithm for the knapsack issue. Determine its time complexity.

Unit - IV
7.(a) How dynamic programming can be applied to travelling salesperson issue ? obtain the length of
the optimal tour of the subsequent graph, the edge lengths are provided by the subsequent matrix.

(b) What is backtracking ? discuss eight queens issue with example.

Or
8.(a) What is all pair shortest path issue ? provide suitable example based on dynamic programming.
Write algorithm and explain its time complexity.
(b) Solve matrix chain multiplication using dynamic programming.

Unit - V
9 discuss the subsequent terms :
(i) Complexity measure
(ii) Polynomial and non-polynomial time complexity
(iii) Complexity class
(iv) NP-hard class
Or
10.(a) What is AND/OR graph decision issue ? provide suitable example.
(b) Prove that travelling salespersons issue is NP-complete.