JNTU Kakinada B-Tech 2-1 R1621052 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE R16 May 2018 Question Paper

Code No: R1621052
II B. Tech I Semester Supplementary Examinations, May – 2018
MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE (Com to CSE & IT)Time: 3 hours Max. Marks: 70
Note: 1. Question Paper consists of two parts (Part-A and Part-B) 2. Answer ALL the question in Part-A
3. Answer any FOUR Questions from Part-B
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
PART ?A
1. a)Construct truth table for the compound predicate: p?(?q ? r) (2M)
b)Draw the Hasse diagram for the power set (P(S), =), where S={1,2,3}. (3M)
c)Write a note on = operator in modular arithmetic. (2M)
d)How many ways are there to arrange the letters of the word ENGINNERING? (2M)
e) Solve the following recurrence relation using generating functions: a
n
-6a
n-1
=0
for n=1 and a
0
=1. (3M)
f)A complete binary tree has 125 edges. How many vertices does it have? (2M)
PART -B
2. a) Show that the following statement is a tautology: (~P^(P?Q))?(~Q) (7M)
b) Using automatic theorem proving, show that: (P V Q) ?(Q?R) ?(P?M) = (RVM) (7M)
3. a) Verify the following relation R on X = {1, 2, 3, 4} is an equivalence relation or
not? Given R = {(1, 1), (1, 4), (4, 1), (2, 2), (2, 3), (3, 4), (3, 3), (3, 2), (4, 3), (4, 4)}. (7M)
b) Given below the relation matrix, M
R
of a relation R on the set {a,b,c} , find the
relation matrices of R
2
= R?R, R
3
=R?R?R.
M
R =

1 0 1
1 1 0
1 1 1

(7M)
4. a)Explain different tests for primality. (7M)
b) Prove that G={-1,1,i,-i} is an Abelian group under multiplication. (7M)
5. a)What are the applications of Binomial and Multinomial coefficients? (7M)
b) In how many ways can you select at least one king, if you choose five cards
from a Deck of 52 cards? (7M)
6. a) Verify by mathematical induction that a
n
=A
1
n+A
2
is a solution to a
n
=d a
n/d
+ e
where n=d
k
. (7M)
b) Write about partial fraction decomposition. (7M)
7. a)What is a cut vertex, cut set and bridge? Explain with suitable examples. (7M)
b) Show that the maximum number of edges in a complete bipartiate graphs with
n vertices is n
2
/4. (7M)
1 of 1
SET – 1
R16