Question Paper: Discrete Mathematics Question Paper - Dec 18 - Computer Engineering (Semester 3) - Pune University (PU)
0

## Discrete Mathematics - Dec 18

### Computer Engineering (Semester 3)

Total marks: 80
Total time: 3 Hours
INSTRUCTIONS
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Draw neat diagrams wherever necessary.

1.a. ) By using mathematical induction show that : 1 + 2 + 3 + ........ + n = n(n + 1)/2 for all natural number values of n.
(4 marks) 00

1.b. Use : p : I will study discrete structure q : I will go to a movie r : I am in a good mood. Write the English sentence that corresponds to each of the following : (i) ~ r $\rightarrow$ q (ii) ~ q $\wedge$ p (iii) q $\rightarrow$ ? ~ p (iv) ~ p $\rightarrow$ ~ r.
(2 marks) 00

1.c. Let R = {(1, 4), (2, 1), (2, 5), (2, 4), (4, 3), (5, 3), (3, 2)} on the set A = {1, 2, 3, 4, 5}. Use Warshall’s algorithm to find transitive closure of R.
(6 marks) 00

Or

2.a. 100 sportsmen were asked whether they play cricket, football or hockey. Out of these 45 play cricket, 21 play football, 38 play hockey, 18 play cricket and hockey, 9 play cricket and football, 4 play football and hockey and 23 play none of these. Find the number of sportsmen who play : (i) exactly one of the games (ii) exactly two of the games.
(6 marks) 00

2.b. A = {1, 2, 3, 4}, B = {1, 4, 6, 8, 9}; aRb iff b = $a^{2}$. Find the domain, range of R. Also find its relation matrix and draw its diagraph.
(6 marks) 00

3.a. From a group of 7 men and 6 women, five persons are to be selected to form a committee so that at least 3 men are are there on the committee. In how may ways can it be done?
(3 marks) 00

3.b. How many 4-letter words with or without meaning, can be formed out of the letters of the word ‘LOGARITHMS’, if repetition of letters is not allowed ?
(3 marks) 00

3.c. Determine whether the two graphs are isomorphic or not. Explain.
(6 marks) 00

Or

4.a. Use Dijkstra’s algorithm to find the shortest path between A and Z in figure :
(6 marks) 00

4.b. If a committee has eight members : (i) How many ways can the committee members be seated in a row ? (ii) How many ways can the committee select a president, vice-president and secretary ?
(6 marks) 00

5.a. Find maximum flow in the transport network using labeling procedure. Determine the corresponding min cut :
(7 marks) 00

5.b. Define the following terms : (i) Level and height of a tree (ii) Cut points (iii) Eccentricity of a vertex.
(6 marks) 00

Or

6.a. Find minimum spanning tree for the graph shown below using Kruskal’s algorithm.
(7 marks) 00

6.b. Suppose data items A, B, C, D, E, F, G occur in the following frequencies respectively 10, 30, 5, 15, 20, 15, 5. Construct a Huffman code for the data. What is the minimum weighted path length ?
(6 marks) 00

7.a. Let Zn = {0, 1, 2, ..........., n – 1}. In Z12 what is the order of 3, 6 and 8.
(3 marks) 00

7.b. Let (Q, *) is an Algebraic system. * is a binary operation defined as $a^{*}+b_{0}=a+b-a b \quad \forall a, b \in$ Q. Determine whether (Q, *) is a group.
(4 marks) 00

7.c. Define : (i) Rings (ii) Integral domain (iii) Field.
(6 marks) 00

Or

8.a. Let Zn = {0, 1, 2, ........., n – 1}. Let * be a binary operation such that a * b = remainder of (a + b) divided by n. Construct a table for n = 4. Is (Z4, *) a monoid, semigroup, group and abelian group
(7 marks) 00

8.b. Define : (i) Group code (ii) Galois theory (iii) Cyclic group.
(6 marks) 00