Jawaharlal Nehru Technological University Kakinada 2007 B.Tech Computer Science and Engineering MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE (3) - Question Paper

Code No: R059210502 Set No. 1
II B.Tech I Semester Regular Examinations, November 2007
MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE
( Common to Computer Science & Engineering, info Technology
and Computer Science & Systems Engineering)
Time: three hours Max Marks: 80
ans any 5 ques.
All ques. carry equal marks
? ? ? ? ?
1. (a) Construed a truth table for every of there (easy) compound statements
i. (p ! q)_(7p ! q)
ii. p ! (7qV r)
(b) Write the negation of the subsequent statements.
i. Jan will take a job in industry or go to graduate school.
ii. James will bicycle or run tomorrow.
iii. If the processor is fast then the printer is slow.
(c) What is the minimal set of connectives needed for a well formed formula.
[8+6+2]
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+ describe 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) describe a lattice. discuss its properties. [4+8+4]
4. (a) If G is a group such that (ab)m = am bm for 3 consecutive integers m for
all a, b two G, show that G is abelian.
1 of 3
(b) Let G be a group and H a subgroup of G. Let f be an automorphism of G and
f(H) = {f(h)/h two H}
Prove that f(H) is a subgroup of G. [10+6]
5. (a) Howmany ways are there to seat 10 boys and 10 girls around a circular table,
if boys and girls seat alternatively
(b) In howmany ways can the digits 0,1,2,3,4,5,6,7,8 and nine be organizes so that 0
and one are adyacent and in the order of 01. [16]
6. (a) Solve an = an - one + an - 2, n _ 2, provided a0 = 1, a1 = one using generating func-
tions
(b) Solve an = 3an-1, n _ 1, using generating functions. [8+8]
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 undi-
rected graph using breadth 1st search algorithm. [8+8]
8. (a) obtain the chromatic numbers of
i. a bipartite graph K3,3
ii. a complete graph Kn and
iii. a wheel graph W1,n.
(b) obtain the chromatic number of the subsequent graph. Figure 8b [16]
2 of 3
Figure 8b
? ? ? ? ?

Earning:   Approval pending.