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

Code No: R059210502 Set No. 2
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) 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]
4. (a) Let G be a group. Then prove that Z(G) = { x two G/ xg = gx for all g two G}
is a subgroup of G.
1 of 2
(b) Let P(S) be the power set of a non -empty set S. Let ‘\' be an operation in
P(S). Prove that associate legal regulations and commutative legal regulations are actual for the operation
'\' in P(S). [10+6]
5. (a) A chain letter is sent to 10 people in the 1st week of the year. The next weak
every person who received a letter sends letters to 10 new people and so on.
How many people have received the letters at the end of the year?
(b) How many integers ranging from 105 and 106 have no digits other than 2, five or 8?
[16]
6. (a) Solve an - 3an - one - 4an - two = 3n provided a0 = 1, a1 = 2.
(b) Solve an - 7an - one + 10an - two = 0, n _ 2, provided a0 = 10, a1 = 41 using generat-
ing 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) Write a brief note about the basic rules for constructing Hamiltonian cycles.
(b) Using Grinberg theorem obtain the Hamiltonian cycle in the subsequent graph.
Figure 8b [16]
Figure 8b
? ? ? ? ?

Earning:   Approval pending.