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

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

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

	mca_india	+Fave Message
	Profile Timeline Uploads Q & A

Home > mca_india >

Formatting page ...

No. of Printed Pages : 4 MCS-0311 MCA (Revised) Term-End Examination N June, 2010 MCS-031 : DESIGN AND ANALYSIS OF ALGORITHMS Maximum Marks : 100 Time : 3 hours Note : Question No. 1 is compulsory. Attempt any three from the rest. (a) (i) What are the different methodologies should involved in the design of an algorithm. (ii) Arrange the following growth rates in the increasing order. 0(n 3), 0(1), 0(n2), 0(n log n). (b) (i) Draw the recursion tree for the following - and write the following. 1. 4 4 4 n T(n) = 4 T 12 + n2 in 0 notations. (ii) Use Master's method to find tight asymptotic bounds for the following recurrence : T (n) = T (n 1) + n MCS-031 1 4 P.T.O. (c) (i) (ii) (d) (i) (ii) (e) (i) (ii) MCS-031 For the following four matrices find the order of parenthesization for the optimal chain multiplication. A 1 = 15 x 5 A 2 = 5 X 10 A 3 = 10 X 20 A 4 = 20 x 25 A l . . . A4 are the matrices of given order. Give greedy algorithm for Huffman code. Give a divide and conquer based algorithm to find i th largest element in an array of size n. Find the minimum spanning for the graph using Prim's algo. Construct a turing machine that finds the sum of two natural numbers. Consider the following instance of the PCP Alphabet = {0, 1, 2} List L = (0, 1, 2) List M = (00, 11, 22) Does PCP have a solution ? 2 4 4 4 4 4 4 3. 6 6 Write Kruskal's algorithm also evaluate its time Complexity. (a) (i) Find the topological ordering of given graph : Apply DFS algorithm on the above graph. 2. 8 (a) What are regular expressions ? Write a regular expression over I= (a, b} to generate all string that end with three a's. 7 Represent the following graph using (i) arrays (ii) Adjacency list. Prove that the Halting problem is undecidable. MCS-031 6 7 3 P.T.O. 4. (a) "Merge Sort is considered to be best if space complexity is not a constraint". Explain the statement by some mathematical proof. 6 Write the algorithm for Best First Search. 4+4 What is minimax principal. Discuss the relationship between class P, NP, NP complete and NP Hard problems with suitable example of each class. (a) To sort the list 15, 10, 13, 9, 12, 17 stored in A [1..6] using heap sort first build a heap for the list and then recursively delete the root and restore the heap. 6 Write the algorithm for binary search also evaluate its time complexity. 8 Sort the given list using merge sort : 5. 6 6 25, 12, 15, 11, 17, 8 also find the number of comparisons and assignment operations required. MCS-031 4

Formatting page ...

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