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

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

l. Answer briefly :

(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

or not. Justify your answer.

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 K_5– 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 :

a_n = 6a_{n – 1} – 11a_{n – 2} + 6a_{n – 3} with the initial conditions

a₀ = 2, a₁ = 5, a₂ = 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 .