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

• Thursday, September 08, 2016
• • ,
• No comments

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

(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) = x2. 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 an = e.

5. Solve the recurrence relation :
an = 3an – 1 – 2an – 2, n > 2, a0 = 0, a1 = 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 {an} be a sequence defined by the recurrence relation

an = 8an – 1 + 10n – 1, a1 = 9, a0 = 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.