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

Code No: R059210502 Set No. 3
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) Let A,B,C _ R2 where A = { (x,y) / y = 2x + 1} , B = { (x,y) / y = 3x} and
C = { (x,y) / x - y = 7} . Determine every of the following:
i. A \ B
ii. B \ C
iii. A¯ [ C¯
iv. ¯B [ ¯ C
1 of 3
(b) State and discuss the applications of the pigon hole principle. [12+4]
4. (a) Prove that a non empty subset H of a group G is a subgroup of G iff
i. a, b two H ) ab two H;
ii. a two H ) a - one two H.
(b) The set of integers Z, is an abelian group under the composition described by _
such that a_ b = a + b+ one for a, b two Z. obtain
i. the identity of (Z, _ ) and
ii. inverse of every element of Z. [10+6]
5. (a) How many various orders can three men and three women be seated in a row of 6
seats if all members of identical sex are seated in adjacent seats
(b) A new state flag is to be designed with six vertical stripes in yellow, white, blue
and red. In how many ways can this be done so that no 2 adjacent stripes
have the identical color? [16]
6. (a) A bank pays eight percent every year on money in saving accounts. obtain recurrence
relation for the amount of money in saving account that would have after n
years if it follows the investment strategies of:
i. Investing $1000 and leaving it in the bank for n years.
ii. Investing $100at the end of every year.
(b) Solve an - 2an - one - 3an - two = 5n, n _ 2, provided a0 = - 2, a1 = 1. [8+8]
7. (a) discuss about the adjacency matrix representation of graphs. Illustrate with
an example.
(b) elaborate the advantages of adjacency matrix representation.
(c) discuss the algorithm for breadth 1st search traversal of a graph. [5+3+8]
8. (a) Prove or disprove that the subsequent 2 graphs are isomorphic. Figures 8a,
8a.
Figure 8a
2 of 3
Figure 8a
(b) Determine the number of edges in [8+8]
i. Complete graph Kn,
ii. Complete bipartite graph Km,n
iii. Cycle graph Cn and
iv. Path graph Pn.
? ? ? ? ?
3 of 3

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

Earning:   Approval pending.