0
3.3kviews
Discrete Mathematics Question Paper - Dec 18 - Computer Engineering (Semester 3) - Mumbai University (MU)
1 Answer
1
160views

Discrete Mathematics - Dec 18

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. Two dice are rolled. find the probability that the sum is

i) Equal to 1

ii) Equal to 4

ii) less than 13

(6 marks) 00

1.b. Use the laws of logic to show that

$[(p\Rightarrow q)$ ^ ~q] $\Rightarrow $ ~p is a tautology

(6 marks) 00

1.c. Determine the matrix of the partial order of divisibility on the set A. Draw the Hasse diagram of the poset. Indicate those which are chains.

i) A = {1,2,3,5,6,10,15,30}

ii) B = {3,6,12,36,72}

(8 marks) 00

2.a. Find the complement of each element in $D_{42}$
(6 marks) 00

2.b. Let Q be the set of positive rational numbers which can be expressed in the form of $2^{a}$ $3^{b}$ , where a and b are integers. Prove that algebraic structure (Q , .) is a group. Where . is multiplication operation.
(6 marks) 00

2.c. Define isomorphic graphs. Show whether the following are isomorphic or not

enter image description here enter image description here

(8 marks) 00

3.a. Determine which of the following graph contains an Eulerian or Hamiltonian circuit.

enter image description here enter image description here

(6 marks) 00

3.b. For all sets A,X and Y show that

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

(6marks) 00

3.c. Let f(x) = x + 2, g(x) = x - 2, and h(x) = 3x for x $\in$ R, where R = set of real numbers . Find (g , f) , (f , g) , (f , f) , (g , g) , (f , h) , (h , g) , (h , f) , (f , h , g)
(8 marks) 00

4.a. Let R is a binary relation. Let S = {(a,b), (a , c) $\in$ R and (c , b) $\in$ R for some c} Show that if R is an equivalence relation then S is also an equivalence relation.
(6 marks) 00

4.b. Determine the generating function of the numeric function $a_{r}$ , Where

i) $a_{r}$ = $3^{r}$ + $4^{r+1}$ , r $\geq$ 0

ii) $a_{r}$ = 5, r $\geq$ 0

(6 marks) 00

4.c. Consider the (3,6) encoding function e : $B^{3} \Rightarrow B^{6}$ defined by

e(000) = 000000 e(001) = 001100 e(010) = 010011 e(011) = 011111

e(100) = 100101 e(101) = 101001 e(110) = 110110 e(111) = 111010

Decode the following words relative to a maximum likelihood decoding function.

i) 000101 ii) 010101

(8 marks) 00

5.a. Determine the number of positive integers n where 1 $\leq$ n $\leq$ 100 and n is not divisible by 2,3, or 5.
(6 marks) 00

5.b. Use mathematical induction to show that

1+5+9+...............+ (4n-3) = n (2n-1)

(6 marks) 00

5.c. Find the greatest lower bound and least upper bound of the set {3 , 9, 12} and {1 , 2, 4 , 5, 10} if they exists in the poset ($z^{+}$ , / ). where / is the relation of divisibility.
(8 marks) 00

6.a. Let A = {1 , 2, 3 , 4} and Let R = {(1 ,1) (1, 2) (1 , 4) (2 , 4) (3 , 1) (3 , 2) (4 , 2) (4 , 3) (4 , 4)} . Find transitive closure by Warshall's algorithm.
(6 marks) 00

6.b. Let H = {$[0]_{6}, [3]_{6}$} find the left and right cosets in group $Z_{6}$. Is H a normal subgroup of closure by Warshall's algorithm.
(6 marks) 00

6.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$

(8 marks) 00

Please log in to add an answer.