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

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

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.
2) Attempt any Four questions from Section - B.
3) Attempt any Two questions from Section - C.

Section - A

Q1)
a) How many edges are there in a graph with 10 vertices each of degree six?
b) Define the terms (i) Euler circuit (ii) Complete graph.
c) Give an example of a connected graph that has both a Hamilton cycle
and an Euler circuit.
d) What is the chromatic number 'of K2,3?
e) Define an equivalence relation and give an example of the same.
f) Give an example of a finite group?
g) Show that {0} is an ideal in any ring R.
h) Define a quotient ring and give an example for the same.
i) State (i) Absorption law (ii) Idempotent law, in a Boolean algebra.
j) What is the generating function for the sequence Sn = 2n?

Section – B

Q2) In a class of 60 boys, 45 boys play cards and 30 boys play carom. How many boys play both              games? How many plays cards only and how many plays caroms only?

Q3) Solve the recurrence relation S(n) - 65 (n - 1) + 95 (n -2)= 3n+1.

Q4) Let R be the relation on the set of ordered pairs of positive iniegers such that

(a, b)R (c, d) if and only if a + d = \$ + c. Show that R is an equivalence
relation.

Q5) If H and K are two subgroups of a group G, then show that H n K is also a
subgroup of G.

Section - C

Q7) Show that every field is an integral domain.

Q8) Consider any connected plan ar graph G = (V E) having R regions, V vertices
and E edges. Show that V + R - E = 2.

Q9) Use generating functions to solve the recurrence relation ak = ak-1 + 2ak-1 + 2k

with initial conditions a0 = 4 and a1= 12.