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.

**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.

**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.

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.

**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.

**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.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.c.**Determine whether the two graphs are isomorphic or not. Explain.

Or

**4.a.**Use Dijkstra’s algorithm to find the shortest path between A and Z in figure :

**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 ?

**5.a.**Find maximum flow in the transport network using labeling procedure. Determine the corresponding min cut :

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

Or

**6.a.**Find minimum spanning tree for the graph shown below using Kruskal’s algorithm.

**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 ?

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

**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.

**7.c.**Define : (i) Rings (ii) Integral domain (iii) Field.

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

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