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

Roll No……..

Total No. of Questins:9]

B. Tech. (CSE) (IT)(Sem.-3rd)

DISCRETE STRUCTURES

Subject Code: BTCS-302

Paper ID: A124

Time : 03 Hours

Note: Attempt al questions in these Sections. Section –A (10x2=20)

Q.1.

(a) What is the power set of the set {0, 1, 2}.

(b) Let A = (a, b ,c, d), B = (x, y, z).

Find (a) A×B (B) B×A

(c) Define an ideal in a ring R. Give an example of an ideal in the ring of integers.

(d) Find the values, if any, of the Boolean variable x that satisfy the equation

+ = 0. (e) How many positive integers between 10 and 99 inclusive are divisible by7?

(f) What is the generating function for the sequence 1, 1, 1, ...

(g) Prove that the set of integers under the binary operation of addition is a group.

(h) Give an example of a semi group without an identify element.

(i) How many connected components are there in a discrete graph on n vertices?

(j) Define a Hamiltonian circuit a graph. Give an example of a graph with a  Hamiltonian                          circuit.

Section –B

Note: Attempt any Four questions from this section.

 Q2. Prove that he relation ‘congruence modulo’ is an equivalence relation on the set of integers. Find         the equivalence classes of this relation.

Q3. Construct a circuit hat produces the output ( + ) X

Q4. How many elements are there in A1 UA2, UA3 if each Ai has 10 element s (i =1, 2, 3), each pair A_i, A_j has 50 common elements and 25 elements are

common in al the three sets.

Q5. Prove that in a finit group G, the order of any element divides the order of G

Q6. Let G be a connected planar simple graph with e edges and v vertices

where v≥3, then prove that e ≤ 3V-6 5

Section –C

Note: Attempt any two questions from this section

Q7. A) Define a total ordering on the set (1, 2, 3, 5, 10, 12) Compatible with the partial order of                       divisibility.

b) Give an example of a relation from a set A to a set B which is not a function.

Q8. Find an explicit formula for the Fibonacci numbers defined by

             f_n = f_n-1+f_n-2 ,f₀ = , = 1.

Q9. A) Prove that A_n – the set of al even permutations on n symbols is a normal sub group of S_n - the             set of al permutations on n symbols.

b) Give an example of a non-commutative ring.