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

FirstRanker.com

Code No: 821AA R15

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

--- Content provided by⁠ FirstRanker.com ---

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.

--- Content provided by​ FirstRanker.com ---

PART - A 5 x 5 Marks =25

1. What are rules of the Well Formed Formulas? [5]
2. Explain Abelian group with example. [5]
3. State and prove binomial theorem. [5]
4. Explain generating function. [5]

--- Content provided by FirstRanker.com ---

5. When two graphs are said to be isomorphic? Explain with an example. [5]

PART -B 5 x 10 Marks = 50

1. Derive the following using CP rule if necessary P—(Q—R),Q = (R—S)=P—(Q—S) [10]
   OR
   Explain in detail about the Logical Connectives with Examples. [10]

--- Content provided by⁠ FirstRanker.com ---

2. Draw the Hasse diagram of (p(S), <), Where p(S) is power set of the set S= {a,b,c}.[10]
   OR
   Define a semi group and Monoid. Give an example of a Monoid which is not a group. Justify your answer. [10]
3. State and prove principle of inclusion and exclusion of three variables. [10]
   OR
   

   --- Content provided by​ FirstRanker.com ---

   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]

--- Content provided by⁠ FirstRanker.com ---

4. Find the particular solution of the recurrence relation a_n+2 — 4 a_n+1 + 4 a_n = 2ⁿ [10]
   OR
   Solve the recurrence relation a_r —5a_r-1 =3, r = 1 with the boundary conditions a₁=1 using generating functions. [10]
5. Write the Kruskal’s algorithm and find minimal spanning tree of the weighted graph shown below. [10]
6. a) A complete binary tree has 25 leaves. How many vertices does it have?
   

   --- Content provided by‍ FirstRanker.com ---

   b) Explain about the following
   i) Eulerian Graph
   ii) Chromatic number. [10]

---00000---

--- Content provided by⁠ FirstRanker.com ---