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

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

a)

How many different paths are there between vertices a and h in the above graph? How many of these paths have length 5?

 b) Define the term, “Complement of a graph” and give an example.

 c) Give an example of a graph which is non-planar.

 d) What is the chromatic number of K_3,3?

 e) Define a partial order relation and give an example.

 f) In any group G, prove that, (ab)^-1 = b^-1 a^-1 for all a, b  G.

 g) Define the term, “an integral domain” and give an example.

 h) Define an ideal of a ring and give an example.

i) Write the dual of each of the following Boolean equations:

i) (x + 0) (1.x) = 1,                   ii) x + x′y = x + y

 j) What is the generating function for the sequence: 0, 0, 0, 6, -6, 6, -6,

6, -6, 6…?

Section - B

Q2) In a group of 50 people, 35 speak Hindi, 25 speak both English and Hindi and all the people speak at least one of the two languages. How many people speak only English and not Hindi? How many people speak English?

Q3) Solve the recurrence relation S(n) – 9s(n – 1) + 8S (n – 2) = 9n + 1.

Q4) Define a relation R defined on Z, the set of all integers as a R b if and only

if 7 divides a – b for all a, b ∈Z, Show that R is an equivalence relation.

Q5) Show that a non – empty subset H of a group G is a subgroup of the group G if and only if, ab^-1∈ H  a, b H.

Q6) In any Boolean algebra B, prove that,

 ( a′ ∨ b′) ∨ (a ∧ b ∧ c′) = (b ∧  c′) ∨ (a′ ∨ b′).

Section - C

Q7) Show that every field is an integral domain.

Q8) State and prove the Euler’s theorem on graphs.

Q9) Use generating functions to solve the recurrence relation

 a_k + 3a_k-1 – 4a_k-2 = 0, k > 2 with initial conditions a₀ = 3 and a₁ = -2 and find the sequence which satisfies it.