0
2.2kviews
Discrete Mathematics Question Paper - Dec 17 - Computer Engineering (Semester 3) - Mumbai University (MU)
1 Answer
0
98views

Discrete Mathematics - Dec 17

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 that 1.1! +2.2! + 3.3! + ....... + n.n! = (n+1)!- 1, where n is a positive integer.
(5 marks) 00

1.b. Let A = {a,b,c} . Show that (P(A), $\subseteq$) is a poset and draw its Hasse diagram .
(5 marks) 00

1.c. Explain the terms-

i) Lattice

ii) Poset

iii) Normal subgroup

iv) Group

v) Plannar Graph

(5 marks) 00

1.d. Comment whether the function f is one to one or onto.

consider the function: f: N $\Rightarrow$N is a set of natural numbers including zero. $ f(j) = j^{2}+2$

(5 marks) 00

2.a. Find the number of ways a person can distribute Rs.601 as pocket money to his three sons, so that no son should receive more than the combined total of the other two. (Assume no fraction of a rupee is allowed)
(6 marks) 00

2.b. Let A = {a1, a2, a3, a4, a5} and let R be a relation on A whose matrix is

enter image description here

Find $M_{R}$* by Warshall's algorithm

(6 marks) 00

2.c. Find the complete solution of the recurrence relation: $a_{n}+2a_{n-1} = n + 3$ for $ n \geq 1$ and with $a_{0} = 3$
(4 marks) 00

2.d. let f : R $\Rightarrow$ R defined as $f(x) = x^{3}$and

let g : R $\Rightarrow$ R defined as $g(x) = 4x^{2} + 1$

Find out $g^{0}f, f^{0}g , f^{2} , g^{2}$

(4 marks) 00

3.a. Given that a student had prepared, the probability of passing a certain entrance exam is 0.99 . Given that a student did not prepare, the probability of passing the entrance exam is 0.05. Assume that the probability of preparing is 0.7 . The student fails in the exam. What is the probability that he or she did not prepare?
(6 marks) 00

3.b. Define equivalence relation with example. let 'T' be a set of triangles in a plane and define R as the R = {(a, b) a,b $\in$ T and a is congruent to b } then show that R is an equivalence relation.
(4 marks) 00

3.c. Let A=B=R , the set of real numbers

let f: A $\Rightarrow$ B, be given by the formula f(x) = $2x^{3} - 1$ and let g : B $\Rightarrow$ A be given by

enter image description here

Show that f is a bijection between A and B and g is a bijection between B and A.

(4 marks) 00

3.d. Let $Z_{n}$ denote the set of integers {0,1,2.......n-1}. Let O be binary operation on $z_{n}$ such that a O b = the remainder of ab divided by n.

i) Consruct the table for the operation O for n=4.

ii) Show that ($Z_{n}$ O)is a semigroup for any n.

(4 marks) 00

4.a. i) Among 50 students in a class, 26 got an A in the first examination and 21 got an A in the second examination. If 17 students did not get an A in either examination , how many students got an A in both examinations?

ii) If the number of students who got an A in the first examination is equal to that in the second examination, if the total numbers of students who got an A in exactly one examination is 40 and if 4 students did not get an A in either examination, then determine the number of students who got an A in the first examination only, who got an A in the second examination only; and who got an A in both the examination.

(6 marks) 00

4.b. Consider the (2,5) group encoding function

e : $B^{2} \Rightarrow B^{5}$ defined by

e(00) = 00000 e(01) = 01110

e(10) = 10101 e(11) = 11011

Decode the following works relative to a maximum likelihoods decoding function.

i) 11110 ii) 10011 iii)10100

(4 marks) 00

4.c. i) Is every Eulerian graph a Hamiltonian?

ii) Is every Hamiltonian graph a Eulerian?

Explain with the necessary graph.

(4 marks) 00

4.d. Given the parity check matrix

enter image description here

Find the minimum distance of the code generated by H. How many errors it can detect and correct?

(4 marks) 00

5.a. Explain the Pigeonhole principle and Extended Pigeonhole principle. Show that in any room of people who have been doing some handshaking there will always be atleast two people who have shaken hands the same number of times.
(6 marks) 00

5.b. Determine whether the Poset with the following Hasse diagrams are lattices or not. Justify your answer.

enter image description here

(6 marks) 00

5.c. From the following digraphs, write the relation a set of ordered pairs. Are the relations equivalence relations?

enter image description here

(4 marks) 00

5.d. For the set X = {2,23,6,12,24,36} , is a relation $\leq$ is defined as x $\leq$ y if x divides y, Draw the Hasse diagram for (X, $\leq$) . Answer the following:

i) What are the maximal and minimal elements?

ii) give one example of a chain and antichain?

iii) Is the Poset a lattice?

(4 marks) 00

6.a. Prove that the set {1,2,3,4,5,6} is group under multplication modulo 7.
(6 marks) 00

6.b. Given a generating function, find out corresponding sequence.

i) $\dfrac{1}{3-6x}$

ii) $\dfrac{x}{1 - 5x + 6x^{2}}$

(6 marks) 00

6.c. Determine whether following graphs are isomorphic or not.

enter image description here

(4 marks) 00

6.c. Prove the following (use laws of set theory)

A x (X $\cap$ Y) = (A x X) $\cap$ (A x Y)

(4 marks) 00

Please log in to add an answer.