Discrete Structures - Dec 2013

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 8ⁿ 3ⁿ is multiple of 5, for n ≥ 1.(4 marks) 1 (b) What is multiset? Explain its significance with at least two examples.(2 marks) 1 (c) Find the transitive closure by using Warshall's algorithm A = {1,2,3,4,5,6} and R = {(x,y) | |xy| = 2}.(6 marks) 2 (a) Salad is made with combination of one or more eatables, how many different salads can be prepared from onion, carrot, cabbage, and cucumber?(2 marks) 2 (b) It is known that in university 60% of professors play tennis, 50% of them play bridge, 70% jog, 20% play tennis and bridge, 40% play bridge and jog and 30% play tennis and jog. If someone claimed that 20% professors jog and play tennis and bridge, would you believe his claim? Why?(4 marks) 2 (c) Show that the set of all divisors of 70 forms a lattice.(6 marks)

Answer any one question from Q3 and Q4

3 (a) Define the following terms with suitable example:
Group.
Monoid.
Isomorphism.(6 marks) 3 (b) List and explain the necessary & sufficient conditions for Hamiltonian and Eulerian path with suitable examples.(6 marks) 4 (a) Define the following terms with suitable example:
Ring.
Integral domain.
Field(6 marks) 4 (b) Find the shortest path between a-z for the graph given in figure 1 using Dijkstra's algorithm. (6 marks)

Answer any one question from Q5 and Q6

5 (a) Define the following terms with reference to tree:
Rooted tree.
Optimal Binary tree.
Height of the tree(6 marks) 5 (b) Find minimum spanning tree for graph given in figure 2 using Kruskal's algorithm. (7 marks) 6 (a) Define the following terms with reference to the tree
Binary Search Tree.
M-ary Tree.
Tree Traversal.(6 marks) 6 (b) Find the Maximum flow of the given Transport network in figure 3. (7 marks)

Answer any one question from Q7 and Q8

7 (a) In a college 25% students failed in Maths, 15% student failed in Physics and 10% students failed in both Maths and Physics. A student is selected randomly then what is the probability that
i) If he failed in Physics, he also failed in Maths.
ii) He failed in maths or Physics.(6 marks) 7 (b) A problem on probability is given to four students A,B,C,D. The probability of solving that problem are 1/2, 3/4, 1/4 and 2/5 respectively. What is the probability that
i) The problem will be solved.
ii) Exactly one of them will solve the problem.(7 marks) 8 (a) Find the number of arrangements that can be made out of the letters:
i) ASSASSINATION.
ii) MISSISSIPPI(6 marks) 8 (b) Two cards are drawn at random from an ordinary deck of 52 cards. Find the probability that
i) Both are spades.
ii) One is spade and one is heart(7 marks)