Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) December 2012

a

Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) December 2012
KR-3533 [Total Marks : 100]
N.B:	(1)	Question no.1 is compulsory.
	(2)	Solve any four questions out of remaining six questions.
	(3)	Assumptions made should be clearly stated.
	(4)	Figures to the right indicate full marks.
1.	(a)	Show that :--  12 + 32 + 52+....+(2n - 1)2 = (4n3 - n)/3.	06
	(b)	Show that if any five numbers from 1 to 8 are choosen, then two of them will add to 9.	06
	(c)	Out of 250 candidates who failed in an examination, it was revealed that 128 failed in mathematics, 87 in physics and 134 in aggregate. 31 failed in mathematics and in Physics, 54 failed in the aggregate and in mathematics, 30 failed in the aggregate and in physics. Find how many candidates failed.      (i) In all the three subjects.      (ii) in mathematics but not in physics.      (iii) In the aggregate but not in mathematics.      (iv) In physics but not in aggregate or in mathematics.	08
2.	(a)	Determine whether the following relation are symmetric, asymmetric and antisymmetrio.   (i) [ 1 0 1 0 0 1 1 1 1 ] (ii) [ 1 0 0 1 0 1 1 1 0 0 1 0 0 0 0 1 ]	06
	(b)	Construct truth table to determine whether the given statement is a tautology, contradiction or neither :-  (i) (q ∧p) ∨(q ∧∼p) (ii) (p∧∼q) ∧ p	06
	(c)	if R be a relation in the set of integers z defined by ---      R = {(x,y) : x ∈ z, y ∈ z, x-y is divisible by 3} Show that the relation R is an equivalence relation and describe the equivalence classes.	08
3.	(a)	Define with example injective, subjective and bijective function.	06
	(b)	Let A= {a, b, c, d, e} and Let R and S be two relations on A whose corresponding diagraph are shown below. Find R, R-1 , R ∩S and R ∪S.	08
	(c)	A connected planer graph has 10 vertices each of degree 3. Into how many regions does a representation of this planar graph split the plane?	06
4.	(a)	Determine whether the following pair of graph are isomorphic or not.	06
	(b)	Let f : R → R, f(x) = x2 - 1, g(x) = 4x2 + 2 find (i) f o(g o f) (ii) g o (f o g)	06
	(c)	Draw hasse diagram of the poset D60 and identify whether it is linearly ordered or not?	08
5.	(a)	let A = {1, 2, 3, 4} and R = {(1,2), (2,1), (2,2), (4,3), (3,1)} Find the transitive closure of relation R by Warshall's algorithm.	06
	(b)	Define a ring and field. Let R = {0, 1, 2, 3}. Show that the modulo 4 system is a ring.	08
	(c)	Determine which of the following graph contain an Eulerian or Hamiltonian circuit.	06
6.	(a)	Consider the (2,6) group encoding function e : B2 →B6 defined by :-   e(00) = 0 0 0 0 0 0 e(01) = 0 1 1 1 1 0 e(10) = 1 0 1 1 0 1 e(11) = 1 1 0 0 1 1 Decode the following relative to maximum likelihood decoding function -- (i) 0 0 1 1 1 0   (ii) 1 1 1 1 0 1      (iii)  1 1 0 0 1 0
	(b)	Solve the recurrence relation an = 4(an-1 - an-2) Where a0 1, a1=1.	06
	(c)	Show that {1,5, 7, 11} is a abelian group under multiplication modulo 12.	06
7.	(a)	Define with example :-   (i) Normal subgroup   (ii) Spanning tree.   (iii) Planar graph.   (iv) Quantifiers.	08
	(b)	Consider chains of divisors of 4 and 9 i.e. L1 = {1, 2, 4} and L2 {1, 3, 9} and partial ordering relation of division on L1 and L2. Draw the lattice L1X L2.	06
	(c)	Prove that every field is an integral domain.	06