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 from Q.1(a,b,c) & Q.2(a,b,c)
1(a) Use Mathematical induction to show that: $\frac{1}{1.2}+\frac{1}{2.3}+\frac{1}{3.4}+.....+\frac{1}{n\left ( n+1 \right )}=\frac{n}{n+1}$
4 M
1(b) Cosider the following:
p: This system is good.
q: This system is chep. Write each of the following sentences in symbolic form:
i) This system is good and cheap.
ii) This system is not good but chep.
iii) This is neither good nor cheap.
iv) This system is good or cheap.
4 M
1(c) Let A = {a, b, c, d}, π = {{a, b}, {c}, {d}}. Find the equivalence relation induced by π and construct its diagraph.
4 M

2(a) Let i) A - ϕ
ii) {ϕ}-A
iii) A∪P (A)
iii) A∩ P (A) where P is a power set.
4 M
2(b) Find the transitive closure of R by Warshall's algorithm, where a {1, 2, 3, 4, 5, 6} and R = {(X, Y)| | X-Y| = 2}.
4 M
2(c) Among 100 students, 32 study Mathematics, 20 study Physics, 45 study Biology, 15 study Mathematics and Biology, 7 study Mathematics and Physics, 10 study Physics and Biology, 30 do not study of the three subjects:
i)n Find the number of students studying all the three subjects
ii) Find the number of students studying exactly one of the three subjects.
4 M

Solve any one question from Q.3(a,b,c) & Q.4(a,b,c)
3(a) Define:
i) Ring
ii) Ring Homomorphism
iii) Ring Isomorphism
iv) Integral domain
v) Semi-Group.
5 M
3(b) Show that if a, b are arbirtary elements of group A, then:
(ab2=a2b2 if and only if G is abelian.
4 M
3(c) Draw a complete bipartite graph on 2 and 4n vertices K2,4 and 2 and 3 vertices K2, 3.
3 M

4(a) Find the shortest path between the vertices a to z in the graph given below by using Dijkstra's algorithm.
!mage
6 M
4(b) With reference to the graph theory define the following terms:
i) Regular Graph
ii) Acylic Graph
iii) Multi Graph.
3 M
4(c) Consider the group (Z, +). Let H = (3n : n∈z). Show that H is a subgroup of z.s.
3 M

Solve any one question from Q.5(a,b) & Q.6(a,b)
5(a) Find the maximum flow in the transport network using labeling procedure. Determine the corresponding minimum cut.
!mage
8 M
5(b) Define binary tree traversal and find recorder, postorder and inorder traversals for the following binary tree.
!mage.
5 M

6(a) Define Spanning Multigraph and Acyclic Graph. Use Krushal's Algorithm to find minmum spaning tree for the graph as shown in figure.
!mage
8 M
6(b) Construct the labeled tree of the following algebraic expression: A + B * C + D * E
5 M

Solve any one question from Q.7(a,b) & Q.8(a,b)
7(a) Suppose license plate contains 3 English letters followed by 4 digits:
i) How many different license plates can be manufactured if repetition of letters of letters and digits are allowed?
ii) How many plates are possible if only the letters are repeated?
iii) How many plates if only the digits are repeated?
7 M
7(b) Mohan has three shares in a lottery in which there are 3 prizes and 6 blanks. Rohan has one share in a lottery in which there is 1 prize and 2 blanks. Show that Mohan's chance of winning a prize of Rohan's chance is the ratio 16:7.
6 M

8(a) In how many ways can seven men and women sit down at a round table in such a way that no two men sit next to each other?
7 M
8(b) A bag contains 3 red and 5 black balls and a second bag contains 6 red and 4 black balls. A ball is drawn from each bag. Find the probability that:
i) both are red
ii) both are black
iii) 1 is red and 1 is black.
6 M

More question papers from Discrete Mathematics