Discrete Structures - Dec 2011

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) 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 window W, were already installed. The survey found,
15 had Air conditioning,
12 had radio,
11 had power window,
5 had air conditioning and power window,
9 had air conditioning and radio,
4 had radio and power window,
3 had all three option,
2 had no option
Find the number of cars having:
(i) Only one of these option
(ii) Radio and power window but not the air conditioning
(iii) None of these option. (6 marks) 1(b) Explain the following terms with suitable example:
(i) Disjoint set
(ii) Symmetric difference
(iii) Partition set
(iv) Cartesian product
(4 marks) 1(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 relation
(ii) Draw the arrow diagram of R
(iii) Find the inverse relation R-1 of R
(iv) Determine the domain and the range of R
(6 marks) 1(d) Prove by the mathematical induction that 6⁽ⁿ⁺²⁾ + 7⁽²ⁿ⁺¹⁾ is divisible by 43 for each +ve integer n(4 marks) 2(a) Write English sentence for following where P(x): X is even, Q(x): X is prime, R(x,y): X+Y is even:
(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)) (7 marks) 2(b) Show that if 30 dictionaries in a library containing total of 61,327 pages, then one of the dictionary must have at least 2045 pages.(6 marks) 2(c) Let G={0,1,2,3,4,5}
(i) Prepare composition table with respect to _'+6'
(ii) Prove that G is an abelain group with respect to _'+6'
(iii) Find the inverse of 2,3,5
(iv) Is it cyclic?
(v) Find the order of 2,3 and the subgroup generated by these elements. (7 marks) 3(a) Determine whether the following graphs are isomorphic:

(6 marks) 3(b) (x1 ? x2) ? (x1 ? x3) ? (x2 ? x3) be the Boolean expression. Write E(x1,x2,x3) in disjunctive and conjunctive normal forms. (7 marks) 3(c) f:R ? R is defined as f(x)=x³
g:R ? R is defined as g(x)=4x²+1
h:R ? R is defined as H(x)=7x-1
Find the rule of defining (h^og)^of, g^o(h^of) (7 marks) 4(a) Explain the Eulerian and Hamiltonian path and circuit with suitable example (6 marks) 4(b) What is the hamming distance? Consider (3,8) encoding function e: B³ ? B⁸ 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 decode function associated with e. How many errors can (e,d) correct? (7 marks) 4(c) Determine whether D₆₂₅ is a Boolean algebra. Justify your answer(7 marks) 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^-1 (7 marks) 5(b) Let A={1,2,3,4,6} and 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. (6 marks) 5(c) Let A={11,12,13,14} and let R={(11,12), (12,13), (13,14), (12,11)}. Find the transitive closure of R using Warshall's algorithm. (7 marks) 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 partition of A induced by R, i.e, find the equivalence classes of R.(6 marks) 6(b) Define a lattice. Let X={1,3,5,15,30,60,90,180} with the relation of divisibility. Draw the harse diagram for it. Whether it is a lattice? Justify your answer. Find the complement of all the elements. (7 marks) 6(c) Determine the sequence whose recurrence relation is a_n=4a_n-1+5a_n-2With a₁=2 and a₂=6 (7 marks) 7(a) Explain various operations on binary trees. (6 marks) 7(b) Show that (P?Q) ? ~(~P?{~Q?~R}) ? (~P?~Q) ? (~P?~R) is tautology (use law of logic). Define universal and existential quantifier with suitable example.(7 marks) 7(c) Define a ring and field. Let R={0,2,4,6,8}. Show that R is a commutative ring under addition and multiplication modulo 10. Verify whether it is a field or not. (7 marks)