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

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

December-2003
CS-203/204
DISCRETE STRUCTURES
B.Tech. 3rd Semester-2123
Note: Section –A is compulsory. Attempt any four question from section-B.A attempt any two questions from section –C.
Section –A
a.     If A = {1,2,4,5}, B {a,b,c,f} and C= {a,5} are three given sets Compute (A C), (AC)x B.
b.     Construct truth table for the following formula: ~ (pv ~q) (p→  q)
c.      Define the following concepts giving one example of each;
i.      Onto function.
ii.      An symmetric relation.
iii.      Union of two sets.
iv.      Partial order relation.
d.     Define the following concepts from graph theory with an example for each.
i.      Spanning sub graph  of a graph
ii.      Isomorphic graphs.
iii.      A full regular binary tree.
iv.      Hamiltonian path in a graph
e.      Define :
i.      Monoid
ii.      Group
iii.      Ring
iv.      Boolean algebra
v.      Permutation.
vi.      Equivalence relation.
Section –B

2.     Using either Breath first search Algorithm or Dijkstra’s algorithm, find the shortest path from s to t in the following weigted path
3.     Given an example of a relation which is:
a.     Neither reflexive nor ineflecixve
b.     Both symmetric and ant symmetric.
c.      Both reflective and symmetric.
d.      Both reflexive symmetric and transitive.
e.      Both symmetric and transitive but not reflective.
4.     Prove that every subgroup  of a cyclic group is cyclic.
5.     Prove that for any commutative monoid(M,*). The set of idempotent elements of  M from a subononoid
6.     Discuss various applications of Boolean algebra in logic in logic circuits.

Section –C
7.
a.     How many 4- digit telephone numbers have one or more repeated digits?
b.     Prove that an undirected graph has an Euler path if and only if and only if is connected and has 2 vertices of odd degree. Give example.
8.     State various postulates of Boolean Algebra. State and prove at least five theorems of Boolean Algebra.
9.
a.     What is a planar graph? Prove that V-E+R=2
b.     What is a chromatic number?

c.      State and prove Eulerian theorem graph to show that Konigsberg’s graph is not proved as a solution.