Question Paper: Discrete Structures Question Paper - Jun 19 - Computer Engineering (Semester 3) - Mumbai University (MU)
0

## Discrete Structures - Jun 19

### Computer Engineering (Semester 3)

Total marks: 80
Total time: 3 Hours
INSTRUCTIONS
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Draw neat diagrams wherever necessary.

1.a. Prove using Mathematical Induction 2+5+8+...+(3n-1)=n(3n+1)/2
(5 marks) 00

1.b. Find the generating function for the following finite sequences i) 1,2,3,4,… ii) 2,2,2,2,2
(5 marks) 00

1.c. Let A = {1, 4, 7, 13} and R = {(1,4), (4,7), (7,4), (1,13)} Find Transitive Closure using Warshall’s Algorithm
(5 marks) 00

1.d. Let f : R O R, where f(x) = 2x – 1 and f-1 (x) = (x+1)/2 (05M) Find (f O f -1)(x)
(5 marks) 00

2.a. Define Lattice. Check if the following diagram is a lattice or not.
(4 marks) 00

2.b. Prove that set G = {1,2,3,4,5,6} is a finite abelian group of order 6 with respect to multiplication module 7
(8 marks) 00

2.c. A travel company surveyed it's travellers, to learn how much of their travel is taken with an Air plane, a Train or a Car. The following data is known; make a complete Venn Diagram with all the data. The number of people who flew was 1307. The number of people who both flew and used a train was 602. The people who used all three were 398 in number. Those who flew but didn’t drive came to a total of 599. Those who drove but did not use a train totaled 1097. There were 610 people who used both trains and cars. The number of people who used either a car or a train or both was 2050. Lastly, 421 people used none of these Find out how many people drove but used neither a train nor an airplane, and also, how many people were in the entire survey.
(8 marks) 00

3.a. . (08 M) Q.3 a) Prove $\neg(p \vee(\neg p \wedge q))$ and $\neg p \wedge \neg q$ and $\neg p \wedge \neg q$ are logically equivalent by developing a series of logical equivalences.
(4 marks) 00

3.b. Consider the (3,5) group encoding function defined by

e(000)=0000 , e(001)=00110

e(010)=01001 , e(011)= 01111

e(100)=10011 , e(101)=10101

e(110)=11010 , e(111)=11000

(8 marks) 00

3.c. Mention all the elements of set D36 also specify R on D36 as aRb if a | b. Mention Domain and Range of R. Explain if the relation is Equivalence Relation or a Partially Ordered Relation. If it is a Partially Ordered Relation, draw its Hasse Diagram. D36
(8 marks) 00

4.a. Explain Extended pigeonhole Principle. How many friends must you have to guarantee that at least five of them will have birthdays in the same month.
(4 marks) 00

4.b. Define Euler Path and Hamiltonian Path.

i) Determine Euler Cycle and path in graph shown in (a)

ii) Determine Hamiltonian Cycle and path in graph shown in (b)

(8 marks) 00

4.c. In a group of 6 boys and 4 girls, four children are to be selected. In how many different ways can they be selected such that at least one boy should be there?
(8 marks) 00

5.a. Let G be a group. Prove that the identity element e is unique.
(4 marks) 00

5.b. A pack contains 4 blue, 2 red and 3 black pens. If 2 pens are drawn at random from the pack, NOT replaced and then another pen is drawn. What is the probability of drawing 2 blue pens and 1 black pen?
(4 marks) 00

5.c. Let A be a set of integers, let R be a relation on AXA defined by (a,b) R (c,d) if and only if a+d=b+c. Prove that R is an equivalence Relation.
(8 marks) 00

6.a. Define reflexive closure and symmetric closure of a relation. Also find reflexive and symmetric closure of R.

A={1,2,3,4}

R={(1,1),(1,2),(1,4),(2,4),(3,1),(3,2),(4,2),(4,3),(4,4)}

b) Let H=$\left|\begin{array}{lll}{1} & {0} & {0} \\ {0} & {1} & {1} \\ {1} & {1} & {1} \\ {1} & {0} & {0} \\ {0} & {1} & {0} \\ {0} & {0} & {1}\end{array}\right|$

Be a parity check matrix. Determine the group $e_{H} B^{3} \rightarrow B^{6}$

(8 marks) 00

6.c. Determine if following graphs G1 and G2 are isomorphic or not.

(8 marks) 00