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

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

Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) May 2013
GS-6525 [Total Marks : 60]
N.B:	(1)	Question no.1 is compulsory.
	(2)	Attempt any four questions out of remaining six questions.
	(3)	Figures to the right indicate marks.
	(6)	Assume suitable data if necessary.
1.	(a)	Prove the mathematical Induction --- 12 + 22 +32+ ......n2 = n(n+1) (2n+1)/6.	08
	(b)	Explain the terms :-      (i) Poset      (ii) Normal Subgroup      (iii) Lattice.	06
	(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 Time 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.	06
2.	(a)	Define 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) = x2  Find     (i) f.g.f     (ii) g.f.g.	08
	(b)	Define equivalence relation on a set. Let R be a relation on the set of integers defined by aRb iff a-b is a muliple of 5. Prove that R is a equivalence relation.	06
	(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.	06
3.	(a)	Explain Hasse diagram. Draw the Hasse diagram of the relation given by :--     (i) R1= { (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) }    (ii) R2= { (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) }	08
	(b)	Let A = {1, 2, 3, 4} and R = { (1, 2), (2, 3), (3, 4), (2, 1)}. Find the Transitive closure or R using Warshall's Algorithm.	06
	(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 o them must be no further apart than 1 unit.	06
4.	(a)	Show that the following graphs are isomorphic.	08
	(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.	06
	(c)	Define :      (i) Integral domain      (ii) Field      (iii) Normal Subgroup.	06
5.	(a)	What is minimum spanning tree? Explain any one technique with example.	08
	(b)	Define Cyclic Group. Prove that the set A = {0, 1, 2, 3, 4, 5} is a finite abelian under addition modulo 6.
	(c)	Determine whether the given graph has a Hamilton circuit or Eulerian circuit. If it does, find such a circuit.

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

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

Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) May 2012
GN-8699 [Total Marks : 60]
N.B:	(1)	Question no.1 is compulsory.
	(2)	Attempt any four questions out of remaining six questions.
	(3)	Assumptions made should be clearly stated.
	(4)	Assume any suitable data wherever required but justify the same.
	(5)	Figures to the right indicate marks.
	(6)	illustrate answer with sketches wherever required.
1.	(a)	Prove that if A ⊆ C and B ⊆ C then A U B ⊆ C.	05
	(b)	Prove that the maximum number of node on level n of a binary tree is 2n where n ≥0.	05
	(c)	Prove that if any 14 integer from 1 to 25 are chosen, then one of them is multiple of another.	05
	(d)	Prove that in any ring (R+.) the additive inverse of each ring element is unique.	05
2.	(a)	Let Q be the set of positive rational numbers which can be expressed in the form 2a3b. Where a and b are integers, prove that algebraic structure (Q.) is a group. Where. is multiplication operation.	07
	(b)	Determine whether the poset with the following Hasse diagrams are lattices or not.	07
	(c)	Let R the relation on set of real numbers such that aRb if and only if a-b is an integer. Prove that R is an equivalence relation.	06
3.	(a)	Find the solution of recurrence relation      an=5an-1 - 6an-2 + 7n	07
	(b)	Show that ((PVQ)∧ ⌉(⌉P ∧(⌉QV ⌉ R)) V (⌉P ∧⌉ Q) V (⌉ P ∧⌉ R)) is tautology.	07
	(c)	Let A = {1, 2, 3, 4} for the relation R whose matrix is given below. Find the matrix of transitive closure using warshall algorithm.   [ 1 0 0 1 ] 1 1 0 0 0 0 1 0 0 0 0 1
4.	(a)	In a survey of 60 people, it was found that     25 read Business indis 26 reads india Today. 26 read Times of india. 11 read both Business india and India Today. 09 read both Business India and Times of India. 08 read both India today and Times of india. 08 read none of the three.      i) How many read all three?      ii) How many read exactly one?	08
	(b)	Use induction to prove that 7n -1 is divisible by 6 for n = 1, 2, 3,......	06
	(c)	Let G be the group and let a and b are elements of G then verify that (ab)-1 = b-1a-1	06
5.	(a)	Consider (3,8) encoding function e:B3 -.B8 defined by   e(000) = 00000000 e(100) = 10100100 e(001) = 10111000 e(101) = 10001001 e(010) = 00101101 e(110) = 00011100 e(011) = 10010101 e(111) = 00110001 and let d be the (8,3) maximum likelihood decoding function associated with e. How many errors can (e,d) correct?	08
	(b)	Prove that if (F, + ,.) is a 'field then it is a integral domain.	06
	(c)	A connected planar graph has a 9 vertices having degrees 2, 2, 2, 3, 3, 3, 4, 4, 5. how many edges are there?	06
6.	(a)	Let G be the group of integers under the operations addition and H be group of all even integers under the operation of addition, show that the function f:G →H is an isomorphism.	08
	(b)	Define Eulerian, Hamilton path and circuit with example. What is the necessary and sufficient condition for eular path and circuit?	06
	(c)	Suppose R and S is the relation from A to B, then prove that  (R∩S)-1 = R-1 ∩ S-1 and (RUS)-1 = R-1 U S -1
7.	(a)	Consider the chains of 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 L1 x L2.
	(b)	Prove that the set {1, 2, 3, 4, 5, 6} is group under multiplication modulo 7.	05
	(c)	How many paths of length 4 are there from a to d in simple graph as shown below.	07
	(d)	Find the complement of each element in D20 and D30.	05

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

Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) December 2011
MP-4117 [Total Marks : 60]
N.B:	(1)	Question no.1 is compulsory.
	(2)	Answer any four out of remaining six questions.
	(3)	Assumptions made should be clearly stated.
	(4)	Assume any suitable data wherever required but justify the same.
	(5)	Figures to the right indicate marks.
	(6)	illustrate answer with sketches wherever required.
1.	(a)	A survey on a sample of 25 new cars being sold of a local auto dealer was conducted to see which of three popular options, air conditioning A, radio R, and popular windows W, were already installed. The survey found, 15  had air conditioning 12  had radio 11  had power windows 5   had air conditioning and power window 9   had air conditioning and radio 4   had radio and power windows 5   had all three options. Find the no. of cars having: (i) Only one of these options (ii) radio & power windows but not air conditioning (iii) none of these options.	06
	(b)	Explain the following terms with suitable example.   (i)  Disjoint set   (ii)  Symmetric difference   (iii)  Partition product.	04
	(c)	Given A= {1, 2, 3, 4} and B {x, y, z}. Let R be the following relation from  A to B : R= {(1,y), (1,z), (3,y), (4,x), (4,z)} (i)  Determine the matrix of the relation. (ii)  Draw the arrow diagram of R. (iii)  Find the inverse realtion R-1 of R (iv)   Determine the domain and range of R.	06
	(d)	Prove the mathematical induction that 6n+2 + 72n+1 is divisible by 43 for each +ve integer n.	04
2.	(a)	Write English sentences for following where: P(x) : x is even,  Q(x): x is prime, R(x,y) : x + y is oven (i)   ∃x ∀y R(x,y) (ii)  ∀x ∃y R(x,y) (iii)  ∼(∃x P(x)) (iv)  ∼(∀x Q(x)) (v)   ∀x ∃y R(x,y) (vi)  ∃x ∀y R(x,y) (vii) ∀x (∼Q(x)).	07
	(b)	Show that if 30 dictionaries in a library contain total of 61,327 pages, then one of the dictionaries must have at least 2045 pages.	06
	(c)	Let G = {0, 1, 2, 3, 4, 5} (i)  Prepare composition table with respect to '+6' (ii)  prove that G is an abelian group with respect to '+6' (iii)  Find the inverse of 2, 3 and 5. (iv)  Is it cyclic? (v)   Find the order of 2, 3 and sub groups generated by these elements.	07
3.	(a)	Determine whether following graphs are isomorphic:	06
	(b)	(x1 ∧ x2) V (x1 ∧x3) V (x2 ∧x3) be the Boolean expression. Write E(x1, x2, x3) in Disjunctive & Conjuunctive Normal Form.	07
	(c)	f: R→R is defined as f(x) =4x2+1 h: R→R is defined as h(x) =7x-1 find the rule of defining (hog)of, go (hof).	07
4.	(a)	Explain the Eulerian & Hamiltonian path & circuit with suitable example.	06
	(b)	What is the hamming distance? Consider (3,8) encoding function e: B3→B8 defined by   e(000) = 00000000 e(001) = 10111000 e(010) = 00101101 e(011) = 10010101 e(100) = 10100100 e(101) = 10001001 e(110) = 00011100 e(111) = 00110001 and let d be the (8,3) maximum likelihood decoding function associated with e. How many errors can (e,d) correct?	07
	(c)	Determine whether D625 is a Boolean algebra. justify your answer.	07
5.	(a)	A function f : R {7/3} → R - {4/3} is  defined as:                     f (x) = 4x - 5/3x - 7 Prove that 'f' is bijective and find the rule for 'f'.	07
	(b)	Let A = }1, 2, 3, 4, 6} and let R be the relation on A defined by "x divides y" written x/y (Note x/y if there exists an integer z such that xz=y.) (i)  Write R as a set of ordered pairs. (ii)  Draw its directed graph. (iii)  Find the inverse relation of R.	06
	(c)	Let A = {11, 12, 13, 14} and Let R = {(11,12), (12,13), (13,14), (12,11)}. Find transitive Closure of R using warshall's algorithm.	07
6.	(a)	Let R be the following equivalence relation on the set A={1, 2, 3, 4, 5, 6}:       R = {(1,1), (1,5), (2,2), (2,3), (2,6), (3,2), (3,3), (3,6), (4,4), (5,1), (5,5), (6,2), (6,3), (6,6)}. Find the partitions of A inducted by R, i.e., find the equivalence classes of R.	06
	(b)	Define a lattice. Let X = {1,3,5,15,30,60,90,180,} with the relation of divisibility. Draw the hasse diagram for it. Whether it is a lattice? Justify your answer. Find the complements of all them elements.	07
	(c)	Determine the sequence whose recurrence relation is an=4an-1+5an-2 with a1=2 &  a2=6.	06
7.	(a)	Explain various operations on the binary trees.	06
	(b)	Verify whether (Use laws of logic)           ((PVQ) ∧⌉(⌉P∧(⌉QV⌉R))V(⌉P∧⌉)V(⌉P∧⌉R) is tautology. Define universal and existential quantifier with suitable example.	07
	(c)	Define a Ring & Field. Let R = {0, 2, 4, 6, 8}. Show that R is a Commutative ring under additions and multiplication modulo 10. Verify  whether it is field or not.	07

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

Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) December 2010
GT-6232 [Total Marks : 60]
N.B:	(1)	Question no.1 is compulsory.
	(2)	Attempt any four questions out of remaining six questions.
1.	(a)	Using mathmetical Induction prove that 5n-1 is divisible by 4 for n>∼1	05
	(b)	What is the minimum number of students required in Discrete Structure class to be sure that at least six will receive the same grade. if there are five possible grades A,B,C,D,E?	05
	(c)	Show that if relation on set A transitive and irreflexive then it is symmetric	05
	(d)	Draw the Hasse diagram of D60 and check if it is lattice?	05
2.	(a)	Among the integers 1 to 1000:   (i) How many of them are not divisible by 3, nor by 5, nor by 7?   (ii) How many are not divisible by 5 and 7 but divisible by 3?	10
	(b)	Define Universal and Existential quantifiers. Transcribe the following into logical notation. Let the universe of discourse be the real numbers.      (i) There are positive values of x and y such that x.y > 0      (ii) For every value of x there is some value of y such that x.y = 1      (iii) There is a value of x such that if y is positive then x+y is negative.	10
3.	(a)	Explain Warshwall's algorithm. Let A = {1,2,3,4,5} and let R be a relation on A Such that R= {(1,1),(1,4),(2,2),(3,4),(3,5),(4,1),(5,2),(5,5)} Find transitive elesure of R by Warshwall's algorithm.	10
	(b)	Define Equivalence relation. let Z be set of integers. Define R on Z iff 6 divides (a-b). Show that R is equivalence relation. Find Z/R.	10
4.	(a)	Let f R → R f(x)=x3, g: R → R g(x)=4x2 + 1, h:R→R h(x)=7x-2 Find  (i) go(hog)     (ii) go(hof)	06
	(b)	Define with example injective, surjective and bijective function	06
	(c)	Define Hamiltonian path and Hamiltonian circuit and find it in K4,3	04
	(d)	Define with example Reflexive closure and symmetric closure	04
5.	(a)	Prove that if (F, +,.) is a field it is an integral domain.	10
	(b)	Consider the group G={1,2,3,4,5,6} under multiplication modulo 7.      (i) Find multiplication table of G, is G abelian Group.      (ii) Find the identity and inverse of each element	10
6.	(a)	Find the solution of recurrence relation: a3 = 5 an-1 - 6an-2 + 7n	04
	(b)	Consider the (2,5) group encoding function - e:B2 → B5 defined by e(00) = 00000     e(10) = 10101     e(01) = 01110     e(11) = 11011 Decode the following relative to maximum likelihood decoding function. (i) 11110     (ii) 10011      (iii) 10100	06
	(c)	R={0,2,4,6,8} Show that R is commutative ring under addition and multiplication modulo 10	06
	(d)	Define subgroup and normal subgroup with example.	04
7.	(a)	Determine whether lattice D30 is distributive, complemented or both. Justify your answer.	06
	(b)	Let G be the group integers under the operation addition, and H be group of all even integers under the operation of addition, show that the function f: G→H is as isomorphism.	06
	(c)	Define and explain bipartite graph, complete bipartifc graph with example.	04
	(d)	Find all spanning trees of the following graph	04

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.

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

Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) December 2009
SP-7370 [Total Marks : 100]
N.B:	(1)	Question no.1 is compulsory.
	(2)	Attempt any four questions out of remaining six questions.
	(3)	Figures to the right indicate full marks.
1.	(a)	Prove by Mathematical induction method-       12 + 22 + 32 + ..................+n2 =n(n+1) (2n+1)⁄6	05
	(b)	If A=B=C=R where R is set of real number and f: A→B, g : B → C are functions defined by f(x) = x + 1, g(x) = X2 + 2, then find (g o f) (x) and (f o g) (2).	05
	(c)	Show that a group (G, *) is abelian if and only if (a * b)2 = a2 * b2.	05
	(d)	In a Boolean algebra, prove that text a Λ b = a v b.	05
2.	(a)	Show that the relation R = {(x, y) is divisible by 4; where x, y are int ehers} is an equivalence relation. Write the equivalence classes given by R.	06
	(b)	Solve the recurrence relation an+2 - 5an+1 + 6an = 2 with initial conditions a0 = 1, a1 = - 1.	06
	(c)	Explain Quantifiers. Negate the statement '√2 is not a rational number'.	04
	(d)	Draw all Hasse diagrams of posets with three elements.	04
3.	(a)	Find the transitive closure of the relation R on set A defined by the given digraph using Warshall's Algorithm.	06
	(b)	Show that te (2, 5) encoding function e : A2→B5 defined by   e(00) = 00000 e(01) = 01110 e(10) = 10101 e(11) = 11011 is a group code. Find the minimum distance.	06
	(c)	Find the lower and upper bounds of the subsets {a, b, c} and {a, c, d, f} of given poset.	04
	(d)	Show that if any five integers form 1 to 8 are selected, then the sum of at least two of them will be 9.	04
4.	(a)	Consider the relation R on set of integers defined as xRy iff y = xk ; k is positive integer. Show that R is a partial order relation.	06
	(b)	Determine the Eulerian path and hamiltonian path, if exist, in the following graph.	06
	(c)	Check if the set A = {2, 4, 12, 16} is a lattice under divisibility.	04
	(d)	Find the generating function of the following sequences         (i) 1, 0 - 1, 0, 1, 0 - 1, 0, .........  (ii)  1, 1, 1, 1, 1,.........	04
5.	(a)	Let H = [ 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 0 0 1 be a parity check matrix. Decode the following words relative to maximum likelihood decoding function (i) 011001  (ii) 101011  (iii) 111010.	06
	(b)	Show that the lattices given in the following Hasse diagrams are non distributive	06
	(c)	Find the number of vertices of the graph having 16 edges if degree of each vertex is 2.	04
	(d)	For sets A, B, C prove that A x (B∪C) = (A x B) ∪ (A x C)	04
6.	(a)	Define isomorphic graphs. Determine whether the given graphs are isomorphic or not	06
	(b)	Draw Hasse diagrams of D4 x D9 is the set of positive divisors of n.	06
	(c)	Show that (I, ⊕, ⊕) is a commutative ring with identity where the operations ⊕ and ⊗ are defined as a ⊗ b = a + b - 1 and a ⊗ b = a + b - ab.	06
			04
7.	(a)	Show that {0, 1, 2, 3, 4, 5} is an abelian group under the operation+6.	06
	(b)	Define the following with example.      (i) Ring homomorphism      (ii) Field      (iii) Spanning tree.	06
	(c)	Show that the function f : R-{2} → R -{0} where R is set of real numbers defined by f(x) = 1/x-2 is a bijection. Find its inverse.

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

Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) May 2009
VR-3330 [Total Marks : 60]
N.B:	(1)	Question no.1 is compulsory.
	(2)	Attempt any four questions out of remaining six questions.
	(3)	Assumptions made should be clearly stated.
	(4)	Figures to the right indicate full marks.
	(5)
1.	(a)	Prove that A x(B ∩ C) = (A x B) ∩ (A x C).	04
	(b)	Prove there is no rational number p/q whose square is 2.	04
	(c)	Show than n3+2n is divisible by 3 for all n > 1.	06
	(d)	Among the integers 1 and 300,      (i) How many of them are divisible by 3,5 or 7 and are not divisible by 3 nor by           by 5 nor by 7?      (ii) How many of them are divisible by 3 but not 5 nor by 7?	06
2.	(a)	Prove that if any 14 integers from 1 to 25 are chosen, than one of them is a multiple of another	04
	(b)	Solve the recurrence relation dn = 2dn-1- dn-2 with initial conditions d1=1.5 and d2 = 3.	04
	(c)	Let A = Z, the set of integers and let R be the relation less than. Is R Transitive?	06
	(d)	Negate the statement. For all real numbers x, if x> 3 then x2>9.	06
3.	(a)	Let A = {a, b, c, d, e}and       R = { (a,a), (a,b), (b,c), (c,e), (c,d), (d,e) } Compute (i) R2 and R∞.	06
	(b)	Let A = { 1, 2, 3, 4 } and let R = { (1,2), (2,3), (3,4), (2,1) } Find Transitive Closure of R using Warshall's algorithms.	06
	(c)	Explain the Equivalence Class with an Example.	04
	(d)	Explain with an Example dual of the poset.	04
4.	(a)	Show that in bounded is distributive lattice, if a complement exists. it is unique.	06
	(b)	Determine whether the following posets are boolean algebras. Just your answers      (i) A = { 1, 2, 3, 6} with divisibility.      (ii) D20 : divisors of 20 with "divisibility".	06
	(c)	Explain primitive Recursive Function. Every primitive recursive function is a total function, justify.	04
	(d)	(i)  Is every Eulerian graph as Hamiltonian? (ii)  is every Hamiltonian graph an Eulerian ?       Justify with the necessary graph.	04
5.	(a)	So that if set A has 3 elements, than we can find 8 relations on A that all have the same symmetric closure.	06
	(b)	Draw the Hasse diagram of the poset A = { 2, 3, 6, 12, 24, 36, 72 } Under the relation of divisibilty. is this poset a lattice? justify.	06
	(c)	Let A = { 0, -1, 1} and B = { 0, 1}, Let f : A → B where f(a) = | a |. Is f onto?	04
	(d)	State and prove right or left cancellation property for a group.	04
6.	(a)	Prove that every field is an integral domain.	06
	(b)	Consider the chains of divisors of 4 and 9 i.e.,L1= {1, 2, 4} And L2= {1, 3, 9}. Find partial ordering relationsof division on L1 and L2. Draw lattice of L1 x L2.	04
	(c)	Explain the linear recurrence relations with constant co-efficeints.	04
	(d)	Explain the types of generating function with an example.	04

7.	(a)	Consider the (3, 5) froup encoding function e : B3 → B5 defined by --     e (000) = 00000   e (100) = 10011 e (001) = 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	06
	(b)	Let G be the set of all nonzero real numbers and let     a * b = ab / 2. Show that (G, *) is an Abelian group.	06
	(c)	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 B2 → B2	04
	(d)	Explain congruence relation with an example.	04