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

Roll No……..

Total No. of Questins:9]

B.Tech. (Sem. – 3^rd )

DISCRETE STRUCTURES

SUBJECT CODE : CS - 203

Paper ID : [A0452]

Time : 03 Hours

Instruction to Candidates:

1) Section - A is Compulsory.

2) Attempt any Four questions from Section - B.

3) Attempt any Two questions from Section - C.

Section - A

QI)

a) What do you mean by chromatic number?

b) Define Euler graph.

c) Define Semi-group.

d) Write down DeMorgan's law for set.

e) Check whether Relation I of divisibility on the set N of positive integers

    is an equivalence relation or not? Justify your answer.

f)Find Chromatic number for bipartite Graph (Kr, r).

g) Postfix expression for the infix expression A+B * (C+D)/F+D * E is....

h) Write down the inclusion and exclusion principle on sets.

i) Define ring with example.

j) Find the multiplication table for G: { l, 2,3,4,5, 6} under multiplication

modulo 7.

Section - B

Q2) What do you mean by cyclic group? Show that any subgroup of a cyclic group is cyclic.

Q3) Solve the recurrence relation, a_n = 3a_n-1 +10a_n-2, n2, given a₀= 1, a₁=-4.

Q4) (a) Using Graph Representation of a relation how we can identify that a Relation is Reflexive, symmetric and anti-symmetric.

(b) Let X: {1, 2,3,4,5,6,7} and R: {(x, y)x -y is divisible by 3} Check whether this equivalence Relation or riot? Give appropriate

reason in support of your answer?

Q5) Give an example of a graph and explain for the following :

(a) A Graph is having Hamiltonian and Euler Circuit.

(b) A Graph is having Hamiltonian Circuit but not an Euler Circuit.

(c) A Graph is having Euler Circuit but not an Hamiltonian Circuit.

Q6) How many integer S between 1 and 300 (inclusive) are

(a) Divisible by at least one of 3, 5,7?

(b) Divisible by 3 and 5, not by 7.

(c) Divisible by 5 but neither by 3 or 7?

Section - C

Q7) Define the following terms with help of example

(a) Ring

(b) Fields.

Q8) Consider the group G : { I, 2, 3, 4, 5) under multiplication modulo 6.

(a) Find the multiplication table of G.

(b) Prove that G is a group.

(c) Find 2-r,3-t and 1-r.

(d) Find the orders and subgroups generated by 2 and 3.

(e) Is G cyclic. Justify  your answer.

Q9)    (a) Let G : (V E) be an undirected graph with k-components and lVl : n,

lEl: m. Prove that m> n - k .

(b) Explain any two applications of Coloring of a Graph.