Jawaharlal Nehru Technological University Kakinada 2010 B.Tech Information Technology 2-1 ENGG.R07 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE SUPPLY SET-1 - Question Paper

4 Code No: X0522/R07 Set No. 1

II B.Tech I Semester Supplementary Examinations, May 2010

MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

( Common to Computer Science & Engineering and info
Technology)

Time: three hours Max Marks: 80

ans any 5 ques.

All ques. carry equal marks


1. (a) Let p,q and r be the propositions.
P: you have the ?ee
q: you miss the ?nal exam.
r: you pass the course.
Write the subsequent proposition into statement form.
i. P ? q
ii. 7p ? r
iii. q ? 7r
iv. pVqVr
v. (p ? 7r) V (q ?~ r)
vi. (p?q) V (7q?r)

(b) De?ne converse, contrapositive and inverse of an implication. [12+4]

2. Prove using rules of inference or disprove.
(a) Duke is a Labrador retriever
All Labrador retriever like to swin
Therefore Duke likes to swin.

(b) All ever numbers that are also greater than
2 are not prime
2 is an even number
2 is prime
Therefore a few even numbers are prime.
UNIVERSE = numbers.

(c) If it is hot today or raining today then it is no fun to snow ski today
It is no fun to snow ski today
Therefore it is hot today
UNIVERSE = DAYS. [5+6+5]

3. (a) Consider f; Z+ ? Z+ de?ne by f (a)= a2
. Check if f is one-to-one and / or
into using suitable explanation.

(b) What is a partial order relation? Let S = { x,y,z} and consider the power set
P(S) with relation R provided by set inclusion. ISR a partial order.

(c) De?ne a lattice. discuss its properties. [4+8+4]

4. A is any non-empty set S is the set of all bijections (one-one and onto mappings)
from A to A. then show that S is a group w.r.t. composition of mappings as binary
operation. [16]

5. A mother distributes five di?erent apples among eight children.
(a) How many ways can this be done if every child receives at most 1 apple
(b) How many ways can this be done if there is no restriction on the number of
apples a child can receive. [16]

6. (a) obtain recurrence relation for number of subsets of an n- element set.
(b) Solve an - 5an - one + 6an - two = 2n + n, n = 2, provided a0 = 1, a1 = one using generating functions. [4+12]

7. (a) Derive the directed spanning tree from the graph shown Figure 7a
Figure 7a

(b) discuss the steps involved in deriving a spanning tree from the provided undirected graph using breadth ?rst search algorithm. [8+8]

8. (a) Write a brief note about the basic rules for constructing Hamiltonian cycles.
(b) Using Grinberg theorem ?nd the Hamiltonian cycle in the subsequent graph.
Figure 8b [16]
Figure 8b

Earning:   Approval pending.