CramX Logo
RegisterLog in
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Document preview page 1

Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 1

Document preview content for Solution Manual for Discrete Mathematics (Classic Version), 5th Edition

Solution Manual for Discrete Mathematics (Classic Version), 5th Edition

Make studying easier with Solution Manual for Discrete Mathematics (Classic Version), 5th Edition, designed for clear and structured learning.

Elizabeth Chen
Contributor
4.9
86
over 1 year ago
Preview (31 of 135 Pages)
100%
Log in to unlock
Page 1 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 1 preview imageDISCRETEMATHEMATICSFIFTHEDITIONJohn A. DosseyIllinois State UniversityAlbert D. OttoIllinois State UniversityLawrence E. SpenceIllinois State UniversityCharles Vanden EyndenIllinois State UniversityINSTRUCTOR’SSOLUTIONSMANUAL
Page 2 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 2 preview image
Page 3 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 3 preview imageContents1An Introduction to Combinatorial Problems and Techniques11.1The Time to Complete a Project . . . . . . . . . . . . . . . . . . . . . . . . .11.2A Matching Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41.3A Knapsack Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41.4Algorithms and Their Efficiency. . . . . . . . . . . . . . . . . . . . . . . . .4Supplementary Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . .52Sets, Relations, and Functions62.1Set Operations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62.2Equivalence Relations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.3Partial Ordering Relations. . . . . . . . . . . . . . . . . . . . . . . . . . . .82.4Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .102.5Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .112.6Applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11Supplementary Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . .123Coding Theory143.1Congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .143.2The Euclidean Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . .153.3The RSA Method. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .173.4Error-Detecting and Error-Correcting Codes. . . . . . . . . . . . . . . . . .173.5Matrix Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .183.6Matrix Codes That Correct All Single-Digit Errors . . . . . . . . . . . . . . .19Supplementary Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . .20iii
Page 4 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 4 preview imageTable of Contents4Graphs224.1Graphs and Their Representations . . . . . . . . . . . . . . . . . . . . . . . .224.2Paths and Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .244.3Shortest Paths and Distance. . . . . . . . . . . . . . . . . . . . . . . . . . .274.4Coloring a Graph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .284.5Directed Graphs and Multigraphs. . . . . . . . . . . . . . . . . . . . . . . .30Supplementary Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . .345Trees365.1Properties of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .365.2Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .385.3Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .405.4Rooted Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .425.5Binary Trees and Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . .465.6Optimal Binary Trees and Binary Search Trees . . . . . . . . . . . . . . . . .51Supplementary Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . .606Matching636.1Systems of Distinct Representatives. . . . . . . . . . . . . . . . . . . . . . .636.2Matchings in Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .636.3A Matching Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .666.4Applications of the Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . .666.5The Hungarian Method. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .67Supplementary Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . .677Network Flows687.1Flows and Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .687.2A Flow Augmentation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . .707.3The Max-Flow Min-Cut Theorem. . . . . . . . . . . . . . . . . . . . . . . .737.4Flows and Matchings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .74Supplementary Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . .75iv
Page 5 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 5 preview imageTable of Contents8Counting Techniques788.1Pascal’s Triangle and the Binomial Theorem. . . . . . . . . . . . . . . . . .788.2Three Fundamental Principles. . . . . . . . . . . . . . . . . . . . . . . . . .788.3Permutations and Combinations. . . . . . . . . . . . . . . . . . . . . . . . .798.4Arrangements and Selections with Repetitions. . . . . . . . . . . . . . . . .798.5Probability. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .808.6The Principle of Inclusion-Exclusion . . . . . . . . . . . . . . . . . . . . . . .818.7Generating Permutations andr-Combinations. . . . . . . . . . . . . . . . .82Supplementary Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . .829Recurrence Relations and Generating Functions849.1Recurrence Relations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .849.2The Method of Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .889.3Linear Difference Equations with Constant Coefficients. . . . . . . . . . . .919.4∗Analyzing the Efficiency of Algorithms with Recurrence Relations. . . . . .949.5Counting with Generating Functions . . . . . . . . . . . . . . . . . . . . . . .999.6The Algebra of Generating Functions. . . . . . . . . . . . . . . . . . . . . . 100Supplementary Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10210Combinatorial Circuits and Finite State Machines10510.1Logical Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10510.2Creating Combinatorial Circuits. . . . . . . . . . . . . . . . . . . . . . . . . 10710.3Karnaugh Maps. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10910.4Finite State Machines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111Supplementary Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115v
Page 6 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 6 preview imageTable of ContentsAppendices120A An Introduction to Logic and Proof120A.1Statements and Connectives. . . . . . . . . . . . . . . . . . . . . . . . . . . 120A.2Logical Equivalence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121A.3Methods of Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125Supplementary Exercises. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127B Matrices130vi
Page 7 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 7 preview imageChapter1An Introduction toCombinatorial Problemsand Techniques1.1THE TIME TO COMPLETE A PROJECT2.31; A-B-E-G4.39; A-C-G-H6.16; B-D-F-H8.27; A-D-E-H10.27; A-B-D-G1
Page 8 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 8 preview imageChapter1An Introduction to Combinatorial Problems and Techniques12.29; C-F-I14.33; H-I-F-G16.31; D-E-I18.20 minutes2
Page 9 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 9 preview image1.2A Matching Problem1.2A MATCHING PROBLEM2.7204.2106.848.168010.19,958,40012.1814.504016.12618.21020.11922.132024.504026.24028.12001.3A KNAPSACK PROBLEM2.T4.F6.F8.F10.T12.T14.T16.no18.yes; 3220.∅,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}; 1622.12824.102426.25628.2630.{1,4,6,7,8,9,10,11,12}1.4ALGORITHMS AND THEIR EFFICIENCY2.yes; 04.no6.no8.−1, 9, 84; 3, 17, 8410.−4,−4, 41, 95; 2, 11, 33, 9512.11100014.0010103
Page 10 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 10 preview imageChapter1An Introduction to Combinatorial Problems and Techniques16.kja1a2a3311121111111011118.kja1a2a3a441110111120.The circled numbers in the table below indicated the items being compared.22.The circled numbers in the table below indicated the items being compared.24.6.5 years, 2.7 seconds26.2.3×1010years, 12.5 seconds4
Page 11 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 11 preview imageChapter 1Supplementary Exercises28.4n−330.3n−232.−4,−4, 41, 95SUPPLEMENTARY EXERCISES2.20; B-E-F-H4.3366.408.1404010.T12.F14.T16.T18.1620.no22.yes; 024.−5, 7, 7, 8826.∅,{4},{3},{3,4},{2},{2,4},{2,3},{2,3,4},{1},{1,4},{1,3},{1,3,4},{1,2},{1,2,4},{1,2,3},{1,2,3,4}28.4.92×108years30.432.4r−35
Page 12 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 12 preview imageChapter2Sets, Relations, andFunctions2.1SET OPERATIONS2.A∪B={1,2,4,5,6,7,9},A∩B={1,4,6,9},A−B=∅,A={2,3,5,7,8}, andB={3,8}4.A∪B={2,3,4,5,6,7,8,9},A∩B={7,9},A−B={3,4,6,8},A={1,2,5}, andB={1,3,4,6,8}6.{(3, 1), (3, 2), (3, 3), (4, 1), (4, 2), (4, 3), (5, 1), (5, 2), (5, 3)}8.{(p, a),(p, c),(p, e),(q, a),(q, c),(q, e),(r, a),(r, c),(r, e),(s, a),(s, c),(s, e)}10.12.ABABC14.A={1, 2},B={1, 3}, andC={1}16.A={1, 2},B={1, 3}, andC={1}6
Page 13 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 13 preview image2.2Equivalence Relations18.A20.∅22.A∩B24.A∪B26.The equalityA−B=B−Aholds if and only ifA=B.28.The equalityA∩B=Aholds if and only ifA⊆B.2.2EQUIVALENCE RELATIONS2.reflexive and symmetric4.reflexive, symmetric, and transitive6.reflexive and symmetric8.none10.reflexive and symmetric12.reflexive and transitive14.The equivalence class ofRcontaining ABCD consists of the string ABC and thestrings of 4 letters having A as their first letter and C as their third letter. There are262= 676 distinct equivalence classes ofR.16.The equivalence class ofRcontaining{1, 2, 3}is the set containing the followingfour elements ofS:{1, 3},{1, 2, 3},{1, 2, 3, 4}, and{1, 3, 4}. There are 8 differentequivalence classes ofR, namely the sets consisting of the elementsS,S∪ {2},S∪ {4},andS∪ {2,4}for everyS⊆ {1,3,5}.18.The equivalence class ofRcontaining (5,8) is the set{(x1, x2) : eachxiis an integer andx1−x2= 5−8}.There are infinitely many distinct equivalence classes ofR, namely, the sets of theform{(x1, x2) : eachxiis an integer andx1−x2=k},wherek= 0,±1,±2,±3, . . ..20.{(1,1),(1,3),(1,6),(3,1),(3,3),(3,6),(6,1),(6,3),(6,6),(2,2),(2,5),(5,2),(5,5),(4,4)}24.The equivalence classes have the formE1×E2, whereEiis an equivalence class ofRi.28.There are 5 partitions of a set with three elements.32.LetSbe a nonempty set andRan equivalence relation onS. Then there is a functionfwith domainSsuch thats1R s2if and only iff(s1) =f(s2).7
Page 14 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 14 preview imageChapter2Sets, Relations, and Functions2.3PARTIAL ORDERING RELATIONS2.not antisymmetric4.partial ordering6.not antisymmetric8.not antisymmetric10.134212.{1, 2, 3, 4}{3, 4}{1, 2}{1, 3}{1, 4}{2, 3}{2, 4}14.R={(a, a),(b, b),(b, a),(c, c),(c, b),(c, a),(d, d),(d, a)}16.R={(1,1),(2,2),(2,1),(2,4),(4,4),(8,8),(8,4)}18.The maximal elements are{1},{2}, and{3}; the only minimal element is{1, 2, 3}.20.The only minimal element is 0; there are no maximal elements.22.One possible sequence is 1, 3, 2, 4.24.One possible sequence is 1, 3, 2, 6, 4, 12.26.LetSdenote the set of residents of Illinois andRbe defined so thatx R ymeans thatxis a sister ofy.28.Every prime integer is a minimal element; there are no maximal elements.30.(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4)8
Page 15 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 15 preview image2.3Partial Ordering Relations32.(9, 4)(9, 2)(8, 4)(8, 2)(7, 4)(7, 2)(9, 6)(9, 3)(8, 6)(8, 3)(7, 6)(7, 3)36.(a)Suppose thatyis element ofSsuch thatx R yis false. If there is no elementy1inSsuch thaty1R y, thenyis a minimal element ofS, contradicting thatxis the unique minimal element ofS. Thus there must be such an elementy1. Ifthere is no elementy2inSsuch thaty2R y1, theny1is a minimal element ofS,another contradiction. So there must be such an elementy2. BecauseSis finite,continuing in this manner must produce a minimal elementykofSdifferent fromx. Becausexis the unique minimal element ofS, the assumption that there isan elementyofSsuch thatx R yis false must be incorrect. Thusx R sis truefor everys∈S.(b)LetZdenote the set of integers andS=Z∪ {∅}. LetRbe the relation definedonSbyx R yif and only if one of the following holds: (i)x, y∈Zandx≤y, or(ii)x=y=∅. Then∅is the unique minimal element inS, but∅R zis falsefor everyz∈Z.40.2n42.2n·3n(n−1)/29
Page 16 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 16 preview imageChapter2Sets, Relations, and Functions2.4FUNCTIONS2.not a function with domainX4.a function with domainX6.a function with domainX8.a function with domainX10.a function with domainX12.not a function with domainX14.416.1318.820.722.−124.626.−228.1030.0.7832.6.6434.3.2236.−2.5638.gf(x) =g(f(x)) =√x2+ 1 andf g(x) =f(g(x)) =x+ 140.gf(x) =13xandf g(x) = 3x42.gf(x) = 5(2x)−22xandf g(x) = 25x−x244.gf(x) = 4x−12−xandf g(x) = 3x−23−x46.one-to-one and onto48.neither one-to-one nor onto50.one-to-one but not onto52.onto but not one-to-one54.f−1(x) =x+ 2356.f−1(x) does not exist.58.f−1(x) does not exist.60.f−1(x) =3√x+ 162.ForY={x∈X:x= 0}, we haveg−1(x) =−1x.64.Ifn < m, there are no one-to-one functions; and ifm≤n, there areP(n, m) =n(n−1)(n−2)· · ·(n−m+ 1)one-to-one functions.68.LetX={1},Y={2,3}, andZ= 4. Definef:X→Ybyf(x) = 2 for allx∈Xandg:Y→Zbyg(y) = 4 for ally∈Y.10
Page 17 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 17 preview image2.5Mathematical Induction2.5MATHEMATICAL INDUCTION2.7, 9, 13, 21, 37, 694.xn={xifn= 1x·xn−1ifn≥26.Letxndenote thenth odd positive integer. Thenxn={1ifn= 1xn−1+ 2ifn≥2.8.Ifk= 1, the sets{x1, x2, . . . , xk}and{x2, x3, . . . , xk+1}are disjoint.10.Ifk= 0, the induction hypothesis cannot be applied toak−1.28.s0+s1+· · ·+sn= (n+ 1)(s0+nd2)2.6APPLICATIONS2.564.9246.1208.71510.n12.r!14.3116.409618.12820.1522.3624.28626.12628.6444.There aren2+n+ 22regions.11
Page 18 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 18 preview imageChapter2Sets, Relations, and FunctionsSUPPLEMENTARY EXERCISES2.{1,2,3,4,5}4.{1,2,4}.6.{1,2,4,5,6}8.{2,3}10.12.ABCABC14.gf(x) = 2(x3+ 1)−5 = 2x3−3 andf g(x) = (2x−5)3+ 1 = 8x3−60x2+ 150x−12416.not a function with domainX18.not a function with domainX20.neither one-to-one nor onto22.one-to-one and onto24.f−1does not exist.26.f−1=3√x−528.8430.21032.{1,7},{2,6},{3,5},{4},{8}34.the sets of positive and negative real numbers36.538.640.(b)a=±142.reflexive only48.x∨x=xfor allx∈S, 1∨y=y∨1 =yfor ally∈S, 2∨3 = 3∨2 = 6, 2∨4 = 4∨2 = 4,2∨6 = 6∨2 = 6, 3∨6 = 6∨3 = 6,x∨yis undefined in all other cases12
Page 19 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 19 preview imageChapter 2Supplementary Exercises52.LetSdenote the set of all subsets of{1,2,3}that contain at most two elements, andletRbe the relation “is a subset of.”IfA={1},B={2}, andC={3}, thenA∨B={1,2},B∨C={2,3}, andA∨C={1,3}, but (A∨B)∨Cdoes not exist.54.[n] ={−n, n}56.f(x) =⎧⎨⎩xifx≡0 (mod 3)x−1ifx≡1 (mod 3)x−2ifx≡2 (mod 3)13
Page 20 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 20 preview imageChapter3Coding Theory3.1CONGRUENCE2.The quotientqis 3, and the remainderris 0.4.q= 12 andr= 76.q=−4 andr= 178.q=−6 andr= 910.p≡q(modm)12.p≡q(modm)14.p≡q(modm)16.p≡q(modm)18.[5]20.[4]22.[2]24.[8]26.[3]28.[5]30.[3]32.[6]34.[1]36.[4]38.11A.M.40.542.344.February, March, and November46.[2] = [10] = [−6]; [7] = [39] = [−1] = [−17]; [45] = [−3]14
Page 21 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 21 preview image3.2The Euclidean Algorithm48.InZ6, [2]= 0 and [3]= 0, but [2]·[3] = [0].50.(a)T6T5T8T7T9T4T3T2T1123457896134687151013(b)The whole project can be completed in 15 days.(c)The critical path isT1–T2–T4–T8.52.(b)Takea=14,b= 0,c= 1,x= 2,y= 0, andm= 2.3.2THE EUCLIDEAN ALGORITHM2.−54,−27,−18,−9,−6,−3,−2,−1,1,2,3,6,9,18,27,544.−24,−12,−8,−6,−4,−3,−2,−1,1,2,3,4,6,8,12,246.iri−13410217112429333140[Print 31]8.iri−1451014312221130[Print 11]15
Page 22 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 22 preview imageChapter3Coding Theory10.iri−189055134221313485563728190[Print 1]12.3014.iqirixiyi−1203010089901122321−223203−3731294−9470−3170[Print 29, 4,−9]16.iqirixiyi−12311001820111491−12335−3431144−5427−111452026−33[Print 7,−11, 14]18.iqirixiyi−1555100214601105551023481−3131744−14637−27752058−15[Print 37,−27, 7]20.(a)yes(b)no22.(a)yes(b)yes24.x= 95,y=−13326.impossible16
Page 23 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 23 preview image3.3The RSA Method3.3THE RSA METHOD2.10, 12, 144.46, 7, 156.QRr1r2pe13029141333033147018187311830183111830181011830180[Print 30]8.QRr1r2pe17532614974926130646413613779376301616311103410101100941000[Print 94]10.QRr1r2pe11210150114412144502505235232512159331110363026226231187111148711015970590[Print 70]12.12014.26416.518.1120.2122.7724.830.a=b= 2,x= 1,x′= 23.4ERROR-DETECTING AND ERROR-CORRECTING CODES2.04.16.08.010..941512..074614..004216..913517
Page 24 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 24 preview imageChapter3Coding Theory18.120.522.224.626.110028.1011130.332.434.(a)12(b)636.(a)19(b)940.Let the message wordxbec11c12. . . c1sc21c22. . . c2s. . . cs1cs2. . . css.Choosebi= 0 orbi= 1 so thatci1ci2. . . cis+biis even fori= 1,2, . . . , s, and choosedk= 0 ordk= 1 so thatc1kc2k. . . csk+dkis even fork= 1,2, . . . , s. Let the codewordcorresponding toxbec11c12. . . c1sc21c22. . . c2s. . . cs1cs2. . . cssb1b2. . . bsd1d2. . . ds.This is an (s2, s2+ 2s)-block code in which the minimal distance between codewordsis at least 3.3.5MATRIX CODES2.644.10246.001111118.0111101010.11×712.13×614.71116.00000, 01111, 10011, 1110018.000000, 001011, 010110, 011101, 100101, 101110, 110011, 11100020.0000000, 0011101, 0101011, 0110110, 1000111, 1011010, 1101100, 111000122.24.⎡⎢⎢⎢⎢⎣101110100010001⎤⎥⎥⎥⎥⎦⎡⎢⎢⎢⎢⎢⎢⎣001011111100010001⎤⎥⎥⎥⎥⎥⎥⎦18
Page 25 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 25 preview image3.6Matrix Codes That Correct All Single-Digit Errors26.28.⎡⎢⎢⎢⎢⎢⎢⎢⎢⎣1001011001011000010000100001⎤⎥⎥⎥⎥⎥⎥⎥⎥⎦⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣1111011011011111000001000001000001000001⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦30.⎡⎢⎢⎣10001001010001010010101000010110⎤⎥⎥⎦32.yes34.no, 110136.yes38.no, 101140.(a)The codewords determined byzandware [0 0 0 0 0 0 0 0] and [1 0 0 0 0 0 0 0];so the distance between these codewords is 1.(b)By Theorem 3.2(a), not all errors in a single digit can be detected.42.⎡⎢⎢⎣1000110010010100101110001011⎤⎥⎥⎦3.6MATRIX CODES THAT CORRECT ALL SINGLE-DIGIT ERRORS2.1001, 104.1100, ??6.0000, 108.0110, 0010.0000, 11112.0111, ??14.1000, 01116.1101, 11118.0000, 10120.0010, 00122.1111, ??24.1010, 10126.0000, 01028.0110, 01030.10, 01, 10, ??19
Page 26 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 26 preview imageChapter3Coding Theory32.1434.3036.k= 26 andn= 3138.k= 1013 andn= 102340.(a)(1−p)4(b)(1−p)7+ 7p(1−p)6SUPPLEMENTARY EXERCISES2.true4.false6.[8]8.[3]10.1112.2 and 114.416.1518.4720.2 = 41a−76b22.47 = 6a+ 11b24.10, 6, 23, 2126.QRr1r2pe1251151312531521416421016161012525250[Print25]28.168030.1632.034..0000000557236.338.The minimal Hamming distance between codewords cannot exceed the number of 1sin the codeword containing the fewest 1s.40.2k42.C(n,0) +C(n,1) +· · ·+C(n, s).44.00101111146.0000, 0111, 1000, 111120
Page 27 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 27 preview imageChapter 3Supplementary Exercises48.50.⎡⎢⎢⎢⎢⎢⎢⎢⎢⎣111111100000010000001000000100000010000001⎤⎥⎥⎥⎥⎥⎥⎥⎥⎦⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣100010111000011100011000001000001000001000001⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦52.⎡⎢⎢⎣100001100010010001001000111000110011⎤⎥⎥⎦54.0111, 11056.0101, ??58.1101, ??60.1011, 01062.(a)57×63(b)63×664.566.1, 2, 4, 8, 16, 32, and 64 pounds68.No; considera= 4,b= 2, andc= 8.21
Page 28 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 28 preview imageChapter4Graphs4.1GRAPHS AND THEIR REPRESENTATIONS2.V={F, G, H};E={{F, G}}4.V={A, B, C, D};E={{A, C},{A, D},{B, C},{B, D}}6.8.WXYZABYX10.no12.yes14.no18.1234567891022
Page 29 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 29 preview image4.1Graphs and Their Representations20.none, 0;C, 124.no26.⎡⎢⎢⎣0111101111011110⎤⎥⎥⎦V1:V2, V3, V4V2:V1, V3, V4V3:V1, V2, V4V4:V1, V2, V328.⎡⎢⎢⎣0111101011011010⎤⎥⎥⎦V1:V2, V3, V4V2:V1, V3V3:V1, V2, V4V4:V1, V330.V1V2V3V4V532.V3V1V4V5V234.There are no edges.36.no42.(a)yes(b)no(c)no44.23
Page 30 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 30 preview imageChapter4Graphs46.48.[2,3][2,4][1,3][1,4][3,4][1,2]50.n52.the vertices corresponding to primespsuch thatp > n24.2PATHS AND CIRCUITS2.not a graph4.a graph6.parallel edges:a, b, c; loops:f8.parallel edges: none; loops: none10.(a)e(1);b, c(2);a, f, b, a, d(5)(b)e(1);a, d(2);b, c(2);a, f, c(3);b, f, d(3)(c)e;b, c;a, d(d)a, b, c, d(4);a, e, c, f(4);b, f, d, e(4);a, d, e(3);c, d, f(3);b, c, e(3);a, b, f(3)24
Page 31 of 31
Solution Manual for Discrete Mathematics (Classic Version), 5th Edition - Page 31 preview image4.2Paths and Circuits12.no14.yes16.no18.no20.yes;a, g, d, e, h, b, c, i, f22.no24.yes,a, b, h, i, m, k, e, d, f, j, g, c26.no28.no30.no32.yes34.yes36.no38.no40.1, 2, 3, 4, 5, 13, 12, 11, 10, 9, 8, 7, 6, 16, 17, 18, 19, 20, 14, 15, 142.0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011,1001, 100044.25
Preview Mode

This document has 135 pages. Sign in to access the full document!

Study Now!

X-Copilot AI
Unlimited Access
Secure Payment
Instant Access
24/7 Support
Document Chat

Document Details

Subject
Mathematics
Textbook
Discrete Mathematics (Classic Versi...

Related Documents

View all
Quick Guides

Precalculus - Polynomial and Rational Functions

Quick Guides

Precalculus - Functions

Quick Guides

Precalculus - Exponential and Logarithmic Functions

Quick Guides

Math Word Problems - Translating Expressions

Quick Guides

Math Word Problems - Equations

Quick Guides

Algebra II – Word Problems

Quick Guides

Algebra II – Sequences and Series

Quick Guides

Algebra II - Segments Lines and Inequalities

Quick Guides

Algebra II - Relations and Functions

Quick Guides

Algebra II - Rational Expressions