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

Roll No……..

Total No. of Questins:9]

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

DISCRETE STRUCTURES

SUBJECT CODE : CS - 203

Paper ID : [A0452]

Time : 03 Hours

Note: attempt four question from Section –B and two questions from section –C . section –A is mandatory.

1.     Give short answers of the following:

a.     Find the number of permutation in the world ‘MALAYALAM’

b.     Define normal subgroup of a group.

c.      Define f: R→ R as f(x) = x² -7x +9. Find the range of f

d.     Give an example of Eater graph.

e.      Is the set {[1],[2]….,[8]} a group under multiplication (mod 9)?

f.       In any Boolean algebra, show that a = b ↔ ab’ +a, b =0

g.     Define cycle.

h.     What are dihedral group?

i.       Sate inclusion and exclusion principle.   

Section –B

2.     Show that the relation x = y (mod 5) defined on the set of integers I is an equivalence relation.

3.     A cricket team of 11 players is chosen from 16 players including 5 bowlers and 2 wicket kippers. In how many different ways can a team be formed so that the team consists of at least 3 bowlers and at least on wicket keeper?

4.      Prove that the intersection of any two subgroups of a group G is again a subgroup of G.

5.     Prove that the sum of degrees of the vertices of an undirected graph G is twice the number of edges of G.

6.     Describe the application of Boolean algebra in logic circuits and switching functions.

Section –C

7.     

Read More

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

Roll No……..

Total No. of Questins:9]

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

DISCRETE STRUCTURES

SUBJECT CODE : BTCS - 302

Paper ID : [A1124]

Time : 03 Hours

Note: attempt four question from Section –B and two questions from section –C . section –A is mandatory.

1.     Give short answers of the following:

a.     State the principle of inclusion and exclusion principle.

b.     What is meant by ring with unity? Give an example.

c.      Define a field.

e.      What are partial order relations?

f.       What is the minimum number of NAND required to construct an OR gate? Construct it.

g.     Prove that a graph has an even number of vertices of odd degree.

h.     Find the multiplication table for G ={1,2,3,4,5,6} under multiplication modulo 7.

i.       Define semi- group.

j.       What do you mean by chromatic number?

Section –B

2.     If G is a connected simple graph with n vertices, (n> 3) and the degree of each vertex is ablest, then show that G is Hamiltonian.

3.     Prove that the relation x = y mod 3 on the set of integers Z is an equivalence relation

4.     Prove that every field is an integral domain.

5.     In how many way a cricket team of eleven is chosen from a batch of 18 players? How many of them will

a.     Include a particular player

b.     Exclude a particular player

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

Section –C

7.     Solve the recurrence relation a_n+1-5a +6a_n-1 =10, with a₀ =5 and a₁= 10

8.     Explain the term logic gates and Karnaugh map in  Boolean Algebra. Express the Boolean expression E(x,y,z_=3 z(x+y) +y into complete sum of product from.

9.     Write short notes on:

a.     Homomorphism.

b.     Subgroups and cosets   

Read More

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. 

Read More

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

Roll No.

Total No. of Questions : 09]

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

DISCRETE STRUCTURES

Subject Code : BTCS-302

Paper ID : [A1124]

Time : 3 Hrs.

INSTRUCTIONS 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 have to attempt any FOUR questions.

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

students have to attempt any TWO questions.

SECTION-A

l. Answer briefly :

(a) Define an equivalence relation on a set A. Explain with the help of an

example.

(b) Define a partial order on the set N of all natural numbers.

(c) Give an example each of a commutative ring with identity and a field.

(d) Make a table of all Boolean functions of degree 2.

(e) Compute the number of distinct five-card hands that can be dealt

from a deck of 52 cards.

(f) Give an example of a linear homogeneous recurrence relation of degree 2.

(g) Is the set Z of integers with the binary operation of subtraction a semi-group ? Justify your                   answer.

(h) Prove that there exists a semi-group which is not a monoid.

(i) Define a simple path in a graph.

(j) Give en example of a connected graph.

SECTION-B

2. Let A = {a, b, c, d} and B = {1, 2, 3}. Determine whether the relation

R from A to B given by R = {(a, 1), (b, 2), (c, 1), (d, 2)} is a function

or not. Justify your answer.

3. Show that xy + yz +xz = xy+ yz + xz where x, y, z are Boolean variables.

4. Show that among 100 people there are at least 9 who were born in the

same month.

5. Give an example of a non-abelian group of order 8.

6. Prove that K_5– the complete graph on 5 vertices is not planar.

SECTION-C

7. (a) What is the chromatic number of Cn – the cycle with n vertices ?

(b) Prove that an undirected graph has an even number of vertices with

odd degree.

8. Solve the recurrence relation :

a_n = 6a_{n – 1} – 11a_{n – 2} + 6a_{n – 3} with the initial conditions

a₀ = 2, a₁ = 5, a₂ = 15.

9. (a) What is a hashing function ? Give one example of an application of

hashing functions.

(b) Construct a circuit using inverters, AND gates and OR gates to

produce the output xyz + x y z . 

Read More

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

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

l.

 (a) Show that the sum of the degrees of the vertices of a non directed graph is twice the number of            edges in the graph.

(b) Define the terms (i) Regular graph (ii) Complete graph

(c) Give an example of a graph that has neither an Euler circuit nor a Hamiltonian circuit.

(d) Define a tree.

(e) Define an equivalence relation and give an example of the same.

(f) If a^-1 = a  a  G , where G is a group, then show that G is commutative.

(g)  a,b  R where R is a ring, show that (-a).(-b) = a.b

(h) Every field is an integral domain. Give an example to establish that the converse is not true.

(i) In a Boolean algebra B, show that, a + a = a  a B.

(j) What is the generating function for the sequence S_n = baⁿ,n 0 ?

Section -B

2. Among the first 1000 positive integers:

(a) Determine the integers which are neither divisible by 5, nor by 7, nor

by 9.

(b) Determine the integers divisible by 5 but not by 7, not by 9.

3 Solve the recurrence relation S(K) - 4S (K -1 ) + 3 S (K - 2) K², without using the concept of generating functions.

4 Let R be the relation on the set of ordered pairs of positive integers such

that (a,b) R (c,d) if and only if a+d = b+c. Show that R is an equivalence relation.

5. State and prove the Lagrange’s theorem.

6. Consider the Boolean function, f(x,y,z) = (x.y + z).(x’ + y.z’).(x’+ z) Construct the circuit corresponding to the Boolean function of the  Boolean algebra of switching circuits.

SECTION-C

7. Show that every field is an integral domain.

8. Consider any connected planar graph G=(V,E) having R regions,

V vertices and E edges. Show that V+R-E = 2.

9. Find the generating function from the recurrence relation

S(n - 2) = S(n - 1) + S(n) where S(0) = S(l) =1, n  0. 

Read More

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

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

1.       

a.     Define function and relation. Give example of each.

b.     Define semi group and Monoid.

c.      Prove that ⁿ⁺¹C_r =ⁿC_r-1 +ⁿCr

d.     Find ‘n’ if P(n,2)= 72

e.      What is Eulerian graph. Give example.

f.       Define one-one and onto function. Give example.

g.     What is Ring Homomorphism.

h.     Define Permutation. How many permutations are possible on a set S = (1,2,3,4,5).

i.       Find the product of the following permutations

 

j.       Give an example of equivalence relation.

Section –B

2.     State and prove D’Morgan’s law.

3.     Prove that Inclusion relation on the set of sets is and equivalence relation.

4.     Suppose f : G → G’ is a group homomorphism. Prove that f(e)= e’ and f(a^-1) = f(a^)-1

5.     Prove that V-E +R =2, where Vis the number of vertices, E the number of edges and R the number of regions in a graph.

6.     Let A = {1,2,3,4,6,8,9,12,18,24} be ordered by the relation “x” divides “y”. draw Hasse diagram of this relation.

Section –C

7.     Express the output Y as a Boolean expression in the inputs A, B,C  for the logic circuits in the following figure.

8.     A bag contains six white marbles and five red marbles. Find the number of ways four marbles can be drawn from the bag if.

a.     They can be any color.

b.     Two must be white and two red.

9.     Let X = {1,2,---- 8,9}.determine whether or not each of the following is a partition of X.

a.     [{1,3,6},{2,8},{5,7,9}]

b.     [{1,5,7}, {2,4,8,9},{3,5,6}]

Read More

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

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

Q1)

a) How many edges are there in a graph with 10 vertices each of degree six?

b) Define the terms (i) Euler circuit (ii) Complete graph.

c) Give an example of a connected graph that has both a Hamilton cycle

and an Euler circuit.

d) What is the chromatic number 'of K_2,3?

e) Define an equivalence relation and give an example of the same.

f) Give an example of a finite group?

g) Show that {0} is an ideal in any ring R.

h) Define a quotient ring and give an example for the same.

i) State (i) Absorption law (ii) Idempotent law, in a Boolean algebra.

j) What is the generating function for the sequence S_n = 2_n?

Section – B

Q2) In a class of 60 boys, 45 boys play cards and 30 boys play carom. How many boys play both              games? How many plays cards only and how many plays caroms only?

Q3) Solve the recurrence relation S(n) - 65 (n - 1) + 95 (n -2)= 3ⁿ⁺¹.

Q4) Let R be the relation on the set of ordered pairs of positive iniegers such that

(a, b)R (c, d) if and only if a + d = $ + c. Show that R is an equivalence

relation.                   

      

Q5) If H and K are two subgroups of a group G, then show that H n K is also a

subgroup of G.

Section - C

Q7) Show that every field is an integral domain.

Q8) Consider any connected plan ar graph G = (V E) having R regions, V vertices

and E edges. Show that V + R - E = 2.

Q9) Use generating functions to solve the recurrence relation a_k = a_k-1 + 2a_k-1 + 2^k

with initial conditions a₀ = 4 and a₁= 12.

Read More

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

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) Define following terms with examples.

a) Euler graph.

b) Poset.

c) Lattice.

d) Ring.

e) Group.

0 Quotient ring.

g) Integral domain.

h) Semi group.

i) Reflexive relation.

j) Function.

Section - B

Q2) For A: { I ,2,{ 1,3}, ɸ}, determine the following sets.

(a) A-{1} (b) A- ɸ (c) A-{ ɸ } (d) A-{1,2,).

Q3) Write all possible relations from

A: {0} to B: {1,2}

Q4) Give an explicit formula for a function from the set of integers to the set of positive integers i.e.

(a) One to one but not onto.

(b) Onto but not one to one.

(c) One to one and onto.

(d) Neither one to one nor onto.

Q5) In how many ways can 5 Gentle man and 5 ladies be seated round a table so that no two ladies are together.

Q6) Show that following graphs are planar. 

Section - C  

Q7) (a) Suppose 8 people enter a Badminton tournament. Use a rooted tree model of the tournament                determine how many games must he played to determine a champion if a player is eliminated              after one loss.

(b) Prove that the set G: {1, 2,3,4,5,6} is a finite alielian Groups of order 6 with respect to                 multiplication modulo 7.

Q9) (a) Simplify using Boolean postulates and theorems

a +ab + abc + abcd + a + ab + abc + abcd

(b) Discuss various applications of Boolean Algebra'

Read More

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

Roll No……..

Total No. of Questins:9]

May-2007

DISCRETE STRUCTURES

SUBJECT CODE : CS - 203

B.Tech. (Sem. – 3^{rd -} 2057)

Time : 03 Hours

Note : Section –A 9 compulsory. Attempt any Four questions form section –B. Attempt any two questions from Section-C.

Section-A

1.       

a.     Discuss symmetric difference of two sets with examples.

b.     Explain the concept of chain.

c.      Define permutation and combination.

d.     Define domain and range of relation.

e.      Define subgroup.

f.       Differentiate between path and circuits.

g.     What is a ring?

h.     Define Euclidean ring(domain)

i.       Define weighted graph and multigraph with examples.

j.       Define homomorphism of groups.

Section –B

2.     Find the number of subsets of a set S containing n elements .

3.     Prove that intersection fo two normal subgroups in again normal subgroup.

4.     Define composition of relations with example.

5.     Minimize the Boolean expression f = xy⨁ x’y⨁x’y’.

6.     How Boolean Algebra is applicable in 1 ogic Circuits? Explain with the help of suitable example

Section –C

9.     Write short notes on the following:

a.     Hamiltonian Graphs.

b.     Linear recurrence relations.

c.      Sum and product rules.

  

Read More

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

Roll No……..

Total No. of Questins:9]

May-2006

DISCRETE STRUCTURES

SUBJECT CODE : CS - 203

B.Tech. (Sem. – 3^{rd -} 2056)

Time : 03 Hours

Note : Section –A 9 compulsory. Attempt any Four questions form section –B. Attempt any two questions from Section-C.

Section-A

1.      

a.     State Euler’s formula for connected planar graph.

b.     Define chromatic number of a graph.

c.      State Basic counting principles.

d.     How many 4- digit telephone numbers have one or more repeated digits?

e.      Define union and intersection of two sets A &B.

f.       Define Partial order relation.

g.     Define subgroup.

h.     Define Homomorphism of Groups

i.       State De Morgan’s laws in Boolean algebra.

j.       Define Euclidean rind(domain)

Section-B

2.     State and prove Euler’s formula in connected maps.

3.     Solve the recurrence relation a_r- 2_r-1 +a_r-2 =0 given that a_n = 1 and a₁ =2

4.     Prove that intersection of two normal subgroups is again a normal subgroup.

5.     Minimize the Boolean expression f = xy⨁ x’y⨁x’y’.

6.     Prove that every cyclic group is abelian.

Section –C

7.     State and prove Lagrange’s theorem on finite groups.

Read More

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

Roll No……..

Total No. of Questins:9]

May-2003

DISCRETE STRUCTURES

SUBJECT CODE : CS - 203

B.Tech. (Sem. – 3^{rd -} 2053)

Time : 03 Hours

Note : Section –A 9 compulsory. Attempt any Four questions form section –B. Attempt any two questions from Section-C.

Section-A

1.       

a.     If A and B are disjoint sets, prove that: n(AUB) =n(A)+(B)

b.     Show that p↔ q logically imply p→ q.

c.      Define trivial graph

d.     Define  degree in graph.

e.      Define closed path and cycle in a graph.

f.       Define ad abelain group.

g.     Define group Homomorphism.

h.     Define group Isomorphism.

i.        Define normal subgroup of a group.

j.       Differentiate between an ordered and unordered partition of a finite set.

Section –B

2.     Let H be a subgroup of G. define a coset representative system for H in G.

3.     Prove that an undirected graph G possesses an Eulerian circuit if it is connected and all its vertices are of even degree.

4.     Suppose a graph G contains two distinct path from a vertex a to b. show that G has a cycle.

5.     Define the term injective, surjective and bijetive with example.

6.     Find the generating function of the Fibonacci sequence.

Section –C

7.   

Show that D is isomorphic to the complex number C whence D is field.

8.     Suppose a directed graph G has m vertices. Show that if there is a path P from vertex u to v, then there is a path P of length m-1 or less form u to v.

9.     Show that how the set options of  union and intersection defined classes of sets .

Read More