Trending ▼   ResFinder  

IGNOU UNIVERSITY MCA - II (SEM 3) DEC 2009 : Design and Analysis of Algorithms

3 pages, 19 questions, 0 questions with responses, 0 total responses,    0    0
mca_india
   		+Fave Message
ProfileTimelineUploadsQ & A
 Home > mca_india >

Formatting page ...

IMCS-0311 MCA (Revised) Term-End Examination December, 2009 -14 MCS-031 : DESIGN AND ANALYSIS OF ALGORITHMS Maximum Marks : 100 Time :`3 hours Note : Question No. 1 is compulsory. Attempt any three questions from the rest. (a) (i) Write Euclid's Algorithm to find GCD of two positive integers. 4 (ii) Differentiate between 'problem and 'instance' with an example each. 4 (i) What is recursion ? Compare the recursive method and non recursive method to find factorial of an integer. 4 (ii) Give asymptotic upper bound for 1. 4 T(n)= 2T (%) + n 3 for n > 2 n<_2 =1 Prove the equality .= z S(n) 20+ 21.+ .. 2n-1=mn_ 1 for n?. -1 using Mathematical Induction. MCS-031 1 6 P.T.O. (i) Given f (x) = 2x 3 + 3x 2 + 1 Show that f (x) = 0 4 (x3) and f (x) # 0 (y2) (ii) Write an algorithm for insertion sort on an array of size n. Estimate the best case running time of insertion sort. 6 (i) Give a regular expression for strings containing exactly two is over the alphabet / ={0, 1}. 4 (ii) Define Finite Automata. 4 (a) Explain the Divide and Conquer technique 10 of solving problem with reference to merge sort algorithm. (b) Write an algorithm for finding spanning tree 10 of a connected graph. (a) Explain the Randomized quick sort 10 algorithm. Find the number of comparisons for sorting A = [9, 7, 6, 8, 1, 2] using randomized quick sort. Give the average case analysis for running time of quick sort. MCS-031 5 5 2 (a) Obtain the DFS tree for the following graph. 10 Compute the discovery time and finishing time for each vertex. (b) Explain the Algorithm for topological sort. 10 Can the topological sort be applied to the graph ? If yes obtain the topological ordering for the same. (a) Define NP-complete & problems. Define vertex cover problem for a given graph G= (V, E). 5 5 Explain the gerieral steps in establishing 10 NP-completeness proof of a given problem. -o0o- MCS-031 3

Formatting page ...

Formatting page ...

 

  Print intermediate debugging step

Show debugging info


 

Additional Info : Mca - II (sem 3) December 2009 Question Paper - Design and Analysis of Algorithms(Revised Course)
Tags : mca exam papers, mca question papers, ignou mca question papers, ptu mca question papers, mca sample question paper, mca mumbai university question papers, mca exam syllabus, mca exam question paper, online mca exam papers, online mca exam preparation, mumbai university mca question papers, ignou university mca question papers  


© 2010 - 2025 ResPaper. Terms of ServiceContact Us Advertise with us

 

mca_india chat