Jawaharlal Nehru Technological University Kakinada 2008 B.Tech Computer Science and Engineering mathematical foundations of computer sciences - Question Paper

Code No: 07A3BS04 Set No. 1
II B.Tech I Semester Regular Examinations, November 2008
MATHEMATICAL FOUNDATIONS 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) Prove that the proposition: (P ? Q) ? (P ? Q) is a Contingency.
(b) find the principal disjunctive normal form of the propositional formula:
( ~ P ? R) ? (Q ? P). [8+8]
2. Write the quanti?ers of the subsequent statements, where predicate symbols denotes,
F(x): x is fruit, V(x): x is vegetable and S(x, y): x is sweeter than y.
(a) a few vegetable is sweeter than all fruits
(b) Every fruit is sweeter than all vegetables
(c) Every fruit is sweeter than a few vegetables
(d) Only fruits are sweeter than vegetables. [16]
3. (a) What is a Poset? Draw the Hasse diagrams of all the lattices with five elements.
(b) Let A = {1, 2, 3}, B = {a, b, c} and C = {x, y, z}. The relation R from A to
B is {(1, b), (2, a), (2, c)} and the relation S from B to C is {(a, y), (b, x),
(c, y), (c, z)}. obtain the composition relation, R?S. [8+8]
4. (a) Explain, in detail, the algebraic systems: Endomorphism and Automorphism
with suitable examples.
(b) Prove that the set Z of all integers with the binary operation a * b = a + b
+ 1, ? ? Z is an abelian group. [8+8]
5. (a) How many anagrams (arrangements of letters) are there of
{7.a, 5.c, 1.d, 5.e, 1.g, 1.h, 7.i, 3.m, 9.n, 4.o, 5.t}?
(b) How many arrangements are there of 8.a, 6.b, 7.c in which every ‘a’ is on at
lowest 1 side of a different ‘a’.? [8+8]
6. (a) De?ne recurrence relation? show that the sequence {an} is a solution of re-
currence relation an = -3 an-1 + four an-2 if an = 1.
(b) What is solution of the recurrence relation an = an-1 + two an-2 with a0 = 2
and a1 =7? [8+8]
7. (a) Prove that a non-directed graph G is connected if and only if G contains a
spanning tree.
1 of 2Code No: 07A3BS04 Set No. 1
(b) Determine the spanning tree of the subsequent ?gure7b using DFS. [6+10]
Figure 7b
8. (a) Suppose that we know the degrees of the vertices of a non directed graph G.
Is it possible to determine the order and size of G? discuss.
(b) Suppose that we know the order and size of a non directed graph G. Is it
possible to determine the degrees of the vertices of G? discuss. [8+8]
? ? ? ? ?












2 of 2Code No: 07A3BS04 Set No. 2
II B.Tech I Semester Regular Examinations, November 2008

Earning:   Approval pending.