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

Code No: X0522/R07 Set No. 4

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) describe converse, contrapositive and inverse of an implication. [Marks 12+4]
2. (a) Let P(x) denote the statement. "x is a professional athlete" and let Q(x)denote
the statement" "x plays soccer". The domain is the let of all people. Write
every of the subsequent proposition in English.
i. ?x (P (x) ? Q(x))
ii. ?x (P (x)?Q(x))
iii. ?x (P (x) V Q(x))

(b) Write the negation of every of the above propositions, both in symbols and in
words. [Marks 6+10]

3. (a) Determine whether the subsequent relations are injective and/or subjective function. obtain universe of the functions if they exist.
i. A = {v,w, x, y, z}
B = {1, 2, 3, 4, 5}
R = {(v,z),(w,1),(x,3),(y,5)}
ii. A = {1, 2, 3, 4, 5}
B = {1, 2, 3, 4, 5}
R = {(1,2),(2,3),(3,4),(4,5),(5,1)}

(b) If a function is de?ned as f(x,n) mod n. Determine the
i. Domain of f
ii. Range of f
iii. g(g(g(g(7)))) if g (n) = f(209, n). [Marks 8+8]

4. (a) Prove that a non empty subset H of a group G is a subgroup of G i?
i. a, b ? H ? ab ? H
ii. a ? H ? a - 1
? H.

(b) The set of integers Z, is an abelian group under the composition de?ned by ?
such that a? b = a + b+ one for a, b ? Z. obtain
i. the identity of (Z, ? ) and
ii. inverse of every element of Z. [Marks 10+6]

5. (a) A chain letter is sent to 10 people in the ?rst week of the year. The next weak
every person who received a letter sends letters to 10 new people and so on.
How many people have received the letters at the end of the year?

(b) How many integers ranging from 105
and 106 have no digits other than 2, five or 8? [Marks 16]

6. (a) Solve an = an - one + an - 2, n = 2, provided a0 = 1, a1 = one using generating functions

(b) Solve an = 3an-1, n = 1, using generating functions. [Marks 8+8]

7. (a) De?ne spanning tree. elaborate its characteristics.

(b) Derive all possible spanning trees for the graph shown in Figure 7. [Marks 6+10]
Figure 7

8. (a) How to determine whether a graph contains Hamiltonian cycle or not using
Grin berg theorem.

(b) Prove or disprove that there is an Hamiltonian cycle in the subsequent graph.
Figure 8b [Marks 16]

Earning:   Approval pending.