 MORE IN Discrete Mathematics
SPPU Computer Engineering (Semester 3)
Discrete Mathematics
May 2017
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

Solve any one question from Q.1(a,b,c,d) & Q.2(a,b,c)
1(a) Explain the concept of countably inifinite set with example.
3 M
1(b) Use mathematical induction to show that, for all n≥1.$$1+2+3+......+n=\frac{n\left ( n+1 \right )}{2}.$$/
3 M
1(c) Let A = {1, 2, 3, 4} consider partition
P = {{1, 2, 3}, {4}}, of A. Find the equivalence relation R on A determined by P.
3 M
1(d) Let A = (1, 2, 3} R is the relation on A whose matrix is: $$M_{R}=\begin{bmatrix} 1 &1 & 1\\ 0 & 0 & 1\\ 0& 0& 1 \end{bmatrix}$$/ show that R is transitive.
3 M

2(a) i) Find DNF of: $\left ( (p\rightarrow q \right )\cap \left ( q\rightarrow p \right )\vee P.$
ii) Find CNF of: $p\leftrightarrow \left (\sim p\vee \sim q \right ).$
3 M
2(b) In the survey of 260 college students, the following data were obtained:
64 had taken a maths course,
94 had taken a cs course,
26 had taken both a maths and a cs course,
14 had taken all types of courses. How many students were surveyed who had taken none of the three types of courses.
3 M
2(c) Let A = Z+ the set of positive integers, and let $$R=\left \{ {\left ( a,b \right )\in A\times A|a\ \text{divides }b} \right \}$$/ Is R symmertric, asymmetric or antisymmetric.
3 M
2(d) Find transitive closure using Warshall algortihm:$M_{R}=\begin{bmatrix} 0 & 1 & 0 & 0\\ 1 &0 & 1 & 0\\ 0 & 0 & 0& 1\\ 0& 0 & 0 & 0 \end{bmatrix}$
3 M

Solve any one question from Q.3(a,b,c,d) &Q.4(a,b,c,d)
3(a) How many words of three distinct letters can be formed from the letters of the word MAST?
3 M
3(b) How many different seven-person committees can be formed each containing three women from an available set of 20 women and four men from an available set of 30 women.
3 M
3(c) Check whether the graph has an Euler circuit, Euler path, justify:
!mage
3 M
3(d) How many coloures required to colour kmgn, why?
(Graph G1) (Graph G2)
3 M

4(a) How many distinguishable words that can be formed from the letters of MISSISSIPPI?
3 M
4(b) Compute the number of distinct five-card hands that can be dealt from a deck of 52 cards.
3 M
4(c) Determine whether the folloiwng graph has a Hamiltonian circuit or Hamiltonian path.
!mage
3 M
4(d) Write 45 applications of graph theory in the field of data analytics.
(Graph G1) (Graph G2)
3 M

Solve any one question from Q.5(a, b) &Q.6(a, b)
5(a) Use labeling procedure to find a maximum flow in the transport network given in the following figure. Determine the corresponding minimum cut.
!mage
7 M
5(b) Explain the following:
1) Difference between binary tree and binary search tree.
2) Rooted tree
3) Cut-sets.
6 M

6(a) Find minimum spanning tree for given graph using Krustkal's algorithm.
!mage
6 M
6(b) Explain the following terms:
i) Application of cutset in computer engineering domain
ii) Prefix code construction using Huffman coding.
iii) Properties of trees.
7 M

Solve any one question from Q.7(a, b, c) &Q.8(a, b, c)
7(a) Prove that: $$\left ( a_b\sqrt{2} ,+,\times \right )$$/ where a, b, ∈ R is integral domain.
6 M
7(b) Explain isomorphism ahnd homomorphism of two semigroups.
3 M
7(c) Prove that every cyclic group is an abelian group.
4 M

8(a) Let G b set of all non-zero real numbers and let: $$a*b=\frac{ab}{2},$$/ show that (G, *) is an abelian group.
6 M
8(b) Explain Galois theory.
3 M
8(c) Explain properties of binary operations.
4 M

More question papers from Discrete Mathematics