Question Paper: Discrete Structures : Question Paper May 2014 - Computer Engineering (Semester 3) | Pune University (PU)

Discrete Structures - May 2014

Computer Engineering (Semester 3)

(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
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)

Please log in to add an answer.