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

• Thursday, September 08, 2016

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 Ai, Aj 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
fn = fn-1+fn-2 ,f0 = , = 1.

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

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