Discrete Structures Question Paper of 3rd Semester CSE74 Download Previous Years Question Paper 11

• Thursday, September 08, 2016

Roll No……..
Total No. of Questins:9]
B.Tech. (Sem. – 3rd )
DISCRETE STRUCTURES
SUBJECT CODE : CS - 203
Paper ID : [A0452]
Time : 03 Hours
Instruction to Candidates:
1. SECTION-A is COMPULSORY consisting of TEN questions carrying
TWO marks each.
2. SECTION-B contains FIVE questions carrying FIVE marks each and
students has to attempt any FOUR questions.
3. SECTION-C contains THREE questions carrying TEN marks each and
students has to attempt any TWO questions.

SECTION-A

l. Write short notes on :

(a) Define an equivalence relation on a set A.
(b) Let f : R → R and g : R → R be defined as f(x) = sin x, g(x) = x2.
Find fog and gof.
(c) Prove that among any 13 people, there are at least 2 of them who
were born in the same month.
(d) How many committees of four persons with a given chairman can be
selected from 10 persons ?
(e) Define a monoid.
(f) Prove that the intersection of two subgroups of a group G is also a
subgroup of G.
(g) Prove that a field F cannot have zero divisors.
(h) Draw logic circuit for ab’ + a’b.
(i) Prove that in any graph, the number of vertices of odd degree can’t be odd.
(j) Find the chromatic number of the complete graph Kn  on n vertices.

SECTION-B

2. Construct a graph that has six vertices and five edges but is not a tree.

3. Prove that the set An of all even permutations in Sn is a normal subgroup.

6. Prove that every ideal A of a ring R is a kernel of some ring metamorphism.

SECTION-C

7. (a) Does the graph shown below has a Hamiltonian circuit ?

(b) Find the generating function of the sequence 1, 2, 3, 4, ... .

8. (a) Find the minimum distance of the encoding function e : B2→ B3 defined by  e(b1, b2) = (b1, b2, b1+ b2)

(b) Prove that in a graph having a vertex of odd degree, there is no Euler circuit.

9.  (a) Prove that any two cyclic groups of the same order are isomorphic.

(b) State and prove the fundamental theorem of isomorphic for groups.