## 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(n^{2}-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: B^{2}→B^{5} 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 a_{r+r}+2a_{r+1}-3a_{r}=0 that satisfies a_{0}=1, a_{1}=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)