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²-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²→B⁵ 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₀=1, a₁=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)