MORE IN Discrete Structures
RGPV Computer Science (Semester 3)
Discrete Structures
December 2015
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

1(a) If A={1,4},B={4,5},C={5,7}, determine
i) (A×B)∪(A×C)
ii) (A×B)∩(A×C)
2 M
1(b) Let A={2,3,4} and B+{3,4,5,6,7}. Assume a relation R from A to B such that (x,y)∈ R when a divides 6.Determine R, its domain and range.
2 M
1(c) Briefly explain the application of Pigeon hole principle using an example.
2 M
Solve any one question from Q.1(d) & Q.1(e)
1(d) Show by mathematical induction:
$1^{2}+3^{2}+5^{2}+\cdots+(2n-1)^{2}=\frac{n(2n+1)(2n-1)}{3}$
7 M
1(e) Let f:R→R be defined by
$f(x)=\left\{ \begin{matrix} 2x+1, x \le 0 \\ x^2+1, x>0 \end{matrix} \right.$
Let g:R→R be defined by
$g(x)=\left\{\begin{matrix} 3x-7,x\le0\\x^3,x>0 \end{matrix}\right.$
then find the composition gof
7 M

2(a) Define semi group. Write its properties.
2 M
2(b) Write short note: i) Mono-id ii) Normal subgroup
2 M
2(c) Prove that every subgroup of a cyclic group G is cyclic
2 M
Solve any one question from Q.2(d) & Q.2(e)
2(d) Prove that the set G={0,1,2,3,4,5} is a finite abelian group of order 6 with respect to addition module 6.
7 M
2(e) Let(R,+,X)be a ring. The operation ⨂is defined by a ⨂b=a×b +b×a.Show that (R,+,X) is a commutative ring.
7 M

3(a) Prove by truth table that the following is tautology-
(P↔q^r)⇒(~r→~p)
2 M
3(b) Obtain the principal disjunctive normal form of the following formula:~(p∨q)↔(p^q)
2 M
3(c) Investigate the validity of the following argument.

2 M
Solve any one question from Q.3(d) & Q.3(e)
3(d) Design DFA and NDFA accepting all strings over {0,1}, which end in 0 but do not contain 11 as substring.
7 M
3(e) Prove the validity of the following argument;
"if Ram is selected in IAS examination, then he will not be able to go to London. Since Ram is going to London, he will not be selected in IAS examination".
7 M

4(a) Prove that, in a graph total number of odd degree vertices is given but then number of even degree vertices may be odd.
2 M
4(b) Distinguish between K-coloring of a graph and chromatic number of a graph.
2 M
4(c) Define Euler and Hamiltonian graph with example.
2 M
Solve any one question from Q.4(d) & Q.4(e)
4(d) Find minimum distance between two vertices K and L of graph, using /Dijkstra's algorithm.

7 M
4(e) State Euler's formula for a planar graph. Give an example of a planar graph with 5 vertices and 5 regions and verify Euler's formula for your example.
7 M

5(a) Let L={1,2,3,4,5} be the lattice shown below, Find all sub ,lattices with three or more elements.

2 M
5(b) Write down the binomial theorem.
2 M
5(c) Draw hasse diagram for the "less than or equal to" relation on set A={0,2,5,10,11,15}
2 M
Solve any one question from Q.5(d) & Q.5(e)
5(d) Determine the particular solution of the recurrence relation latex
7 M
5(e) Explain briefly:-
i)Posets ii) Permutation iii)combination iv) Total solutions
7 M

More question papers from Discrete Structures