Question Paper: Discrete Structures : Question Paper Dec 2013 - Computer Engineering (Semester 3) | Mumbai University (MU)
0

## 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 ab=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
an=5an-1 + 6an-2 + 7n
(5 marks)
2 (a) Prove by mathematical induction xn - yn 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 f1 : 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 L1 and L2 be lettices shown below :- Draw the Hasse diagram of L1 x L2 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 (ab)n=an * bn.(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: B3 → B5 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 ar=3ar-1+2, r≥1 with a0=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)