## Discrete Structures - Dec 2014

### 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)** Prove by mathematical induction x^{n}-y^{n} is divisible by x-y.(5 marks)
**1 (b)** How many vertices are necessary to construct a graph with exactly 6 edges in which each vertex is of degree 2.(5 marks)
**1 (c)** Show that a relation is reflexive and circular if and only if it is an equivalence relation.(5 marks)
**1 (d)** Prove that the set G={1,2,3,4,5,6} is an abelian group under multiplication modulo 7.(5 marks)
**2 (a)** Is it possible to draw a tree with five vertices having degrees 1,1,2,2,4?(4 marks)
**2 (b)** Find how many integers between 1 and 60 are

i) not divisible by 2 nor by 3 and nor by 5.

ii) Divisible by 2 but not by 3 and nor by 5.(8 marks)
**2 (c)** Solve the recurrence relation a_{r+2}-a_{r+1}-6a=4.(8 marks)
**3 (a)** Show that A?(B?C)=(A?B)?(A?C)(4 marks)
**3 (b)** State and explain Pigeonhole principle, extended Pigeonhole principle. 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?(8 marks)
**3 (c)** Let R be a relation on set A={1,2,3,4}, given as

R={(1,1), (1,4), (2,2), (2,3), (3,2), (3,3), (4,1), (4,4)}.

Find transitive closure using Warshall's Algorithm.(8 marks)
**4 (a)** Find the generating function for the following sequence

i) 1,2,3,4,5,6......

ii) 3,3,3,3,3......(4 marks)
**4 (b)** Show that the (2,5) encoding function e:B^{2}?B^{5} defined by

e(00)=00000 e(01)=01110

e(10)=10101 e(11)=11011 is a group code.

How many errors will it detect and correct.(8 marks)
**4 (c)** Draw Hasse Diagram of D_{42}. Find the complement of each element in D_{42}.(8 marks)
**5 (a)** Define Distributive Lattice along with one appropriate example.(4 marks)
**5 (b)** Let the functions f,g and h defined as follows:

f:R→R, f(x)=2x+3

g:R→R, g(x)=3x+4

h:R→R, h(x)=4x

Find gof, fog, hof, gofoh(8 marks)
**5 (c)** $$ Let \ H= \begin{vmatrix}
1 &0 &0 \\0 &1 &1 \\1 &1 &1 \\1 &0 &0 \\0
&1 &0 \\0 &0 &1 \end{vmatrix} $$ Be a parity check matrix. Determine the group code e_{H:} B^{3} ? B^{6}.(8 marks)
**6 (a)** Determine $$ [(p\Rightarrow q)\wedge q]\Rightarrow \neg p $$ is a tautology.(4 marks)
**6 (b)** Define isomorphic graphs. Show that following graphs are isomorphic
(8 marks)
**6 (c)** R be a relation on set of integers Z defined by

R={(x,y)|x-y is divisible by 3}

Show that R is an equivalence relation and describe the equivalence classes.(8 marks)