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.

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 ).\]

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,

58 had taken a business course,

28 had taken both a maths and a business course,

26 had taken both a maths and a cs course,

22 had taken both a cs and a business course,

14 had taken all types of courses. How many students were surveyed who had taken none of the three types of courses.

64 had taken a maths course,

94 had taken a cs course,

58 had taken a business course,

28 had taken both a maths and a business course,

26 had taken both a maths and a cs course,

22 had taken both a cs and a business 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

!mage

3 M

3(d)
How many coloures required to colour k

(Graph G

_{mgn,}why?(Graph G

_{1}) (Graph G_{2})
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

!mage

3 M

4(d)
Write 4

(Graph G

^{5}applications of graph theory in the field of data analytics.(Graph G

_{1}) (Graph G_{2})
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

!mage

7 M

5(b)
Explain the following:

1) Difference between binary tree and binary search tree.

2) Rooted tree

3) Cut-sets.

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

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

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