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

Code No: R059210502 Set No. 4

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) Let p,q and r be the propositions.
P: you have the flee
q: you miss the final 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. [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) State and discuss the properties of the pigeon hole principle.
(b) Apply is pigeon hole principle show that of any 14 integere are opted from
the set S={1, 2, 3...........25} there are at lowest 2 where sum is 26. Also write
a statement that generalizes this outcome.
(c) Show that if 8 people are in a room, at lowest 2 of them have birthdays
that occur on the identical day of the week. [4+8+4]
1 of 3
4. (a) describe Semi group. Verify which of the subsequent are semi groups.
i. (N, +),
ii. (Q, -),
iii. (R, +)
iv. (Q, o), aob = a - b +ab.
(b) Prove that in a group G, if a two G, then O(a)= O (a-1). [8+8]
5. (a) In howmany ways can a committee of five ladies and four gents be chosen from
9 ladies and 15 gents, if gent, A refuses to take part if lady, B is on the
committee.
(b) Howmany 5-card hands have two clubs and three hearts.
(c) Howmany 5-card hands consist only of hearts. [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. Derive the
(a) breadth 1st tree and
(b) depth 1st search spanning trees for the subsequent graph. Figure 7b [8+8]
Figure 7b
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 [16]
2 of 3
Figure 8b
? ? ? ? ?

Earning:   Approval pending.