
	Trending ▼ ICSE CBSE 10th ISC CBSE 12th CTET GATE UGC NET Vestibulares ResFinder

IGNOU UNIVERSITY MCA - II (SEM 3) JUN 2009 : Design and Analysis of Algorithm

4 pages, 21 questions, 0 questions with responses, 0 total responses,

	mca_india	+Fave Message
	Profile Timeline Uploads Q & A

Home > mca_india >

Formatting page ...

MCA (Revised) Term-End E xamination |une, 2009 \O C! MCS-031: D ESIGN A ND A NALYSIS O F ALGORTTHMS Maximum M arks : 7 00 Time : 3 h ours Note : 1. Q uestion N o. 1-i s c ompulsory. Attempt a ny t hree questions f i'onr the r est. (a) (i) Enumerate f ive i mportant c haracteristics o f a n A lgorithm. (ii) (b) W rite a r ecursive p rocedure t o f ind the sum of first n natural numbers. ( i) S tate T ravelling S ales P ersons problem. C omment o n t he n ature o f solution t o t he p roblem. (ii) You are given stampsof value Rs.5 and Rs. 6 . S how t hat a ny a mount > R s. 2 0 can b e r ealized u sing s tamps o f R s. 5 and Rs. 5. Use MathematicalInduction for the proof. MCS-03L P.T.O. (i) W rite t he n on-recursiveb inary s earch procedure. (ii) ( c) S olve t he r ecurrence ) r (n:2r (,/r)* -1 (d) (i) " n >Z rt <2 Obtain t he m inimum c ost s panning tree f or t he f ollowing g raph u sing PRIMS a lgorithm. Obtain t he B FS t ree f or t he a bove graph, g iven i n d ( i). Write a c ontext f ree g rammar t o generatep alindromes o f e ven l ength Over a lphabet I - { a, b }. (i') 2. (u) Write t he f i nite a utomata corresponding t o t he r egular expression( a+b)*ab. Derive t he p rinciple multiplication MCS-031 o f o ptimality of matrix chain. f or (b) (c) 3. Compute t he o ptimal n o . o f s c a l a r multiplications r equired to m ultiply t he following m atrices. 1.0 4'L o f o rder 3 0 x 3 5 A2 o f o rder 3 5 x 1 5 A3 o f o rder 1 5x 5 Give t he l ist i n e achi teration f or s orting t he list 9 0, 4 2, 4 1, 1 .20, A,50 u sing s election 6 sort. (u) E xplain t he C homsky's C lassification o f grammars. 10 (b) W hat i s a n a mbigous g rammar ? H ow d o you prove that a given grafiunar is ambigous ? 10 Explain w ith a n e xample. 4. (u) If L 1 a nd L , a re c ontext f ree l anguages t hen, c prove t hat L , U l ,zis a c ontext f ree l anguage. (b) Define P ushdown A utomata. (c) Explain Decidable and Undecidable 5 10 problems. G ive e xample f or e ach. (u) C onstruct a t uring m achine t hat c opies a given s tring o ver { a, b }. F urther f ind a computation o f T M f or t he s tring ' aab'. (b) Explain the importance of asyrnptotic analysis f or r unning t ime o f a n a lgorithm. (.) J. W rite a n ote o n N P-hard p roblems. -oOo- MCS-031 10

Formatting page ...

Additional Info : Mca - II (sem 3) June 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

mca_india chat

Horizontal lines at:
Guest Horizontal lines at:
AutoRM Data:
Box geometries: