Biju Patnaik University of Technology 2007 B.Tech Information Technology SEMESTAR - Question Paper

DiscRETE MATHEMATICAL STRUCTURES

Total number of printed pages - 7 B.Tech

BSCM 3301

Fifth Semester Examination - 2007 DISCRETE MATHEMATICAL STRUCTURES

   . Full Marks - 70

V..C    

X.

Time: 3 Hours

   Answer Question No. 1 which is compulsory

IWL    and any five from the rest.

The figures in the right-hand margin indicate marks,

1. Answer the following questions : 2x10 (i) Define scope of a quantifier and give an example.

<i,i) What is Euclidian algorithm to find the GCD of two integers ?

P.T.O-

(iii) What is lex icographic orde ring on N X 'N , where N is the set of natural numbers ?

. (iv) Give a recursive definition of the set of all positive integers congruent to 2 modulo 3.

(v)    How many positive integers less than 1000 exit which are divisible by 7 but not by 11 ?

(vi)    What is symmetric closure of the relation R = {(a, b ) | a > b } ?

(vii)    What are the principles of drawing Hasse diagram of a partial ordering relation ?

(viii)    Define chromatic number of a simple graph

and that of a planar graph.

. (in) It ({a, bj, *) be a semigroup where a' a = b then can you say that b * b = b ? Justify your answer.

{*} Let a, b are two elements of a lattice (A, <), Show that a a b = b iff a v b = a.

a) Show that the hypotheses (p a q) v r and, r -* s imply the' inclusion p v s.    5

i

b) Using mathematical induction show that n3 - n is divisible by 3 whenever n is a positive integer,    5

3, (a) Using Warshall's algorithm find the transitive closure of the relation whose matrix BSCM 3301    3    p-m

poset ? Show that there ts exactly one greatest element of a poset* if such an element exits. What about maxima) element 7

(b) Let R be a relation on the set of ordered pairs of positive integers such that ((a, b), (c, d)) e H if and only if ad be Show that R is an equivalence relation, 5 I v< a) Show that the relation set inclusion* on the power set of S is a partial ordering relation. Draw the Hasse diagram of the relation where S =fa , b, c}.    5 ib) How do you differentiate between the maximal element and greatest element of a

>5. a) Solve the following recursive relation ar = ar-1 - af_2, given that a, = l and a? = 0 5 (b) Use generating function to find the number of ways to select r objects of n different Kinds if we must select at least one object of each kind.    5 6. a) Define a tree. Show that an undirected graph is a tree if and only if there is an unique simple path between any two of its 5 vertices. c    p.TO. BSCM 3301    5

---

(bi Show thal a eocwwcied my ttgrapfi w<rh at two vortx&inas an Euorru i f and <yvy if oae#> of wrnes has oven <Jegr- *7 a) Lei (A, *j be A monoid such That for avery x A. x " x = e, whre* e is llVf tdervMy element Show thal fA, "j is an abelian where Kf. afKi at are non-negative rrtegefs less than six    5 fb\\ Find the total1 number ot strings of 10 ternary dtgits< (0. 1 or 2) wtuch contain exactly two Os. three 1 s and ttve 2s. 5

---

v<b) Lei fA, s) be a distributive lattice if a a x = a a y and a v * - a v y^!for some a, then show that x = y.    5

a) Explain the pnncipJe ol inclusion- exclusion. Using this principle, find out the number of solutions for the equations. + x_ + x = 13_t

i    f    J

BSCM 3301    6    Contd.

JSCM 3301

Attachment: biju-patnaik-university-of-technology-2007-b-tech-information-technology-36266-1.pdf

Earning:   Approval pending.