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

4 (a) Find the shortest distance in the given figure from a to z by using Dijkstra shortest path algorithm. (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)