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

Roll No.

Total No. of Questions : 09

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

DISCRETE STRUCTURES

Subject Code : CS-203

Paper ID : [A0452]

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. Answer briefly :

(a) Draw a graph with four vertices with degrees 4, 5, 5 and 2 respectively.

(b) When are two graphs (V1, E1) and (V2, E2) said to be isomorphic ?

(c) Which of the following collections are sets :

(i) the vowels of English Alphabet

(ii) the 5 most beautiful cities of United States.

(d) Let f, g be functions from the set of real numbers to the set of real

numbers-defined by f(x) = 2x + 3 and g(x) = x². Find gof(x) and fog(x).

(e) In how many ways can you deal a king or a black card from a standard deck of cards ?

(f) Define the factorial function f(n) = n!, where f(0) = 1 in a recursive way.

(g) Define Boolean algebra.

(h) A light bulb containing a sensor lights up automatically when there is no sunlight. This              situation is modelled by which gate ?

(i) Define :

(i) the symmetric group S4 on 4 symbols and

(ii) the group of symmetries of a square.

(j) Define an (m, n) encoding function.

SECTION-B

2. Let a be an arbitrary element of a finite group G with identity e. Prove

    that there exists a natural number n such that aⁿ = e.

5. Solve the recurrence relation :

a_n = 3a_{n – 1} – 2a_{n – 2}, n > 2, a₀ = 0, a₁ = 1.

6. Define a congruence relation R on a semigroup (S, *). Explain by giving

an example.

SECTION-C

7. (a) Construct a circuit to produce the output (x + y + z) ( x y z) .

(b) Draw the Hasse diagram of D30 – the partially ordered set consisting of all divisors of 30 with       the partial order of divisibility of natural numbers.

8. Let {a_n} be a sequence defined by the recurrence relation

a_n = 8a_{n – 1} + 10_{n – 1}, a₁ = 9, a₀ = 1. Find an explicit formula for

an using generating functions.

9. Prove that a connected graph has an Euler Circuit if and only if it has no vertex of odd degree.