Download JNTUH MCA 1st Sem R15 2018 January 821AA Mathematical Foundations Of Computer Science Question Paper

Download JNTUH (Jawaharlal nehru technological university) MCA (Master of Computer Applications) 1st Sem (First Semester) Regulation-R15 2018 January 821AA Mathematical Foundations Of Computer Science Previous Question Paper

R15

Code No: 821AA















JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

MCA I Semester Examinations, January ? 2018

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE

Time: 3hrs













Max.Marks:75


Note: This question paper contains two parts A and B.

Part A is compulsory which carries 25 marks. Answer all questions in Part A. Part B
consists of 5 Units. Answer any one full question from each unit. Each question carries 10
marks and may have a, b, c as sub questions.





PART - A



















5 ? 5 Marks = 25

1.a)

What are rules of the Well Formed Formulas?









[5]

b) Explain Abelian group with example.











[5]

c) State and prove binomial theorem.











[5]

d) Explain generating function.













[5]

e) When two graphs are said to be isomorphic? Explain with an example.



[5]



PART - B

















5 ? 10 Marks = 50

2.

Derive the following using CP rule if necessary

P (QR), Q (RS) P (Q S)









[10]

OR

3.

Explain in detail about the Logical Connectives with Examples.





[10]



4.

Draw the Hasse diagram of (p(S), ), Where p(S) is power set of the set S= {a,b,c}.[10]







OR

5.

Define a semi group and Monoid. Give an example of a Monoid which is not a group.
Justify your answer.















[10]


6.

State and prove principle of inclusion and exclusion of three variables.



[10]

OR

7.

Answer the following:
a) In how many ways can six men and four women sit in a row?

b) In how many ways can they sit in a row if all the men sit together?

c) In how many ways can they sit in a row if just the women sit together?

d) In how many ways can they sit in a row if men sit together?





[10]


8.

Find the particular solution of the recurrence relation an+2 ? 4 an+1 + 4 an = 2n?

[10]

OR

9.

Solve the recurrence relation a 5a

3, r 1

r

r 1

with the boundary conditions a0=1 using

generating functions.















[10]














10.

Write the Kruskal's algorithm and find minimal spanning tree of the weighted graph
shown below.

















[10]



OR

11.a) A complete binary tree has 25 leaves. How many vertices does it have?
b) Explain about the following
i) Eulerian Graph
ii) Chromatic number.















[10]



---oo0oo---