Nalanda Open University 2010 M.C.A Computer Aplications Master of Computer Application Part–I, –VII (Design and Analysis of Algorithm) Annual , - Question Paper

Master of Computer Application Part–I, Paper–VII (Design and Analysis of Algorithm) Annual Examination, 2010

IN ALAIN DA OPEN UNIVERSITY Master of Computer Application Part-1, Paper-VII (IX'sign and Analysis of Algorithm)

Annual Examination, 2010 Full Marks : 80    Time : 3 Hours.

Answer any Five Questions. AU questions carry equal marks.

1.    (a) Define an Algorithm. Write building block of algorithms.

(b) Explain how the algorithm sum .N.3 find the sum of first 3 natural numbers.

2.    (a) Differentiate important concepts of procedures and recursion.

(b) Discuss about the Control Structure i.e. sequencing, selection and repetition.

3.    (a) Write the principle of Mathematical Induction.

(b) Write an algorithm for a recursive function that outputs the maximum value in a list of size n.

4.    (a) Write an algorithm for Insertion sort for any given list. Also find the number of

comparisons and assignments required by the algorithm in sorting the list.

(b) Sort the following sequence of number using bubble sort OR Insertion sort 80 32 31 110 50 40.

5.    Trace the action of Binary search include the value of Low. High and middle after each. Iteration for the list {2. 3. 5. 7. 11. 13. 17. 19} for search element x=7.

6.    Write an algorithm for sequential search OR Binary search for any given list.

7.    (a) Write short notes on any Three of the following: -

(i) Context free grammar (ii) Regular grammar (iii) DFA

(iv) NFA    (v) PDA    (vi) Moore Machine.

(b) Construct a grammar for a the language L= {aⁿⁱCbⁿm>n}.

8.    (a) Explain the following notation for the growth rate of function:-

(i) O (big oh)    (ii) 1 (big Omega)

(b) Prove that for the following hold for the function /(*)-2x* + 3jt +1 (i) f(x) = (>(x⁴)    (ii) a- =o{f(x))    (iii) f(x)=a(x>).

9.    Write a Kmskal's algorithm and find a minimal spanning tree for the following graph:-

Attachment: nalanda-open-university-2010-m-c-a-computer-aplications-40883-1.gif

Earning:   Approval pending.