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

? ? ? ? ?







2 of 2Code No: 07A3BS04 Set No. 3

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) Show the implication: (P ? Q) ? Q ? P ? Q
(b) Show that the proposition: (P? ~ Q) ? ( ~ P? ~ Q) ?Q is a tautology.[8+8]
2. (a) How does an indirect proof technique di?er from a direct proof?
(b) Using predicate logic, prove the validity of the subsequent argument:
“Every husband argues with his spouse. ‘X’ is a husband. Therefore, ‘X’
argues with his wife”. [6+10]
3. (a) obtain the inverse of the subsequent functions:
i. f(x) = 10
5 v7-3x
ii. f(x) = 4e(6x+2)
.
(b) Draw the Hasse diagram for the relation R on A = {1, 2, 3, 4, 5}, whose
relation matrix is provided below: [8+8]
MR =
?
? ? ? ? ?
? ? ? ? ?
1 0 one 1 1
0 one 1 one 1
0 0 one 1 1
0 0 0 one 0
0 0 0 0 1
?
? ? ? ? ?
? ? ? ? ?
4. Consider the group, G = {1, 2, 4, 7, 8, 11, 13, 14} under multiplication modulo 15:
(a) Construct the multiplication table of G.
(b) obtain the values of: 2-1
, 7-1
and 11-1.
(c) obtain the orders and subgroups generated by 2, 7, and 11.
(d) Is G cyclic [16]
5. (a) In how many ways can we draw a heart or spade from ordinary deck of playing
cards? a heart or an ace? an ace or a king? A card numbered two through 10?
(b) How many ways are there to roll 2 distinguishable dice to yield a sum that
is divisible by 3? [8+8]
6. (a) obtain a recurrence relation for number of ways to climb n stairs if the person
climbing the stairs can take one,two,or 3 stairs at a time.
(b) elaborate the initial conditions? How many ways can this person climb a ?ight
of 8 stairs? [8+8]
1 of 2Code No: 07A3BS04 Set No. 3
7. (a) Write the algorithm for breadth ?rst search spanning tree.
(b) Apply breadth ?rst search on the subsequent ?gure 7b. [6+10]
Figure 7b
8. (a) Let G = (V,E) be an undirected graph, with G1 = (V1,E1) a subgraph of G.
Under what condition(s) is G1 not an induced subgraph of G?
(b) For the graph shown in ?gure8b, ?nd a subgraph that is not an induced graph.
[8+8]
Figure 8b
? ? ? ? ?








2 of 2Code No: 07A3BS04 Set No. 4
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) obtain the truth table for the propositional formula: (P ?~ Q) ? (Q ? P).
(b) What is the compound statement that is actual when exactly 2 of the three
statements P, Q and R are true?
(c) What is the negation of the statement: “2 is even and -3 is negative?” [6+5+5]
2. (a) Prove or disprove the conclusion provided beneath from the subsequent axioms:
“All men are morta. Mahatma Gandhi is a man. Every mortal lives less
than 100 years. Mahatma Gandhi was born in 1869. Now, it is 2008.
Therefore, Is Mahatma Gandhi alive now?”
(b) Using proof by contradiction, show that
v2 is not a rational number. [8+8]
3. (a) Consider the subsequent recursive function de?nition:
If x < y, then f(x, y) = 0; If y = x, then f(x, y) = f(x-y, y) + 1. obtain the
value of f(5861, 7).
(b) Let the relation R = {(1, 2), (2, 3), (3, 3)} on the set {1, 2, 3}. What is the
transitive closure of R? [8+8]
4. (a) Let (S1, *1), (S2, *2) and (S3, *3) be semi groups and f: S1 ? S2 and g:
S2 ? S3 be homomorphisms. Prove that the mapping of g o f: S1 ? S3
homomorphism.
(b) Prove that H = {0, 2, 4} forms a subgroup of (Z6, +). [8+8]
5. A group of eight scientists is composed of five psychologists and sociologists:
(a) In how many ways can a committee of five be formed?
(b) In how many ways can a committee of five be formed that has three psychologists
and two sociologists? [8+8]
6. (a) In how many ways can Traci choose n marbles from a large supply of blue, red
and yellow marbles( all of the identical size) if the selection must include an even
number of blue ones.
(b) Determine the sequence generated by f(x) =1/(1-x) + 3x7
-11. [8+8]
7. (a) Prove that a tree with n vertices has exactly n-1 edges.
(b) Show that graph G is a tree i? G is connected and contains no circuits.
1 of 2Code No: 07A3BS04 Set No. 4
(c) How many vertices will the subsequent graph contain 16 edges and all vertices
of degree 2. [6+6+4]
8. (a) provide an example of a connected graph G where removing any edge of G outcomes
in a disconnected graph.
(b) provide an example for a bipartite graph with examples.
(c) explain graph coloring issue with needed examples. [4+6+6]
? ? ? ? ?
2 of 2

Earning:   Approval pending.