## Discrete Structures - Dec 2013

### 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 that in a full binary tree with n vertices, the number of pendant vertices is (n+1)/2(4 marks)
**1 (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.(6 marks)
**1 (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.(5 marks)
**1 (d)** Find all solutions of the recurrence relation

a_{n}=5a_{n-1} + 6a_{n-2} + 7^{n}(5 marks)
**2 (a)** Prove by mathematical induction x^{n} - y^{n} is divisible by x-y.(4 marks)
**2 (b)** Let m be the positive integers greater that 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 equivalance relation on the set of integers.(6 marks)
**2 (c) ** Let s= {1, 2, 3, 4} and A=S x S. define the following relation :- R on A : (a,b) R(a', b) if and only if a+b=a'+b.

(i) show that R is an equivalance relation.

(ii) compute A/R.(6 marks)
**2 (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.(4 marks)
**3 (a)** Consider an 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 and onot.(5 marks)
**3 (b)** Let L_{1} and L_{2} be lettices shown below :- Draw the Hasse diagram of L_{1} x L_{2} with product partial order :

(7 marks)
**3 (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.(4 marks)
**3 (d)** How many vertices are necessary to construct a graph with exactly 6 edges in which each vertex is of degree 2.(4 marks)
**4 (a)** Show that is every element in a group is its own inverse, then the group must be abelian.(4 marks)
**4 (b)** If (G, *) is an abelian group, then for all a, b ∈ G, prove that by mathematical induction (a*b)^{n}=a^{n} * b^{n}.(5 marks)
**4 (c) ** If f is a homorphism from a commutative group (S, *) to another group (T, *'), then prove that (T,*') is also commutative.(4 marks)
**4 (d)** Consider the (3,5) group encoding function

e: B^{3} → B^{5} 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 maximum likelyhood decoding function

(i) 11001 (ii)01010 (iii) 00111(7 marks)
**5 (a)** Find the generation function for the following sequence

1, 2, 3, 4, 5, 6,. . .(5 marks)
**5 (b)** Solve the recurence relation a_{r}=3a_{r-1}+2, r≥1 with a_{0}=1 using generation function.(6 marks)
**5 (c) ** Show that the following graphs are isomorphic. :

(5 marks)
**5 (d)** use the laws of logic to show that

[ (p⇒q)¬q]⇒¬p is a tautology.(4 marks)