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

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

4 pages, 24 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 Examination o) December,2A08 @ r-l o) c) MCS-031:D ESIGN A ND A NALYSIS O F ALGORITHMS Time : 3 hours Note : Maximum Marks : L00 n Q uestion umber1 ,i s c ompulsory.A ttempt a ny t hree questions s from therest. All algorithrns houldbewritten nearerto C/C++ language. Parts of the samequestion should be attemptedtogether. 1. (a) (0 (ii) W hat i s t he d ifference b etween a O(big-oh) a nd O (little-oh) n otations. Which o f t hese n otations i s n ot asymptotically tight Arrange the following in the order of worst to best efficiency : (b) (c) O O(nIogn), O (Zn),O (tog n 21, 1n27 Write an algorithm (an informal algorithm is sufficient) to find the ith order statistic, which ensures that the worst caserunning time to selectan element isO(n), i.e., linear. (0 D iscuss i nformally t hat a r ecursive solution to matrix-chain multiplication is exponential in nature. (ii) If, both dynamic programming and grebdy approaches are applicable to a g iven p roblem, t hen w hich approach w ould g enerally g ive a faster solution, and why ? (d) W hat i s t he b enefit o f r andomization i n quicksort algorithm ? (e) What are non-regular languages ? Can we use c ontext f ree g rammar t o g enerate regular as well as non-regular languages ? (f) 2. If yes, then give an example of each. \tVhat is the difference between polynomial time and non-polyriomial time algorithms ? (a) D iscuss t he r ole o f o ptimal s ubstructure property in applying a greedy algorithm to solve a given problem. (b) (0 Analyze the worst case running time of merge sort on n numbers. (ii) Given an array of elements : 5 12 , 9 , 4 , 3 , 7 ,6 , 8 If we apply quick sort algorithm on the a bove a rray t hen, w hat i s t he minimum and maximum number of times, e ach e lement w ould b e (c) compared to others. Write Dijkstra's Algorithm to find shortest path t o a g iven n ode i n a n u ndirected weighted graph. 3. ( u) E xplain h ow b inary s earch a lgorithm . performs more efficiently than linear search algorithm. Compare their running times. (b) Write a recursive function to find/calculate the sum of all elementsin an integer aftay. (") Describe,how alpha betapruningsaves time as c ompared t o m inimax-procedure i n a two player game. You can use an example. (d) 4. W hat i s p reconditioning ? E xplain h ow preconditioning i s u seful i n f inding a solution to a problem. ( a) Design a t uring m achine t hat a ccept collection of all strings with an even number of a's and an even number of b's over the alphabet2 : { a, b }. (b) Using K ruskal's a lgorithm, c onstruct a minimum spanning tree from the following graph: (") W tite a c ontext f ree g rammar t hat c an generate the language represented by the regular e xpression( b*a b *a ! *)* J. (u) (b) W hile a pplying D epth F irst S earch i n a directed g raph, h ow d o w e d ifferentiate between a cross edge and a forward edge with respect to the discovery time (i.e., the time at which a vertex become known) of its end vertices. (r) What language is represented by the (ii) (c) (d) regular e xpression6 *a ! *(ab*ab*)*. Define pumping lemma for regular languages. \A/hat is the difference between divide and d ynamic conquer a pproach a nd programming approach to solve.problems. Define a n N P-hard p roblem. G ive a n example also. -oOo-

Formatting page ...

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