Search Your Paper

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

• 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
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 K3,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-1H 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

ak + 3ak-1 – 4ak-2 = 0, k > 2 with initial conditions a0 = 3 and a1 = -2 and find the sequence which satisfies it.