11-mca-or-discrete Structures

OR

Code No: OR-11/MCA

MCA-I Semester Supplementary Examinations, July/Aug 2008. DISCRETE STRUCTURES Time: 3hours

Max. Marks: 60 Answer any FIVE questions All questions carry equal marks ---

1.a) b)

Prove that if R is a symmetric relation, then R ∩ R −1 = R . Prove that A ⊂ B ⇒ A ∪ ( B − A) = B

2.a)

Conjecture a general formula for the following: 1 1 1 + + ........ + 1.2 2.3 n(n + 1) b) How many ways are there to roll two distinguishable dice to yield a sum that is divisible by 3 ?

3.a) How many 4-digit telephone numbers have one or more repeated digits? b) Enumerate the number of non negative integer solutions to the inequality x1 + x2 + x3 + x4 + x5 ≤ 19 . 4.a) What is meant by a Recurrence relation? Find a generating function to count the number of integer solutions to e1 + e2 + e3 = 10 if for each

i, 0 ≤ ei . ( x 3 + x 4 + x 5 .....)5 . b) 5.a) b)

Find the co-efficient of X 20 in ( x3 + x 4 + x5 + .....) . 5

Explain the Fibonacci Relation. Discuss the method of undetermined coefficients.

6.a)

What is binary relation? Discuss the special properties of binary relations. b) What is meant by Equivalence relation? How many different equivalence relations are there on a set with n elements for n = 1, 2,3, 4, and 5?

7.a) b)

What is Isomorphism? Discuss how to discover isomorphisms. Write the algorithm of breadth first search for spanning tree.

8.

Write short notes on any three of the following: a) Directed tree b) Binomial coefficients c) Lattices d) Chromatic Numbers ****