## 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^{(n+2)} + 7^{(2n+1)} 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^{3}

g:R ? R is defined as g(x)=4x^{2}+1

h:R ? R is defined as H(x)=7x-1

Find the rule of defining (h^{o}g)^{o}f, g^{o}(h^{o}f) (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^{3} ? B^{8} 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_{625} 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-2}With a_{1}=2 and a_{2}=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)