Discrete Struc Dec 2002

.,

:

JIIIJ

" [DL*:

!l1axi1l1l1l1l

Murks : J 00

=

n! stands for the product 1.2.3 .... 11.

= {(a, b) I a - b is an odd positive integer} ordering relation? An equivalence relation? 20

'

Is R reflexive? Symmetric? Antisymmetric? Transitive? A partial

that R

Let R he a binary relation on the set of all positive integers such

n >= 1 by induction.

10+ 10

1.1! +2.2! + 3.3! + ..... + n.n! (n + 1)1 -I. where

C;) Show that 2" x 2" - I is divisible by .3 for all

:.\ J;

(

(b) Prove by induction that forn >= I

(iii) Show that (A - B) - C = (A - C) - (B - C).

.. ,.JJJI •. ~ LJlJ: ." ..

2.

= A - (B u C). (ii)

Show that (A - B) - C = (A - C) - B.

(i) Show that (A _. B) - C

1. (a) let A, B, C be arbitrary sets.

Unit-I

each unit. All questions carry eql/ollllarks.

Note: Attempt five quesrions in all with at least olle questioll from

Time allowrd : 3 hours

Paper-CSE-20 l-C

D~CRETESTRUCTURES

Examination December-20H2

B. E. (Computer Engg.) BIrd Semester (New Scheme),

478

r

;;J:'<':'"~::'~,~';>-:'''l:~-''7"7· ~_--",~""""",:"-"c:~_,,._

3.

r

o

o

- 2 ar_1

Unit-III

= f (r) where f (r) = 7 r2.

(a) ar - 2 ar_1 = f (r) where f (r) = 7 r (b)lIr

equations:

10+10

Detennine the particular solution for the following difference

(b) a, + ar_1

(a) a, - 7 a'_1 + 10 ar_2

= 3 given that a = 0 and a, = 1 + a'_2 = 0 given that a = 0 and a! == 2. 10+10

Solve the following recurrence relations:

10+10

- .••.• ~:'. ~,..,-o,~..-.-<->+o .~< ,,,.~-,,,,,,,,,,.,,,,,,-.

··:-"'~~·:~7-,"'_.:\"f~_·.-.,...-""':~,,._~_~~~

odd permutations? Give the proof also.

~'~'--'" .•••..•••. ' .• , ..... "'.~- ..•. ~_ .•••• _._,,:"'J .. ,.,.,.~.~

permutation of degree n and how many of them are even and

by even and odd permutati()!1s? How many are the total

6. (a) Deline permutation group and scmigroup. What do you understand

(iii) {-I, I} with multiplication.

(ii) M2 x 2 (R), with matrix multiplicatiun

(R) with matrix addition

(b) Which of the following are groups? GiV<' reasons also: (i) M,.,

of integers modulo 4 under addition

addition"? Find the inverse of each element in Z4' the group

5. (a) What do you understand by "The group of integers modulo under

4.

4.

Unit-II

(a)

(a)

_

= am b m

for three

10+10

Prove that a finite connected graph G is Eulerian if and

Unit-IV

show that G is Abelian.

consecutive integers m for all a, b belongs to G,

(ii) If G is a group such that (ab)m

reverse order.

group G is the product of the inverse taken in the

The inverse of the product of two elements of a

10+10

~.:- .•.. ">tflIl:ro;;...<, ._..,z:l"' ••.. ~~"".~.--

..,.~

".!lI !!I_."'_Il\II!! •• _.II!!I •.••••• "l~ -""'!":·E;~~ •••• '

~:~"l~'I!:[';~, ••••

•• "". ;;-. ,-

vertex u to a vertex v. Show that G has a cycle. 10+ 1 0

(b) Suppose a Graph G contains two distinct paths from a

T: .'0, 33, 44, 22. 77, 35, 60, 40.

inse:ted into an empty binary search tree:

Draw the final tree T if the following numbers are

the resulting graph has exactly one cyde.

(iv) J is cycle--free, but if any edge is added to G then

(;dge e of G.

(iii) G is connected; but G- e is disconnected for any

simple path.

(ii) Each pair of vertices is connected by exactly one

(i) G is a tree.

following are equivalern :

(b) Let G be a graph with more than one vertex. Prove the

only if each vertex has even degree.

478-2.200

8.

7.

(i)

(b) What is an Abelian group? Show that: