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

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

l.

 (a) Show that the sum of the degrees of the vertices of a non directed graph is twice the number of            edges in the graph.

(b) Define the terms (i) Regular graph (ii) Complete graph

(c) Give an example of a graph that has neither an Euler circuit nor a Hamiltonian circuit.

(d) Define a tree.

(e) Define an equivalence relation and give an example of the same.

(f) If a^-1 = a  a  G , where G is a group, then show that G is commutative.

(g)  a,b  R where R is a ring, show that (-a).(-b) = a.b

(h) Every field is an integral domain. Give an example to establish that the converse is not true.

(i) In a Boolean algebra B, show that, a + a = a  a B.

(j) What is the generating function for the sequence S_n = baⁿ,n 0 ?

Section -B

2. Among the first 1000 positive integers:

(a) Determine the integers which are neither divisible by 5, nor by 7, nor

by 9.

(b) Determine the integers divisible by 5 but not by 7, not by 9.

3 Solve the recurrence relation S(K) - 4S (K -1 ) + 3 S (K - 2) K², without using the concept of generating functions.

4 Let R be the relation on the set of ordered pairs of positive integers such

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

5. State and prove the Lagrange’s theorem.

6. Consider the Boolean function, f(x,y,z) = (x.y + z).(x’ + y.z’).(x’+ z) Construct the circuit corresponding to the Boolean function of the  Boolean algebra of switching circuits.

SECTION-C

7. Show that every field is an integral domain.

8. Consider any connected planar graph G=(V,E) having R regions,

V vertices and E edges. Show that V+R-E = 2.

9. Find the generating function from the recurrence relation

S(n - 2) = S(n - 1) + S(n) where S(0) = S(l) =1, n  0.