Mathematical Foundation Of Computer Science Jan2007 R059210502

Set No. 1

Code No: R059210502

II B.Tech I Semester Supplementary Examinations, February 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) Use De morgon’s laws to write the negation of each statement. i. ii. iii. iv.

I want a car and a worth cycle. My cat stays outside or it makes a mess I’ve faller and I can’t get up You study or you don’t get a good grade.

(b) Are (p → q) → r and p → (q → r) logically equivalent? Justify your answer by using the rules of logic to simply both expressions and also by using truth tables. [8+8] 2. (a) Let P(x) denote the statement. “x is a professional athlete” and let Q(x)denote the statement” “x plays soccer”. The domain is the let of all people. Write each of the following proposition in English. i. ∀x (P (x) → Q (x)) ii. ∃x (P (x) ΛQ (x)) iii. ∀x (P (x) V Q (x)) (b) Write the negation of each of the above propositions, both in symbols and in words. [6+10] 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) Define Semi group. Verify which of the following are semi groups. i. (S, o), aob = a ii. (Z, o), aob = a +b ab (b) If H is any subgroup of a group G, then HH = H.

[8+8]

5. (a) Howmany ways are there to place 20 identical balls into 6 different boxes in which exactly 2 boxes are empty.

1 of 2

Set No. 1

Code No: R059210502

(b) In howmany ways canwe partition 12 similar coins into 5 numbered nonempty batches. [16] 6. (a) Solve the difference equation ar + 5ar - 1 + 6ar - 2 = 3r2 - 2r + 1. (b) Solve the difference equation ar - 5 ar - 1 + 6a

r-2

= 1.

[10+6]

7. (a) Define spanning tree. What are its characteristics. (b) Derive all possible spanning trees for the graph shown below. Figure 1 [6+10]

Figure 1: 8. (a) Prove that in any non directed graph there is an even numbers of vertices of add degree. (b) Distinguish between cycle and circuit. Give suitable examples for each. (c) What are the steps followed in discovering the isomorphism? ⋆⋆⋆⋆⋆

2 of 2

[6+4+6]

Set No. 2

Code No: R059210502

II B.Tech I Semester Supplementary Examinations, February 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. ii. iii. iv. v. vi.

P →q 7p → r q → 7r pVqVr (p → 7r) V (q →∼ r) (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. ii. iii. iv.

A∩B B∩C A¯ ∪ C¯ ¯ ∪ C¯ B 1 of 3

Set No. 2

Code No: R059210502

(b) State and explain the applications of the pigon hole principle.

[12+4]

4. (a) If a, b are any two elements of a group (G, .) which commute show that i. a - 1 and b commute, ii. b - 1 and a commute and iii. a - 1 and b - 1 commute. (b) Let S be a non-empty set and o be an operation on S defined by aob=a for a, b ∈ S. Determine whether o is commutative and associative in S. [12+4] 5. (a) Find the arrangements of letters of M I S S I S S I P P I) (b) In howmany ways can 3 boys share 15 different sized apples if each takes 5. [16] 6. (a) Solve an - 7an - 1 + 10an - 2 = 4n . (b) Solve an - 5an - 1 + 6an - 2 = 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) Define the following graphs with one suitable examples for each graphs. i. ii. iii. iv.

Complement graph Sub graph Induced sub graph Spanning sub graph.

(b) Determine whether the following two graph are isomorphic or not. If isomorphic, give the one to one mapping. Figure 1, 2 [8+8]

⋆⋆⋆⋆⋆

2 of 3

Set No. 2

Code No: R059210502

Figure 1:

Figure 2:

3 of 3

Set No. 3

Code No: R059210502

II B.Tech I Semester Supplementary Examinations, February 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. ii. iii. iv. v. vi.

P →q 7p → r q → 7r pVqVr (p → 7r) V (q →∼ r) (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. ii. iii. iv.

A∩B B∩C A¯ ∪ C¯ ¯ ∪ C¯ B 1 of 2

Set No. 3

Code No: R059210502

(b) State and explain the applications of the pigon hole principle.

[12+4]

4. (a) H is a non-empty complex of a group G. Prove that the necessary and sufficient condition for H to be a subgroup of G is a, b ∈ H ⇒ ab - 1 ∈ H, where b - 1 is the inverse of b in G (b) Prove that the mapping f: Z → Z such that f(x) = -x for x ∈ Z where Z is an additive group of integers is an automorphism. [If f: G → G is an isomorphism from a group G to itself then f is called on automorphism of G.] [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 the recurrence relation ar = 3ar - 1 + 2, r ≥ 1, a0 = 1 using generating function. (b) Solve an - 4an - 1 + 4an - 2 = (n + 1)2 given a0 = 0, 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) Define the following terms. Give one suitable example for each. i. ii. iii. iv.

Euler path Euler Circuit Multi graph Hamiltonian graph.

(b) State and prove Grinberg’s theorem to determine whether Hamiltonian cycle exists in a given graph or not. [8+8] ⋆⋆⋆⋆⋆

2 of 2

Set No. 4

Code No: R059210502

II B.Tech I Semester Supplementary Examinations, February 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. (a) Let P(x) denote the statement. “x is a professional athlete” and let Q(x)denote the statement” “x plays soccer”. The domain is the let of all people. Write each of the following proposition in English. i. ∀x (P (x) → Q (x)) ii. ∃x (P (x) ΛQ (x)) iii. ∀x (P (x) V Q (x)) (b) Write the negation of each of the above propositions, both in symbols and in words. [6+10] 3. (a) Define a bijective function. Explain with reasons whether the following functions are bijiective or not. Find also the inverse of each of the functions. i. f(x) = 4x+2, A=set of real numbers ii. f(x) = 3+ 1/x, A=set of non zero real numbers iii. f(x) = (2x+3) mod7, A=N7 . (b) Let f and g be functions from the positive real numbers to positive real numbers defined by f (x) = ⌊2x⌋ g(x) = x2 Calculate f o g and g o f. [10+6] 4. (a) If f is a homomorphism from a group (G,.) into (G’,.) then prove that (f(G),.) is a subgroup of G’. (OR) Prove that the homomorphic image of a group is a group. 1 of 3

Set No. 4

Code No: R059210502

(b) The set, S, of all ordered pairs (a, b) of real numbers for which a 6= 0 w.r.t. the operation × defined by (a, b) × (c, d) = (ac, bc+d) is a group. Find i. the identity of (G, o) and ii. inverse of each element of G.

[10+6]

5. (a) Find total number of positive integers that can be formed from the digits 1, 2, 3, 4 and 5, if no digit is repeated in any integer. (b) A chain letter is sent to 10 people in the first week of the year. The next week who receives a letter sends letters to 10 new people, and so on. How many people have received letters after 10 weeks? [16] 6. (a) Solve the recurrence relation ar = 3ar - 1 + 2, r ≥ 1, a0 = 1 using generating function. (b) Solve an - 4an - 1 + 4an - 2 = (n + 1)2 given a0 = 0, a1 = 1 .

[8+8]

7. (a) Derive the directed spanning tree from the graph shown Figure 1

Figure 1: (b) Explain the steps involved in deriving a spanning tree from the given undirected graph using breadth first search algorithm. [8+8] 8. (a) Prove or disprove that the following two graphs are isomorphic. Figures 2, 3. (b) Determine the number of edges in i. ii. iii. iv.

Complete graph Kn , Complete bipartite graph Km,n Cycle graph Cn and Path graph Pn . ⋆⋆⋆⋆⋆

2 of 3

[8+8]

Set No. 4

Code No: R059210502

Figure 2:

Figure 3:

3 of 3