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

Roll No……….

B.Tech. (CSE/IT) (Sem.–3rd)

DISCRETE STRUCTURES

Subject Code : BTCS-302 (2011 Batch)

Paper ID : [A1124]

Time : 3 Hrs.

INSTRUCTION TO CANDIDATES :

1. SECTION-A is COMPULSORY consisting of TEN questions carrying

TWO marks each.

2. SECTION-B contains FIVE questions carrying FIVE marks each and

    students has to attempt any FOUR questions.

3. SECTION-C contains THREE questions carrying TEN marks each and

students has to attempt any TWO questions.

SECTION-A

l. Write short notes on :

(a) Define an equivalence relation on a set.

(b) Give an example of a partial order relation on the set 1 of

integers.

(c) Prove that the intersection of any two left ideals of a ring is also a

left ideal of the ring.

(d) Give an example of a Boolean Algebra.

(e) Find the number of different messages that can be represented by

sequences by 4 dots and 6 dashes.

(f) What is the minimum number of people with the same last initials in

a group of 85 people.

(g) Define a semigroup and a monoid.

(i) Define a simple graph and a complete graph.

(j) Find the chromatic number of the complete bipartite graph K3, 4.

SECTION-B

2. Let H : K → L be a hash function where L consists of two digit

addresses 00, 01, 02, ..., 49. Find H (12304) using :

(i) Division method and

(ii) Folding method.

3. Let G be a finite group and H be a subgroup of G. Prove that order of H divides the order of G.

4. List any five properties of a graph which are invariant under graph isomorphism.

5. Let T : R → S be a ring homomorphism. Define Ker (T), the kernel of T. Prove that Ker(T) is a two sided ideal of R.

6. Find the minimum number of persons selected so that at least eight of them will have birthdays on the same day of the week.

SECTION-C

7. Design a three-input-minimal AND-OR circuit with the following truth table :

T = {A, B, C ; L} = {00001111, 00110011, 01010101, 11001101}.

8. Solve the recurrence relation :

a_n – 4a_{n – 1} = 6.4ⁿ , a₀= 1.

9. Prove that it is not possible be supply three utilities to three places by conduits without crossing over.