**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.

## 0 comments:

Post a Comment