R6-11-mca-discrete-structures-set1

R6

Code No: R6-11-MCA

M.C.A. I Semester Supplimentary Examinations, Jul/Aug 2008 DISCRETE STRUCTURES ---Time: 3 hours Max Marks: 60 Answer any FIVE Questions All Questions carry equal marks ????? 1. (a) Obtain the principal disjunctive normal forms of i. ¬P ∨ Q ii. (P ∧ Q) ∨ (¬P ∧ R) ∨ (Q ∧ R) (b) Explain the principal conjunctive Normal Forms. 2. Perform the proofs by contradiction for the following: (a) In a room of 13 people, 2 or more people have their birthdays in the same month. (b) Suppose that the 10 integers 1,2,...,10 are randomly positioned around a circular wheel. Show that the sum of some set of 3 consecutively positioned numbers is at least 17. 3. (a) If relations R and S are both reflexive, show that R ∪ and R ∩ are also reflexive. (b) Show weather the following relations are transitive: R1 = {h1, 1i} R2 = {h1, 2i , h2, 2i} R3 = {h1, 2i , h2, 3i h1, 3i h2, 1i} 4. Discuss some simple Algebraic systems and general properties with suitable examples. 5. (a) How many different outcomes are possible by tossing 10 similar coins. (b) How many integral solutions are there to x1 + x2 + x3 + x4 + x5 = 20, where each xi ≥ 2 6. Find a recurrence relation for the number of ways to make a pile of n chips using garnet, gold, red, white, and blue chip such that no two gold chips are together. 7. (a) Let T1 andT2 be spanning trees of a simple connected graph G and let e be an edge of T1 andT2 show that there is a spanning tree T3 of G containing e and all but one edge of T2 . (b) Compare breadth-first search and depth first search spanning trees for a cycle graph with n vertices.

1 of 2

R6

Code No: R6-11-MCA

8. (a) Show that two simple graphs are isomorphic if and only if their complements are isomorphic. (b) Give two examples graph which have both Euler circuit and Euler path. ?????

2 of 2