Biju Patnaik University of Technology 2008-5th Sem B.Tech (B Tech), discrete mathematics structure . - Question Paper
BPUT(B Tech), fifth semester discrete mathematics structure ques. paper.
 |
TTI |
| L Total number of printed pages -7 B, Tech BSCM3301 Fifth Semester Examination - 2008 DISCRETE MATHEMATICAL STRUCTURES Full Marks 70 Time: 3 Hours Answer Question No 1 which is compulsory anti any Hve from the rest IWL The figures m the.right-hand margin indicate marts. 1 Answer ttie following questions : 2 xtO (i) Express the following system specification using predicate, quantifier and logical connectives. "At least one mail message, among tht,e non-empty sel of messages, can be saved if thereis a disk with more than 10 kilobytes of free space." (0 Define a covntaWe wt Grve art example of a countable so! (Hi) DrUw the Ha&se diagram of the partial ottSef rotation 'greater than equaS to" on the *et (11, 2, X < 5) (iv) In how many ways three job* can be assigned To five employees if each employee cambo grvenmore Ihan one job ? M How many positive integers less than 1000 exist which are drristbtoby 5 but net* by 7 ? (vtj What is the transitive closure of the relabon R-{ (a, b), <b# aMc. tJ). (d,c)j ? fvii) Let S s |1, 2, 3, 4, 5. 6), The collection of sets A =(1 t t 3} B '={4, 5J and C= '(6) forms a partition of the set S. Find the r-d equivalence relation, on S corresponding to this partition. (viii) Define chromatsc number. What is the chromatic number corresponding to a pofygon of to sides ? (f*) The order of a group is prime. Can you tind a subgroup other than the trivial subgroups ? Justify. it) Find the inverse of each element, if exist, of ihe lattice D. where a s b if a divides b and D * represents ihe se\ of all divisors Of 30 t IWL 2. (a) Verify that the following program segment is correct with reseed to the initial asser-non y = 3 and the final assertion z = 6 x = 2 z : = x +y if y > 0 then,. 2:sz+1 else z : = o 5 (t>) Using mathematical imJuCtigo ahow ihai lor any positrva integer n, 3 + 3.5 + 3 57 + 3 5 3 + *3,5'r 3(5"'*- T |/4 S 3. (a) Find The number ot ways in v/htch 25 itfenticaf GOOfees be distributed among lour children so tha< each child go*s ai toa& three but no mcXG than seven cootos 5 (b) Use generating functron to solve ttio rocurrenca relation am * 3a 1 * 4* ' with the initial condition a0 - 1 5 4, (a) Using Marshall's algorithm find the transitive closure ot the relation whose matrix representation is given below 5 10 0 0 1 10 10 10 0 1, 0 0 1 Oj 8SCM 3301 4 Contd. (b) Define closure of a refatton wiih respect to a properly P. Suppose that the relation R on the flmte set A its represented by the matax Show that the matrix lhat represents the reflexive closure of R is Mr Vt 5 5 {a) Prove that a connected muttigraph has an Euiet path but not an Euler circuit if and only if ill has exactly two vertices of odd degree. 5 IWL (b) Show tKal a simple graph G is bipartite if only if it has no circuit with odd number of edges, 5 6. (a) Show that a simple graph that has a circuit with odd number of vertices in it can nol be colored using two colors. 5 (b) Suppose 1000 people enter a chess tournament. Use a rooted tree model of the tournament to determine how many games must be played to determine a champion; it a player is eliminated after one loss and games are played until one entrant has not lost 5 7* (a) Let (A,*) be a semigroup and e be a left identity* Furthermore, for every x in A there exist y in A such that y * x = e,Ihen (t) show that for every a, b, c in A, if a * b = a * c then b = c (ii) show that {a, *) is a group by showing that e is an identity element, 5 (b) Let (H ,") be a subgroup ot (G ,*). Let e G, xHx-1 = H}. Then show that (N ,*) is a subgroup of (G 5 8. (a) Let E(xv xl x3) = (x,y x2)v(xi ax3) be a boolean expression over twovalued boolean algebra. Write E(x,, xpi x3) both in disjunctive and conjunctive normal forms. 5 (b) For any a and b in a lattice, show that (i) av(a/\b)=a (ii) aA(av b)-a 
-C BSCM 3301 7
You are here:
PAPER
 Biju Patnaik University of Technology 2008-5th Sem B.Tech (B Tech), discrete mathematics structure . - Question Paper
|