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

Roll No……..

Total No. of Questins:9]

B.Tech. (Sem. – 3^rd )2014

DISCRETE STRUCTURES

SUBJECT CODE : BTCS - 302

Paper ID : [A1124]

Time : 03 Hours

Note: attempt four question from Section –B and two questions from section –C . section –A is mandatory.

1.     Give short answers of the following:

a.     State the principle of inclusion and exclusion principle.

b.     What is meant by ring with unity? Give an example.

c.      Define a field.

e.      What are partial order relations?

f.       What is the minimum number of NAND required to construct an OR gate? Construct it.

g.     Prove that a graph has an even number of vertices of odd degree.

h.     Find the multiplication table for G ={1,2,3,4,5,6} under multiplication modulo 7.

i.       Define semi- group.

j.       What do you mean by chromatic number?

Section –B

2.     If G is a connected simple graph with n vertices, (n> 3) and the degree of each vertex is ablest, then show that G is Hamiltonian.

3.     Prove that the relation x = y mod 3 on the set of integers Z is an equivalence relation

4.     Prove that every field is an integral domain.

5.     In how many way a cricket team of eleven is chosen from a batch of 18 players? How many of them will

a.     Include a particular player

b.     Exclude a particular player

6.     What do you mean by cyclic group? Show that any subgroup of a cyclic group is cyclic.

Section –C

7.     Solve the recurrence relation a_n+1-5a +6a_n-1 =10, with a₀ =5 and a₁= 10

8.     Explain the term logic gates and Karnaugh map in  Boolean Algebra. Express the Boolean expression E(x,y,z_=3 z(x+y) +y into complete sum of product from.

9.     Write short notes on:

a.     Homomorphism.

b.     Subgroups and cosets