Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) May 2010

Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) May 2010
AN-2503 [Total Marks : 100]
N.B:	(1)	Question no.1 is compulsory.
	(2)	Attempt any four questions out of remaining six questions.
	(3)	Assumption made should be clearly stated.
	(4)	Figures to the right indicate full marks.
1.	(a)	Use mathematical induction to prove the following inequality n<2" for all positive integers n.	04
	(b)	Define a pigeonhole principle. Show that if seven colours are used to paint 50 bicycles, at least 8 bicycles will be of same colour.	04
	(c)	What is an universal and existential quantifier?	04
	(d)	Define the following terms with the example.      (i) Disjoint set                     (iii) Partial order relation      (ii) Symmetric difference     (iv) Antisymmetric realtion.	04
	(e)	How many numbers must be selected from the set {1, 2, 3, 4, 5, 6} to Guarantee that at least one pair of these numbers add up to 7?	04
2.	(a)	Prove that if x is a rational number and y is an irrational number, than x + y is an irrational number.	05
	(b)	Define following -- Power Set, Surjective and Injective function	05
	(c)	Is a graph a planner graph?	05
	(d)	how many friends must you have to guarantee that at least five of them will have birthdays in same month?	05
3.	(a)	Let A = {a, b, c, d} and x be a relation on A whose matrix is   MR = [ 1 0 1 1 ] 0 1 1 1 0 0 1 1 0 0 0 1 Prove that R is partial order. Draw Hasse diagram of R.	10
	(b)	(i) Define group, monoid, semigroup (ii) Converse of statement is given.       Write inverse and contra positive of statement       " If i came early then i can get a car"	05
4.	(a)	Write Prims Algorithm. Apply it to following graph.	10
	(b)	(i) Let A = {1, 2, 3, 4, 5}, P={{1,2} {3}, {4,5}} find equivalence relation determined by P and draw its diagraph. (ii) Check whether relation is reflexive, irrreflexive, symmetric, anti symmetric, transitive. R1 = {(1,1), (1,2), (2,1),(2,2),(3,3),(4,3),(3,4),(4,4)} R2 = {(1,3), (1,1), (3,1),(1,2),(3,3),(4,4)}	05
5.	(a)	Prove that the set G = {1,2,3,4,5,6} is a Finite Abelian group of order 6 with respect to multiplication modulo7.	10
	(b)	(i) Find out Eular path and Eular ckt for the graph	05
		(ii) Find out Hamiltonian path and Hamiltonian cycle.	05
6.	(a)	(i) Show that (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.	05
		(ii) R={0,2,4,6,8}. Show that R is commutative ring under addition and multiplication modulo 10. Verify whether it is field or not.	05
	(b)	(i) Let L be the bounded distributive lattice.      Prove that if complement exist then it is unique.	05
		(ii) give the exponential generating functions for the sequences given below       (i) { 1, 1. 1,.............................}       (ii) { 0,1,0,-1,0,1,0-1,.............}	05
7.	(a)	In any Ring ( R + .) prove that (i) The zero element z is unique. (ii) The additive inverse of each ring element is unique.	10
	(b)	(i) Let m = 2, n = 5 and   H= [ 1 1 0 ] 0 1 1 1 0 0 0 1 0 0 0 1 Determine the group code eH : B2 → B5.	05
		(ii) Consider the (3,5) group encoding Function e : e: B2 → B5 defined by e(000) = 00000 e(100) = 10011 e(000) = 00110 e(101) = 10101 e(010) = 01001 e(110) = 11010 e(011) = 01111 e(111) = 11100 Decode  the following words relative to a maximum likelihood decoding function   (i) 11001.  (ii) 01010.  (iii) 00111.