## 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^{n} 3^{n} 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)