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

Roll No……..

Total No. of Questins:9]

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

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 K_2,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 S_n = 2_n?

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)= 3ⁿ⁺¹.

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 a_k = a_k-1 + 2a_k-1 + 2^k

with initial conditions a₀ = 4 and a₁= 12.