Discrete Struc Dec 1999

Total No. of Questions : B J

[ Total No. of Printed Pages : 2

478/99 B. E. (Third Semester) EXAMINATION, Dee., 1999 (New ScheDJc)

(Computer Eug.)

DISCRETE STRUCTUREs (CSE-ZOI-C) Tune: Three Hours J

[ Maximum Marla : 100 [ Kmimum Pass Marla : 40

Note : Attempt any fiVt! questions. 1. What is a relation ? Discuss different types of relations, giving suitable examples. Determine whether the relation of division . on the set N of positive integerS is equivalcnc:e relation or not ? 20 2.(a) Fmd the pOwer set p (A) of A = {l, 2. 3, 4, 5}.

4

t.

(b) Let g, h . be functions from N to N, where N is the set of Dalural numbers so :

fen) =n + 1 g(n) hi)

= 2n

_{a n is

even}

\n - 1 n is odd

Determine fo/. hog, (fog)oh, hot

1 6 P. 1: Q.

[ 2 ] 3.

What do you understand by generating function ? Find the soll!tion of or = 7'3', r ~ 0 by method of generating function. 20

4. _ The total solution of the recurrence J.:elation Co or + clor _ 1-+

c7flr _

2 = f (r) is 3' + 4' + 20. Given that f

(r)

== 6 for all r,

determine Co> ci and c2' 20 5. Frod all the spanning trees of graph G, and frod which is the minimal spanning tree of G. Also describe the algorithm used to frod minimal spanning tree.

Ar 6FT

B

2ili !1

B 6.(a) (b)

20

cF

Define and 4raw Hamiltonian path and circuit:

1

Supposcpreorder and inorder are given: ~M~U:G

B Q A C K F P D E R H IDordu : Q B KeF A G P E D H R Draw the diagram of tree.

0

7. Define and give examples of the following :

2 1 0

(a) Monoid (b) Group (e) RiDg (d) Automorphisin

0

8. ,(a) Let (A, .) be a semigroup. Show that fOr a, b, C in A, if Q • C = C • a and b • c =

C•b then 10 (a.b).c=c.(a.). 10 (b) Let (A, .) be a semigroup.

Show that if A is finite set, there exists Q in A such that a • Q

478199

=

D.

10

800