0
Discrete Structures : Question Paper Dec 2016 - Computer Engineering (Semester 3) | Mumbai University (MU)

Discrete Structures - Dec 2016

Computer Engineering (Semester 3)

TOTAL MARKS: 80
TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Assume data if required.
(4) Figures to the right indicate full marks.
1(a) Consider the set A={1, 2, 3, 4, 5, 6} under the multiplication modulo 7.
i) Find the multiplication tabel for the above
ii) Find the inverse of 2,3 and 5,6
iii) Prove that it is a cyclic group
iv) Find the orders and the subgroups generated by {3, 4} and {2, 3}
(8 marks)
1(b) Determine the number of integers between 1 and 250 that are divisible by any of the intergers 2, 3, 5 and 7.(6 marks) 1(c) Suppose that A is non empty set, and f is a function that has A as it's domain . Let R be the relation on A consisting of all ordered pairs (x, y) where f (x) = f (y). Show that R is an equivalence relation on A.(6 marks) 2(a) Given S={1, 2, 3, 4} and a Relation R on S given by R={(4,3), (2, 2), (2, 1), (3, 1), (1, 2)}
i) Show that R is not transitive
ii) Find transitive closure of Rby Warshall's algorithm
(8 marks)
2(b) Show that n(n2-1) is divisible by by 24, where n is any odd positive integer.(6 marks) 2(c) Prove that a connected graph with n vertices must have at least n-1 edges. Can a single undirected graph of 8 vertices have 40 edges excluding self loop.(6 marks) 3(a) Find the ordinary generating functions for the given sequences:
i) {0, 1, 2, 3, 4,......}
ii) {1, 2, 3, 4, ......}
iii) {0, 3, 32,33,.....}
iv) {2, 2, 2, 2......}
(8 marks)
3(b) Functions f, g, h are defined on a set, X={1, 2, 3} as [6] f={(1,2), (2, 3), (3, 1)}. g= {(1, 2), (2, 1), (3, 3)}. h= {(1, 1), (2, 2), (3, 1)}.
i) Find f o g , go f, are they equal?
ii) Find f o go h and f o h o g
(6 marks)
3(c) For each of the following sets of weights construct an optimal binary prefix code. For each weight in the set give the corresponding code word:
i) 1,2,4,6,9,10,12 ii) 10,11,14,16,18,21 iii) 5,7,8,15,35,40.
(6 marks)
4(a) Show that the (2,5) encoding function e: B2→B5 defined by e(00)=00000 e(01)=01110 e(10)=10101 e(11)=11011 is a group code . How many errors will it detect?(8 marks) 4(b) Prove the following (A-B) (B-A) = (AU B)- (An B)(6 marks) 4(c) Let T be the set of all even integers. Show that (Z, +) and (T, +) are isomorphic.(6 marks) 5(a) Determine the matrix of the partial order of divisibility on the set A= {1, 3, 5, 15, 30}. Draw the Hasse diagram of the poset. Indicate whether it is a chain or not?(8 marks) 5(b) Define Hamiltonian path and circuit with example. What is the necessary and sufficient condition to exist Hamiltonian circuit?(6 marks) 5(c) Find the solution of ar+r+2ar+1-3ar=0 that satisfies a0=1, a1=2(6 marks) 6(a) Determine whether the following posets are Boolean algebra. Justify your answers.
i) A={1, 2, 3, 6} with divisibility
ii)D20: divisor of 20 with divisibility
(8 marks)
6(b) Define Universal and Existential quantifiers?Explain with examples.(6 marks) 6(c) Prove that the set G={0, 1, 2, 3, 4, 5} is an Abelian group of order 6 with respect to addition modulo 6.(6 marks)

0  upvotes

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.

Search

Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More