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

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

Roll No……..
Total No. of Questins:9]
B.Tech. (Sem. – 3rd )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 an+1-5a +6an-1 =10, with a0 =5 and a1= 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