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

December-2003

CS-203/204

DISCRETE STRUCTURES

B.Tech. 3^rd Semester-2123

Note: Section –A is compulsory. Attempt any four question from section-B.A attempt any two questions from section –C.

Section –A

1.       Answer the following questions.

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.