Indira Gandhi Institute of Development Research 2011 Indira Gandhi National Open University (IGNOU) Post Graduate Diploma Computer Application MCS-031: Design and Analysis of Algorithms , e’ - Que

No. of Printed Pages : 4

MCA (Revised) Term-End Examination June, 2011 MCS-031 : DESIGN AND ANALYSIS OF '    ALGORITHM

Time : 3 hours    Maximum Marks : 100

Note : Question No. 1 is compulsory. Attempt any three from the rest of the questions.

(g)    Define Knapsack Problem and cite one instance of the problem.

(h)    Consider a (hypothetical) country in which only notes available are of denominations 10,40 and 60. Using Greedy algorithm, how do we collect an amount of 80.

(i)    Briefly explain Kruskal's OR Prim's algorithm for finding minimal spanning tree of a graph.

(j) Name four undecidable problems, each with brief description.

Using Dijkstra's algorithm, find the minimum distances of all the nodes from node 'b' which is taken as the source node, for the following graph.

(b)    Find a regular expression for the language {a, a, a b b, a b b b, a b b b b b b,....}

(c)    Briefly discuss Chomsky classification for Grammars.

3. (a) Trace how BFS (Breadth - First Search) 8 traverses, i.e, discovers and visits the graph given below when starting at node A.

(b)    Write pseudo-code for Depth-First search. 5

(c)    Find the value of (12)³¹ using not more than 7 SIX multiplications and/or divisions.

4. (a) Write a program that computes the length 6 of the diagonal of a right - angled triangle, the length of the two sides of which are given.

(b)    For the function / (x) = 4x³ + 6x +1 show 6 that (i) f(x) = O (x⁴) but (ii) x⁴# O (J (x))

(c)    Sort the following sequence of numbers 8 using Quick Sort: 8, 6, 4,12,11, 5, 7 and 9.

5. (a) Design a Turing Machine that recognises the 10 languages of all strings of even lengths over the alphabet {c, d}.

(b) For each of the following pairs of lists, 10 discuss whether PCP (Post Correspondence Problem) has a solution :

(i)    List A = (b, b a b b b, b a) and List B = (b b b, b a, a)

(ii)    List C = ( a b, b, b) and

D = (a b b, b a, b b)

MCS-031    4

Attachment: indira-gandhi-institute-of-development-research-2011--2685-1.pdf

Earning:   Approval pending.