MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE JNTU previous year question paper for CSE,IT,CSSE department students

MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE JNTU previous year question paper for CSE,IT,CSSE department students

MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE JNTU previous year question paper for CSE,IT,CSSE department students

II B.Tech I Semester Regular Examinations, November 2007

MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

( Common to Computer Science & Engineering, Information Technology

and Computer Science & Systems Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

⋆ ⋆ ⋆ ⋆ ⋆
1. (a) Construed a truth table for each of there (easy) compound statements
i. (p ! q) (7p ! q)
ii. p ! (7qV r)
(b) Write the negation of the following 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 required 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 some 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) Consider f; Z+ ! Z+ define by f (a) . a2. Check if f is one-to-one and / or
into using suitable explanation.
(b) What is a partial order relation? Let S = { x,y,z} and consider the power set
P(S) with relation R given by set inclusion. ISR a partial order.
(c) Define a lattice. Explain its properties. [4+8+4]
4. (a) If G is a group such that (ab)m = am bm for three consecutive integers m for
all a, b 2 G, show that G is abelian.
(b) Let G be a group and H a subgroup of G. Let f be an automorphism of G and
f(H) = {f(h)/h 2 H}
Prove that f(H) is a subgroup of G. [10+6]
5. (a) Howmany ways are there to seat 10 boys and 10 girls around a circular table,
if boys and girls seat alternatively
(b) In howmany ways can the digits 0,1,2,3,4,5,6,7,8 and 9 be arranged so that 0
and 1 are adyacent and in the order of 01. [16]
6. (a) Solve an = an - 1 + an - 2, n 2, given a0 = 1, a1 = 1 using generating func-
tions
(b) Solve an = 3an−1, n 1, using generating functions. [8+8]
7. (a) Derive the directed spanning tree from the graph shown Figure 7a
Figure 7a
(b) Explain the steps involved in deriving a spanning tree from the given undi-
rected graph using breadth first search algorithm. [8+8]
8. (a) Find the chromatic numbers of
i. a bipartite graph K3,3
ii. a complete graph Kn and
iii. a wheel graph W1,n.
(b) Find the chromatic number of the following graph. Figure 8b [16]

II B.Tech I Semester Regular Examinations, November 2007

MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

( Common to Computer Science & Engineering, Information Technology

and Computer Science & Systems Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

⋆ ⋆ ⋆ ⋆ ⋆

1. (a) Construed a truth table for each of there (easy) compound statements
i. (p ! q) (7p ! q)
ii. p ! (7qV r)
(b) Write the negation of the following 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 required 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 some 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 explain the properties of the pigeon hole principle.
(b) Apply is pigeon hole principle show that of any 14 integere are selected from
the set S={1, 2, 3...........25} there are at least two where sum is 26. Also write
a statement that generalizes this result.
(c) Show that if eight people are in a room, at least two of them have birthdays
that occur on the same day of the week. [4+8+4]
4. (a) Let G be a group. Then prove that Z(G) = { x 2 G/ xg = gx for all g 2 G}
is a subgroup of G.
(b) Let P(S) be the power set of a non -empty set S. Let ‘\′ be an operation in
P(S). Prove that associate law and commutative law are true for the operation
′\′ in P(S). [10+6]
5. (a) A chain letter is sent to 10 people in the first week of the year. The next weak
each 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 between 105 and 106 have no digits other than 2, 5 or 8?
[16]
6. (a) Solve an - 3an - 1 - 4an - 2 = 3n given a0 = 1, a1 = 2.
(b) Solve an - 7an - 1 + 10an - 2 = 0, n 2, given 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) Explain the steps involved in deriving a spanning tree from the given undi-
rected graph using breadth first search algorithm. [8+8]
8. (a) Write a brief note about the basic rules for constructing Hamiltonian cycles.
(b) Using Grinberg theorem find the Hamiltonian cycle in the following graph.
Figure 8b [16]
Figure 8b
⋆ ⋆ ⋆ ⋆ ⋆

II B.Tech I Semester Regular Examinations, November 2007

MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

( Common to Computer Science & Engineering, Information Technology

and Computer Science & Systems Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

⋆ ⋆ ⋆ ⋆ ⋆

1. (a) Let p,q and r be the propositions.
P: you have the flee
q: you miss the final examination.
r: you pass the course.
Write the following 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) Define 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 some 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 each of the following:
i. A \ B
ii. B \ C
iii. ¯ A [ ¯ C
iv. ¯B [ ¯ C
1 of 3
Code No: R059210502 Set No. 3
(b) State and explain 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 2 H ) ab 2 H;
ii. a 2 H ) a - 1 2 H.
(b) The set of integers Z, is an abelian group under the composition defined by
such that a b = a + b+ 1 for a, b 2 Z. Find
i. the identity of (Z, ) and
ii. inverse of each element of Z. [10+6]
5. (a) How many different orders can 3 men and 3 women be seated in a row of 6
seats if all members of same sex are seated in adjacent seats
(b) A new state flag is to be designed with 6 vertical stripes in yellow, white, blue
and red. In how many ways can this be done so that no two adjacent stripes
have the same color? [16]
6. (a) A bank pays 8 percent each year on money in saving accounts. Find 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 each year.
(b) Solve an - 2an - 1 - 3an - 2 = 5n, n 2, given a0 = - 2, a1 = 1. [8+8]
7. (a) Explain about the adjacency matrix representation of graphs. Illustrate with
an example.
(b) What are the advantages of adjacency matrix representation.
(c) Explain the algorithm for breadth first search traversal of a graph. [5+3+8]
8. (a) Prove or disprove that the following two graphs are isomorphic. Figures 8a,
8a.
Figure 8a
2 of 3
Code No: R059210502 Set No. 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.

II B.Tech I Semester Regular Examinations, November 2007

MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

( Common to Computer Science & Engineering, Information Technology

and Computer Science & Systems Engineering)

Time: 3 hours Max Marks: 80

Answer any FIVE Questions

All Questions carry equal marks

⋆ ⋆ ⋆ ⋆ ⋆

1. (a) Let p,q and r be the propositions.
P: you have the flee
q: you miss the final examination.
r: you pass the course.
Write the following 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) Define 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 some 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 explain the properties of the pigeon hole principle.
(b) Apply is pigeon hole principle show that of any 14 integere are selected from
the set S={1, 2, 3...........25} there are at least two where sum is 26. Also write
a statement that generalizes this result.
(c) Show that if eight people are in a room, at least two of them have birthdays
that occur on the same day of the week. [4+8+4]
1 of 3
Code No: R059210502 Set No. 4
4. (a) Define Semi group. Verify which of the following 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 2 G, then O(a)= O (a−1). [8+8]
5. (a) In howmany ways can a committee of 5 ladies and 4 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 2 clubs and 3 hearts.
(c) Howmany 5-card hands consist only of hearts. [16]
6. (a) Solve an = an - 1 + an - 2, n 2, given a0 = 1, a1 = 1 using generating func-
tions
(b) Solve an = 3an−1, n 1, using generating functions. [8+8]
7. Derive the
(a) breadth first tree and
(b) depth first search spanning trees for the following 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 following graph.