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

Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) December 2013
GX-12185 [Total Marks : 60]
N.B:	(1)	Question no.1 is compulsory.
	(2)	Attempt any three questions out of remaining four questions.
	(3)	Assumptions made should be clearly stated.
	(4)	Figures to the right indicate marks.
	(5)	Assume suitable data whatever required and justify it.
1.	(a)	Prove that in full binery tree with n vertices, the number of pendant vertices is ( n + 1 )/2.	04
	(b)	Let G be the set of rational numbers other than 1. Let define an operation * on G by a *b = a + b -ab for all a, b ∈G. Prove that (G, *) is a group.	06
	(c)	Find the number of integers between 1 and 1000 which are      (i) Divisible by 2, 3 or 5.      (ii) Divisible by 3 only but not by 2 nor by 5.	05
	(d)	Find all solutions of the recurrence relation  an = 5an-1 + 6an-2 + 7n.	05
2.	(a)	Probe by mathematical induction xn - ynis divisible by x - y.	04
	(b)	Let m be the positive integers greater than 1. Show that the relation R = {(a, b) | a=b (mod m)}, i.e. aRb if and only if m divides a-b, is an equivalence relation on the set of integers.	06
	(c)	Let s = {1, 2, 3, 4} and A = S x S Define the the following relation :- R on A : (a, b) R (a,' b') id and only if a + b = a' + b'.      (i) Show that R is an equivalence relation.      (ii) Computer A/R.	06
	(d)	If f : A → B be both one-to-one and onto, then prove that f-1 : B → A is also both one-to-one and onto.	04
3.	(a)	Consider and equilateral triangle whose sides are of length 3 units. if ten points are chosen lying on or inside the triangle, then show that at least two of them are no more than 1 unit apart.	05
	(b)	Let L1 and L2 be lettices shown below :- Draw the Hasse diagram of  L1 x L2 with product partial order.	07
	(c)	Let A = {a, b, c}. Show that (P(A), ⊆) is a poset. Draw its Hasse diagram. P (A) is the power set of A.	04
	(d)	How many vertices are necessary to construct a graph with exactly 6 edges in which each vertex is of degree 2.	04
4.	(a)	Show that if every element in a group is its own inverse, then the group must be abelian.	04
	(b)	If (G, *) is an abelian group, then for all a, b ∈ G, prove that by mathematical induction (a * b)n = an * bn .	05
	(c)	If f is a homorphism from a commutative group (S, *) to another group (T, *'), then prove that (T, *') is also commutivate.	04
	(d)	Consider the (3, 5) group encoding function e : B3 → B5 defined by   e(000) = 00000 e(001) = 00110 e(010) = 01001 e(011) = 01111 e(100) = 10011 e(101) = 10101 e(110) = 11010 e(111) = 11100 Decode the following words relative to a maximum likelyhood decoding function. (i) 11001     (ii) 01010     (iii) 00111	07
5.	(a)	Find the generating function for the following sequence      1, 2, 3, 4, 5, 6, ..........	05
	(b)	Solve the recurrence relation a2 = 3ar-1 + 2, ≥ 1 with a0 =1, using generating function.	06
	(c)	Show that the following graphs are isomorphic	04
	(d)	Use the laws of logic to show that [(p →q) ∧ ⌉ q] → ⌉  p is a tautology	04