Discrete Structures - May 2013

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) Prove by Mathematical Induction -
$$1^2+2^2+3^2+\bullet{}\bullet{}\bullet{}\bullet{}\bullet{}\bullet{}\bullet{}\bullet{}n^2=\frac{n(n+1)(2n+1)}{6}$$(8 marks) 1 (b) Explain the terms :-
(i) Poset
(ii) Normal Subgroup
(iii) Lattice.(6 marks) 1 (c) In a survey of 60 people, it was found that 25 reads Newsweek Magazine, 26 reads Times and 26 reads Fortune. Also 9 reads both Newsweek and Fortune, 11 reads both Newsweek and Times, 8 reads Times and Fortune and 8 reads no magazine at all.
(i) Find the number of people who read all three magazines.
(ii) Determine number of people who read exactly one magazine.
(6 marks) 2 (a) Determine injective, surjective and bijective functions. If f: R → R and g: R → R are defined by the formulas - f(x)=x+2 and g(x)=x² find (i) f.g.f. (ii) g.f.g.(8 marks) 2 (b) Define equivalence relation on a set. Let R be a relation on the set of integers defined by a Rb iff a-b is a multiple of 5. prove that R is a equivalence relation.(6 marks) 2 (c) State the converse, inverse and contrapositive of the following :-
(i) If it is cold, then he wears a hat.
(ii) If an integer is a multiple of 2, then it is even.
(6 marks)

Explain Hasse diagram. Draw the Hasse diagram of the relation given by

3 (a)(i) R₁= { (1,1), (1,2), (1,3), (1,4), (1,5), (2,2), (2,3), (2,4), (2,5), (3,3), (3,4), (3,5), (4,4), (4,5), (5,5) }(4 marks) 3 (a)(ii) R₂= { (1,1), (1,3), (1,4), (1,5), (2,2), (2,3), (2,4), (2,5), (3,3), (3,4), (3,5), (4,4), (5,5), } (4 marks) 3 (b) Let A= { 1, 2, 3 4} and R= { (1,2), (2,3), (3,4), (2,1)}. Find the Transitive closure of R using Warshall's Algorithm.(6 marks) 3 (c) Consider the region shown below. It is bounded by a regular hexagon whose sides are the length 1 units. Show that if any seven points are chosen in this region then two of them must be no further apart than 1 unit.
(6 marks) 4 (a) Show that the following graphs are isomorphic. :
(8 marks) 4 (b) Let R={ (1,2), (4,3), (2,2), (2,1), (3,1) } be a relation on s={1,2,3,4}. Find the symmetric closure of R.(6 marks) 4 (c) Define :-
(i) Interal domain
(ii) Field
(iii) Normal Subgroup.
(6 marks) 5 (a) What is a minimum spanning tree? Explain one techniques with example.(8 marks) 5 (b) Define Cyclic Group. Prove that the set A = { 0, 1, 2, 3, 4, 5} is a finite abelian under addition modulo 6.(6 marks) 5 (c) Determine whether the given graph has a Hamilton circuit or Eulerian circuit. If it does, find such a circuit :
(6 marks)