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
r
ilB(p
Fifth Semester Examination - 2007 DISCRETE MATHEMATICAL STRUCTURES
. Full Marks - 70
V..C
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
1 0 1'
0 1 o
1 1 0
(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 = 13t
- C
i f J
BSCM 3301 6 Contd.
JSCM 3301
Attachment: |
Earning: Approval pending. |