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

• Thursday, September 08, 2016
• • ,
• No comments

Roll No.
Total No. of Questions : 09]
B.Tech. (CSE-2011 Batch)/(IT-2011 Batch) (Sem.–3rd)
DISCRETE STRUCTURES
Subject Code : BTCS-302
Paper ID : [A1124]
Time : 3 Hrs.
INSTRUCTIONS 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 have to attempt any FOUR questions.
3. SECTION-C contains THREE questions carrying TEN marks each and
students have to attempt any TWO questions.

SECTION-A

(a) Define an equivalence relation on a set A. Explain with the help of an
example.

(b) Define a partial order on the set N of all natural numbers.

(c) Give an example each of a commutative ring with identity and a field.

(d) Make a table of all Boolean functions of degree 2.

(e) Compute the number of distinct five-card hands that can be dealt
from a deck of 52 cards.

(f) Give an example of a linear homogeneous recurrence relation of degree 2.

(g) Is the set Z of integers with the binary operation of subtraction a semi-group ? Justify your                   answer.

(h) Prove that there exists a semi-group which is not a monoid.

(i) Define a simple path in a graph.

(j) Give en example of a connected graph.

SECTION-B

2. Let A = {a, b, c, d} and B = {1, 2, 3}. Determine whether the relation
R from A to B given by R = {(a, 1), (b, 2), (c, 1), (d, 2)} is a function
3. Show that xy + yz +xz = xy+ yz + xz where x, y, z are Boolean variables.
4. Show that among 100 people there are at least 9 who were born in the
same month.
5. Give an example of a non-abelian group of order 8.
6. Prove that K5– the complete graph on 5 vertices is not planar.

SECTION-C

7. (a) What is the chromatic number of Cn – the cycle with n vertices ?

(b) Prove that an undirected graph has an even number of vertices with
odd degree.

8. Solve the recurrence relation :

an = 6an – 1 – 11an – 2 + 6an – 3 with the initial conditions
a0 = 2, a1 = 5, a2 = 15.

9. (a) What is a hashing function ? Give one example of an application of
hashing functions.

(b) Construct a circuit using inverters, AND gates and OR gates to

produce the output xyz + x y z .