PNROLLMENT NO, | melt re eye a pale XAMINATION APRIL 2023 ee B.Tech. IV Sem. (AICTE)|CSE/T/A1&DS| a Discrete Structure Subject Code: MAdOI Paper Code: BAISFOI Time: Three Hours No, of Pages: 02 Tastructions: 01 Attempt any one question from each module. 02 All question carry equal marks. Module-1 QI (@) Let 1 bea binary relation on the set ofall integers such Re 2 a0 + yes Bhs = {(@,b):(@ ~ b) is an even integer} Is a an equivalence relation? @) and 7. ww OR Q2 (a) For any three set A, B.C prove that Ax (B—C)=(A xB) -(AxC) ene Determine the number of integer between | to 250 that are aon a of the integers 2, 3, 5 ey Maximum Marks: 70 Minimum Marks: 22 coe! oO a cs iy {col} {col} (©) Show thatthe function f:2 -» Z defined by f(x) =x? + x, forall x € z, is amany one function, [cor Modute-tt Q3 (a) Define a lattice, distributive lattice. For any a and b in A, prove that [co2} av (ab) =aandaA(avb)=a (®) Show that a lattice is distributive if: [coz] (@Ab) Vv (bAc)V(CAa@) = (av b)ACVC)A(CVa) . OR . Q.4 (a) Show that {co2) ~ (pAq) = (~ pV (~ pva))e (~ pv) (b) Prove that {co2) CeD)IGS)> 087) is a tautology Module-II Q5 (a) Show that {coz} mye ree coeur) rea By mathematical induction. : (b) Determine the generating function of the numeric function a,, where [co2} 2, ifriseven oi {or , ifrisodd OR : 2.6 (a) Determine the particular solution for the difference equation, [co2 a, ~ 3a, + 20,2 = 2" (co2] (b) Solve the recurrence relation: dp ~ 5a; + 60-2 = 1(7 1), for r= 2 aModule-1V Q7 (a) Show that the intersection of two normal subgroup of a group is a normal subgroup. [603] (b) Detine field and show that the set of ceal number of the forma + hy3. where a and b are rational number, is a field with respect to addition and multiplication. {C03} OR Q.8 (a) Let H be a subgroup of a, prove that () H =Haif and only ifa eH (ii) Ha = Hb if and only if ab" EH (b) IER is aring, then for all a, b, c € R, show that: Rah * Module-V Q.9 (a) Write short note on. [co4] (_Tsomorphic graph (ii) Hamiltonian graph (iil) Binary tree (iv) Connected graph (®) Prove that the complement of a spanning tree does not contain a cut set and that the complement of a cut set does not contain a spanning tree. [co4] oR, Q.10 (a) Determine a minimum spanning tree for the graph shown below: (c04] (b) Write and explain an algorithm to find the shortest path from a specified vertex to another specified vertex of a graph. [CO4] 05603 BASE} S20? . eo bE oa Sas a = a s foes Sore Ly we) ' .ENROLLMENT NO, EXAMINATION APRIL 2024 B.Tech, LY Sem. (AICTE), [CSE, IT, ALS DS Discrete Structure Subject Code: MA4OL Paper Code: BAKSROI Time: Three Hours Maximum Marks: 70 No. of Rages: 02 Minimum Marks: 22 Tustruction ae resenbt one question from each module, Each question carries e ual an . Ei vi marks. 02. Assume Suitable data if missing/required. 2 “ : oN aaa Module I ag e QU (@) IFF:X ¥ in one-one onto, then Prove that f~":¥ —+ X is also one-oge 08 onto. {COL} (b) If 4,8, C.D are any four sets then prove: & (COR Weak 3 nB)xCnbd)=(Axc)n(BxD) 3.562? 02%; 0) OR a ws Q2 (a) Prove that among 10,000 people there are two who were bom at ex@Yfy the same time (hour, minute, second). (coy ©) TER is an equivalence relation in a set 4, then prove that R-1 is an equivalence relation in the set A. [col Module I Q3 (a) Prove that the following statement is logically equivalent: [co1) @ > @)Vvr=(pvr) (vr) (b) Define Hasse diagram. If A = {1,2,3,4,6,8,9,12,18,24) be ordered by the relation * divides 6” then draw the Hasse diagram of A. Icoly OR Q4 (a) Show that the following statement is tautology. (col) @AQV @A~ QV (~PAQ)V ~ pA~ Q). (b) IfX be a collection of sets closed under intersection and union. Then prove that (X,0,U) isa a {c Module D1 err i 2 is i ipl 6 25 @) Write the principle of mathematical induction and prove that n(n? + 5) is an integer aera - for all positive integers n, ©) Solve the recurrence telation a, + 6a,-1 + 9ar—2 = 3, given that ag = 0 anda, =1. {CO2] | | OR a = 2 2 usil rating function. UA) Solve the recurrence relation a, — 70,1 + 10dy-2 = 0, form > 2 using generating [c02) Cont... Re= - oo (h) Wate the generating function for the sequences (a = + 2)0 +13 Module 1V Q7 (a) Define cosets of a group with example. Consider a multiplicative group cG=(y alia: show that every left coset is equal tothe corresponding right coset , isa subgroup of G (CO3| (6) Prove that the intersection of two subgroups of a group G, is a subgroup of G [C03] oR Q8 (a) Prove thata non empty subset H of group G isa subgroup of G iff. » ~ 71603] i2- ; (i) a€H, bEH > abeEH c Be i UES @) aeHaate Ae sre bare sapaleut, ii is . pad, GOKAIPUN 4473" Where a” is the inverse of a in G. Pern Road OOk9 331997 (b) Define normal subgroups of a group G. Prove that a subgh3@PH°Ota group G, is normal eee H, WxeG ‘Module V 9 (a) Wright an algorithm for shortest path in weighted graph and use it to find shortest path from a toz in the following graph, where numbers associated with the edges are the weights [co4] (b) Define the following [co4] (@_Isomorphism and Homomorphism of graphs i) Graph coloring and chromatic number. , OR Q.10(a) Define Hamiltonian graph and Hamiltonian path wit i lton path with exampl en draw it vee contigs Hanitonian cat utsat anus aie sen 8 Pw (®) 1fG is aconnected graph then n —e + + = 2 where n d i e numberof edges and denotes the number of regions in an umbet of vertices, ¢ “(cou at ns BAKaroIR}NROLL MENT NO. ee ee | ABER 2024 TT, AT&DS} (AICTE) IV Sem. [CS Diserete Structure Subject Code: MA4OI Paper Code: BAL4FOL Time: Three Hours Maximum Marks: 70 No. of Pages: 02 Minimum Marks: 22 Instructions: OL. Attempt one question from each module. 02. All questions carry equal marks. Module 1 QU (@) Prove that @ A-(BNC)=(4-B)U(A-c) (i) AX (BC) = (axa) - (axe) () Debs Partial order relation and prove that the relation G defined on power set P(A) is partial order relation OR Q2 (a) Let R bean binary relation on the set of all integers such that R= {(ab) : a-b is aneven integer.) Prove that R is an equivalence Relation. (b) Show that the function f: R---->R_ defined by f(x) = 2x is one one and onto Module II Q3 (a) Show that the following proposition is tautologies (Aq) V (PA~q) V(~ pAQ) V(~ PA~a) (b) Write short notes on following: (i) Ordered set, | (ii) Isomorphic ordered set oR Q4 (a) Define Lattice. Let X beacollection of sets closed under intersection and union , then prove that (X, U,n jis a lattice. (6) Show that (p ~A q)V~r is equivalentto pV ~ (qAr) Module III > (@) Define Mathematical Induction . Use it to prove 416+ +n nine 2 Cont(by Solve the recurrence relation yer tyner | yu bh’ tht L OR (26 (a) Apply the generating himetion method to solve the following near difference equation Module IV Q7 (a) Define subgroup and prove that intersection of two subgroup is subgroup. (b) Let (R, +) be the additive group of all real numbers and (R’ , .) be the multiplicative group ‘number then show that the following mapping f is an isomorphism £R——>R’ defined by fer eV x ER OR Q8 (@) Define Normal subgroup and prove that A subgroup H of G is normal ifand only if xHxt VxeG pe er sic Copy (b) Write short notes on: Raj Phote eae eiisentonr doea at Sein Papers (ii) Monoid groups Fes. NOES (ii) Abelian group ‘ Doge aee Main Road. Guna ee rop Module Y Mob.-9424394652 Q9 (@) Define degree af vertex in a graph. Prove th wat, In any graph the number of vertices of odd d is always even. ‘() Find the shortest path form vertex A to Z in the following: Q10(a) Define the following with an example: (Graph (ii) Selfloop (iii) Regular graph (iv) Simple graph. () Show that the maximum number of edgesin a simple graph with n verticesis 2&2