Fundamental of Data Structure Numerical and Computational Theory 2019 MCA 4th Sem AKTU

Printed Pages: 02 Sub Code: RCAA02

Paper Id: 214246 Roll No. _____________________

MCA

(SEM IV) THEORY EXAMINATION 2018-19

Fundamental of Data Structure Numerical and Computational Theory

Time: 3 Hours Total Marks: 70

Note: 1. Attempt all Sections. If require any missing data; then choose suitably.

SECTION A

1. Attempt all questions in brief. 2 x 7 = 14

    a. What is regular expression?

b. What is difference between Arrays and queue?

c. Which sorting method is slowest? Why?

d. What is the difference between curve fitting and interpolation?

e. What is regression?

f. Which language is accepted bu finite automata?

SECTION B

2. Attempt any three of the following: 7 x 3 = 21

    a. What is a linked list in data structures? How is linked list implemented?

b. Which of the sorting algorithms can e used to sort a random linked list with minimum time complexity? Discuss it with an example.

c. What is the difference between linear regression and multiple regression?

d. Design a NFA for the regular expression (a+b)*ab

e. Discuss the closure properties of context free languages.

SECTION C

3. Attempt any one part of the following: 7 x 1 = 7

    (a) What is a data structure? What are linear and nonlinear data structures?

(b) Define insertion sort. Sort the sequence 8, 1, 4, 1, 5, 9, 2, 6, 5 by using insertion sort.

4. Attempt any one part of the following: 7 x 1 = 7

(a) How are linked lists better than arrays? What are the advantage of linked list over array?

(b) If the regression coefficients are 0.12 and 0.3, What would be the value of coefficients of correlation?

5. Attempt any one part of the following: 7 x 1 = 7

    (a) Find the straight line that best fits the following data using least squares method:

x:	1	2	3	4	5
y:	2	5	3	8	7

(b) Write short notes on:

(i) T – test

(ii) F – test

6. Attempt any one part of the following: 7 x 1 = 7

(a) Show that L = {a^p/p is prime number}

(b) Define a Turing machine. Describe it using ID with an example.

7. Attempt any one part of the following: 7 x 1 = 7

    (a) Define Push down automata (PDA) using diagram? Construct a PDA for the language L = {aⁿ/b²ⁿ/n>=1}.

(b) Write short notes on:

(i) Ambiguous grammar

(ii) Normal forms of grammar