MORE IN Discrete Mathematics
SPPU Computer Engineering (Semester 3)
Discrete Mathematics
December 2016
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 fromQ.1(a,b,c) and Q.2(a,b,c)
1(a) Prove by mathematical induction: $$\frac{1}{1.3}+\frac{1}{3.5}+\frac{1}{\left ( 2n-1 \right )\left ( 2n+1 \right )}=\frac{n}{2n+1}\text{for}\ n\geq 1.$$/
3 M
1(b) Define the following with examples:
i) Uncountable infintite set
ii) Countable infinte set.
3 M
1(c) If
R = {(a, b), (b, a), (b, c), (c, d), (d, a)} be a relation on the set A = {a, b, c, d}. Find the transitive closer of R using Warshall's agorithm.
6 M

2(a) Let
A = (a, b, c, d} and B = {1, 2,3}. Determine whether the relation R from A to B is a function. Justify. If it is function give the range:
i) R = [(a, 1), (b, 2), (c, 1), (d, 2)]
ii) R = [(a, 1), (b, 2), (a, 2), (c, 1), (d, 2) ].
4 M
2(b) The following is the Hasse diagram of the poset:
{(a, b, c, d, e), <}.
Is it a lattice? Justify.
!mage
2 M
2(c) In a class of 80 students, 50 students know English, 55 know French and 46 know German language, 37 students know English and French, 28 students know French and German, 25 know English and German, 7 students know none of the languages. Find out: i) How many students know all the 3 languages?
ii) How many students know exactly 2 languages?
iii) How many students know only one language?
6 M

Solve any one question fromQ.3(a,b,c) and Q.4(a,b)
3(a) A bag contains 6 red and 8 green balls.
i) If one ball is drawn at random, then what is the probability of the ball being green?
ii) If two balls are drawn at random, then what is the probability that one is red and the other is green?
6 M
3(b) Determine which of the graphs below represents Eulerian circuit, Eulerian path, Hamiltonian circuit and Hamiltonian path. Justify your answer.
!mage
4 M
3(c) Define the graph Kn and Kmn.
2 M

4(a) In how many ways can 6 men and 5 women be seated in a line so that no two women st together? In how many ways can 6 men and 5 women sit in a line so that women occupy the eve places.
6 M
4(b) Use Dijkstra's algorithm to find the shortest path between a and z.
!mage
6 M

Solve any one question fromQ.5(a,b,c) and Q.6(a,b,c)
5(a) Find maximum flow in the transport network using labeling procedure. Determine the corresponding min cut.
!mge
7 M
5(b) Define:
i) Forest
ii) Height of a tree
iii) Ordered tree
iv) Properties of tree.
4 M
5(c) State whether the given code is prefix code. Justify:
{000, 001, 01, 10, 11}.
2 M

6(a) Give the stepwise construction of minimum spanning tree using Prim's algorithm for the following graph. Obtain the total cost of minimum spanning tree.
!mage
6 M
6(b) Explain fundamental system of cutsets with suitable examples.
4 M
6(c) Explain binary tree, binary search tree and ordered tree with suitable examples.
3 M

Solve any one question fromQ.7(a,b,c) and Q.8(a,b,c)
7(a) Consider the binary relation * defined on the set:
A = {a, b, c, d} by the following table . Fill the empty cell.
 * e a b c e e a b c a a b c e b c
2 M
7(b) Prove that: $$\left (( a+b\sqrt{2} \right ), +, *)$$/ when the a, b ∈R is integral domain.
6 M
7(c) Define Normal Subgroup and rings with example.
5 M

8(a) Let
R= {0°, 60°, 120°, 180°, 240°, 300°} and * is a binary operation so that a and b in R, a * b is overall angular rotation corresponding to successive rotations by a and then b. Show that (R, *) is a group.
6 M
8(b) Let A = {0, 1}. Is A closed under:
i) Multiplication