Discrete Structures - Dec 2012

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) Show that:
1² + 3² + 5²+ ... + (2n-1)² = (4n³ - n)/3(6 marks) 1(b) Show that if any 5 numbers from 1 to 8 are chosen , then two of them will add to 9.(6 marks) 1(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 aggregate and in physics. Find how many candidates failed:
i. In all the 3 subjects
ii. In mathematics but not in physics
iii. In the aggregate but not in physics
iv. In physics but not in aggregate or in mathematics(8 marks) 2(a) Determine whether the following relation are symmetric, asymmetric and antisymmetric.
(6 marks) 2(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(6 marks) 2(c) If R be a relation in the set of integers z defined by: R={(x,y): x belongs to z, y belongs to z, x-y is divisible by 3}, show that the relation R is an equivalence relation and describe the equivalence classes(8 marks) 3(a) Define with example injective, bijective and surjective function(6 marks) 3(b) Let A={a,b,c,d,e} and let R and S be two relation on A whose corresponding diagraph are shown below. Find complement of R, R^-1, R ? S and R ? S
(8 marks) 3(c) A connected planar graph has 10 vertices each of degree 3 . Into how many regions does a representation of this planar graph split the plane?(6 marks) 4(a) Determine whether the following pairs of graph are isomorphic or not.
(6 marks) 4(b) Let F: R ? R, F(x)=x²-1, g(x)=(4x²+2)
Find i) f o (g o f)
ii) g o (f o g)(6 marks) 4(c) Draw harse diagram of the poset D30 and identify whether it is a linearly ordered or not (8 marks) 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 the relation R by warshall's algorithm(6 marks) 5(b) Define a Ring and field. Let R={0,1,2,3}. Show that the modulo 4 system is a ring.(8 marks) 5(c) Determine which of the following graph contains an eulerian or Hamiltonian Circuit
(6 marks) 6(a) Consider the (2,6) group encoding function e:B2 ? B6 defined by:
e(00) =000000
e(01)=011110
e(10)=101101
e(11)=110011
Decode the following relative to maximum likelihood decoding function
i) 001110
ii) 111101
iii) 110010(8 marks) 6(b) Solve the recurrence relation a_n = 4(a_n-1 - a_n-2) where a₀ = 1, a₁=1(6 marks) 6(c) Show that {1,5,7,11} is a abelian group under multiplication modulo 12(6 marks) 7(a) Define with example
i. Normal subgroup
ii. Spanning tree
iii. Planar graph
iv. Quantifiers(8 marks) 7(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 L1 * L2(6 marks) 7(c) Prove that every field is an integral domain(6 marks)