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.
0 comments:
Post a Comment
North India Campus