## Discrete Structures - May 2014

### Computer Engineering (Semester 3)

TOTAL MARKS: 100

TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.

(2) Attempt any **four** from the remaining questions.

(3) Assume data wherever required.

(4) Figures to the right indicate full marks.

### Answer any one question from Q1 and Q2

**1 (a)** With the help of mathematical induction prove that, $$ 1^2 + 3^2 + 5^2 + (2n -1)^2 = \dfrac {n(2n-1)(2n+1)}{3} $$(4 marks)
**1 (b)** Over the universe of book defined propositions

B(x): x has blue cover

M(x): x is maths book

I(x): x published in India

Translate the following i)$\ \forall x (M(x)\wedge I(x) \rightarrow B(x)) $ ii) There are maths books published outside India.(2 marks)
**1 (c)** Let x={1,2,........,7} and R={(x,y)|x-y is divisible by 3}. Show that R is equivalence relation. Draw graph of R.(6 marks)
**2 (a)** Prove the following using Venn diagram $ A\cap (B\oplus C)=(A\cap B)\oplus (A\cap C) $(2 marks)
**2 (b)** Among the integers 1 to 1000

i) How many of them are not divisible by 3 nor by 5 nor by 7.

ii) How many are not divisible by 5 or 7 but divisible by 3.(4 marks)
**2 (c)** Let x = {2,3, 6, 12, 24, 36} x ≤ y if x divides y

Find

1. Maximal element

2. Minimal element

3. Chain

4. Antichain

5. Is poset lattice ?(6 marks)

### Answer any one question from Q3 and Q4

**3 (a)** Define the following

1. Group

2. Ring

3. Field(6 marks)
**3 (b)** Show that the following graphs are isomorphic

(6 marks)

**4 (a)**Find the shortest distance in the given figure from a to z by using Dijkstra shortest path algorithm. (6 marks)

**4 (b)**Prove that the set Z of all integers with binary operation * defined by a * b = a + b + 1such that ∀a,b∈? Z is an abelian group.(6 marks)

### Answer any one question from Q5 and Q6

**5 (a)** For the following set of weights, construct optimal binary prefix code. For each weight in the set, give the corresponding code words. 10,30,05,15, 20,15, 05.(7 marks)
**5 (b)** Find the minimum spanning tree of the given figure using Kruskal's algorithm
(6 marks)
**6 (a)** Define the following terms with reference to tree with example

i. Level and height of a tree

ii M-ary tree

iii Eccentricity of a vertex(6 marks)
**6 (b)** Find the maximum flow of the transport network given in the figure.
(7 marks)

### Answer any one question from Q7 and Q8

**7 (a)** A husband and wife appear in an interview for two vacancies in the same post. The probability of husband's selection is 1/7 and that of wife's selection is 1/5. what is the probability that

1. both of them will be selected

2. only one of them will be selected

3. none of them will be selected(7 marks)
**7 (b)** How many numbers of 7 digits can be formed with the digits 0,2,2,5,6,6,6 . How many of them are even ?(6 marks)
**8 (a)** A committee of 5 people is to be formed from a group of 4 men and 7 women. How many possible committees can be formed if at least 3 women are on the committee?(6 marks)
**8 (b)** A box contains 6 red, 4 white and 5 black balls. A person draws 4 balls from the box at random. Find the probability that among the balls drawn there is at least one ball of each colour.(7 marks)