Skip to content
Textbook Guides

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.

Preview 31 of 135 pages

See the first 31 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    D ISCRETE M ATHEMATICS F IFTH E DITION John A. Dossey Illinois State University Albert D. Otto Illinois State University Lawrence E. Spence Illinois State University Charles Vanden Eynden Illinois State University I NSTRUCTOR ’ S S OLUTIONS M ANUAL

  2. Page 2
  3. Page 3
    Read page 3 as text

    Contents 1 An Introduction to Combinatorial Problems and Techniques 1 1.1 The Time to Complete a Project . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 A Matching Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 A Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Algorithms and Their Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . 4 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Sets, Relations, and Functions 6 2.1 Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Partial Ordering Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.5 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.6 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 Coding Theory 14 3.1 Congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 The Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3 The RSA Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.4 Error-Detecting and Error-Correcting Codes . . . . . . . . . . . . . . . . . . 17 3.5 Matrix Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.6 Matrix Codes That Correct All Single-Digit Errors . . . . . . . . . . . . . . . 19 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 iii

  4. Page 4
    Read page 4 as text

    Table of Contents 4 Graphs 22 4.1 Graphs and Their Representations . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2 Paths and Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.3 Shortest Paths and Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.4 Coloring a Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.5 Directed Graphs and Multigraphs . . . . . . . . . . . . . . . . . . . . . . . . 30 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5 Trees 36 5.1 Properties of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.2 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.3 Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.4 Rooted Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.5 Binary Trees and Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.6 Optimal Binary Trees and Binary Search Trees . . . . . . . . . . . . . . . . . 51 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6 Matching 63 6.1 Systems of Distinct Representatives . . . . . . . . . . . . . . . . . . . . . . . 63 6.2 Matchings in Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 6.3 A Matching Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.4 Applications of the Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.5 The Hungarian Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 7 Network Flows 68 7.1 Flows and Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.2 A Flow Augmentation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 70 7.3 The Max-Flow Min-Cut Theorem . . . . . . . . . . . . . . . . . . . . . . . . 73 7.4 Flows and Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 iv

  5. Page 5
    Read page 5 as text

    Table of Contents 8 Counting Techniques 78 8.1 Pascal’s Triangle and the Binomial Theorem . . . . . . . . . . . . . . . . . . 78 8.2 Three Fundamental Principles . . . . . . . . . . . . . . . . . . . . . . . . . . 78 8.3 Permutations and Combinations . . . . . . . . . . . . . . . . . . . . . . . . . 79 8.4 Arrangements and Selections with Repetitions . . . . . . . . . . . . . . . . . 79 8.5 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 8.6 The Principle of Inclusion-Exclusion . . . . . . . . . . . . . . . . . . . . . . . 81 8.7 Generating Permutations and r -Combinations . . . . . . . . . . . . . . . . . 82 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 9 Recurrence Relations and Generating Functions 84 9.1 Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 9.2 The Method of Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 9.3 Linear Difference Equations with Constant Coefficients . . . . . . . . . . . . 91 9 . 4 ∗ Analyzing the Efficiency of Algorithms with Recurrence Relations . . . . . . 94 9.5 Counting with Generating Functions . . . . . . . . . . . . . . . . . . . . . . . 99 9.6 The Algebra of Generating Functions . . . . . . . . . . . . . . . . . . . . . . 100 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 10 Combinatorial Circuits and Finite State Machines 105 10.1 Logical Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 10.2 Creating Combinatorial Circuits . . . . . . . . . . . . . . . . . . . . . . . . . 107 10.3 Karnaugh Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 10.4 Finite State Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 v

  6. Page 6
    Read page 6 as text

    Table of Contents Appendices 120 A An Introduction to Logic and Proof 120 A.1 Statements and Connectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 A.2 Logical Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 A.3 Methods of Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 B Matrices 130 vi

  7. Page 7
    Read page 7 as text

    Chapter 1 An Introduction to Combinatorial Problems and Techniques 1.1 THE TIME TO COMPLETE A PROJECT 2. 31; A-B-E-G 4. 39; A-C-G-H 6. 16; B-D-F-H 8. 27; A-D-E-H 10. 27; A-B-D-G 1

  8. Page 8
    Read page 8 as text

    Chapter 1 An Introduction to Combinatorial Problems and Techniques 12. 29; C-F-I 14. 33; H-I-F-G 16. 31; D-E-I 18. 20 minutes 2

  9. Page 9
    Read page 9 as text

    1.2 A Matching Problem 1.2 A MATCHING PROBLEM 2. 720 4. 210 6. 84 8. 1680 10. 19,958,400 12. 1 8 14. 5040 16. 126 18. 210 20. 119 22. 1320 24. 5040 26. 240 28. 1200 1.3 A KNAPSACK PROBLEM 2. T 4. F 6. F 8. F 10. T 12. T 14. T 16. no 18. yes; 32 20. ∅ , { 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 } ; 16 22. 128 24. 1024 26. 256 28. 26 30. { 1 , 4 , 6 , 7 , 8 , 9 , 10 , 11 , 12 } 1.4 ALGORITHMS AND THEIR EFFICIENCY 2. yes; 0 4. no 6. no 8. − 1, 9, 84; 3, 17, 84 10. − 4, − 4, 41, 95; 2, 11, 33, 95 12. 111000 14. 001010 3

  10. Page 10
    Read page 10 as text

    Chapter 1 An Introduction to Combinatorial Problems and Techniques 16. k j a 1 a 2 a 3 3 1 1 1 2 1 1 1 1 1 1 1 0 1 1 1 18. k j a 1 a 2 a 3 a 4 4 1 1 1 0 1 1 1 1 20. 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 seconds 26. 2 . 3 × 10 10 years, 12.5 seconds 4

  11. Page 11
    Read page 11 as text

    Chapter 1 Supplementary Exercises 28. 4 n − 3 30. 3 n − 2 32. − 4, − 4, 41, 95 SUPPLEMENTARY EXERCISES 2. 20; B-E-F-H 4. 336 6. 40 8. 14040 10. T 12. F 14. T 16. T 18. 16 20. no 22. yes; 0 24. − 5, 7, 7, 88 26. ∅ , { 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 × 10 8 years 30. 4 32. 4 r − 3 5

  12. Page 12
    Read page 12 as text

    Chapter 2 Sets, Relations, and Functions 2.1 SET OPERATIONS 2. A ∪ B = { 1 , 2 , 4 , 5 , 6 , 7 , 9 } , A ∩ B = { 1 , 4 , 6 , 9 } , A − B = ∅ , A = { 2 , 3 , 5 , 7 , 8 } , and B = { 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 } , and B = { 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. A B A B C 14. A = { 1, 2 } , B = { 1, 3 } , and C = { 1 } 16. A = { 1, 2 } , B = { 1, 3 } , and C = { 1 } 6

  13. Page 13
    Read page 13 as text

    2.2 Equivalence Relations 18. A 20. ∅ 22. A ∩ B 24. A ∪ B 26. The equality A − B = B − A holds if and only if A = B . 28. The equality A ∩ B = A holds if and only if A ⊆ B . 2.2 EQUIVALENCE RELATIONS 2. reflexive and symmetric 4. reflexive, symmetric, and transitive 6. reflexive and symmetric 8. none 10. reflexive and symmetric 12. reflexive and transitive 14. The equivalence class of R containing ABCD consists of the string ABC and the strings of 4 letters having A as their first letter and C as their third letter. There are 26 2 = 676 distinct equivalence classes of R . 16. The equivalence class of R containing { 1, 2, 3 } is the set containing the following four elements of S : { 1, 3 } , { 1, 2, 3 } , { 1, 2, 3, 4 } , and { 1, 3, 4 } . There are 8 different equivalence classes of R , namely the sets consisting of the elements S , S ∪ { 2 } , S ∪ { 4 } , and S ∪ { 2 , 4 } for every S ⊆ { 1 , 3 , 5 } . 18. The equivalence class of R containing (5 , 8) is the set { ( x 1 , x 2 ) : each x i is an integer and x 1 − x 2 = 5 − 8 } . There are infinitely many distinct equivalence classes of R , namely, the sets of the form { ( x 1 , x 2 ) : each x i is an integer and x 1 − x 2 = k } , where k = 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 form E 1 × E 2 , where E i is an equivalence class of R i . 28. There are 5 partitions of a set with three elements. 32. Let S be a nonempty set and R an equivalence relation on S . Then there is a function f with domain S such that s 1 R s 2 if and only if f ( s 1 ) = f ( s 2 ). 7

  14. Page 14
    Read page 14 as text

    Chapter 2 Sets, Relations, and Functions 2.3 PARTIAL ORDERING RELATIONS 2. not antisymmetric 4. partial ordering 6. not antisymmetric 8. not antisymmetric 10. 1 3 4 2 12. {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. Let S denote the set of residents of Illinois and R be defined so that x R y means that x is a sister of y . 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

  15. Page 15
    Read page 15 as text

    2.3 Partial Ordering Relations 32. (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 that y is element of S such that x R y is false. If there is no element y 1 in S such that y 1 R y , then y is a minimal element of S , contradicting that x is the unique minimal element of S . Thus there must be such an element y 1 . If there is no element y 2 in S such that y 2 R y 1 , then y 1 is a minimal element of S , another contradiction. So there must be such an element y 2 . Because S is finite, continuing in this manner must produce a minimal element y k of S different from x . Because x is the unique minimal element of S , the assumption that there is an element y of S such that x R y is false must be incorrect. Thus x R s is true for every s ∈ S . (b) Let Z denote the set of integers and S = Z ∪ { ∅ } . Let R be the relation defined on S by x R y if and only if one of the following holds: (i) x, y ∈ Z and x ≤ y , or (ii) x = y = ∅ . Then ∅ is the unique minimal element in S , but ∅ R z is false for every z ∈ Z . 40. 2 n 42. 2 n · 3 n ( n − 1) / 2 9

  16. Page 16
    Read page 16 as text

    Chapter 2 Sets, Relations, and Functions 2.4 FUNCTIONS 2. not a function with domain X 4. a function with domain X 6. a function with domain X 8. a function with domain X 10. a function with domain X 12. not a function with domain X 14. 4 16. 13 18. 8 20. 7 22. − 1 24. 6 26. − 2 28. 10 30. 0.78 32. 6.64 34. 3.22 36. − 2 . 56 38. gf ( x ) = g ( f ( x )) = √ x 2 + 1 and f g ( x ) = f ( g ( x )) = x + 1 40. gf ( x ) = 1 3 x and f g ( x ) = 3 x 42. gf ( x ) = 5(2 x ) − 2 2 x and f g ( x ) = 2 5 x − x 2 44. gf ( x ) = 4 x − 1 2 − x and f g ( x ) = 3 x − 2 3 − x 46. one-to-one and onto 48. neither one-to-one nor onto 50. one-to-one but not onto 52. onto but not one-to-one 54. f − 1 ( x ) = x + 2 3 56. f − 1 ( x ) does not exist. 58. f − 1 ( x ) does not exist. 60. f − 1 ( x ) = 3 √ x + 1 62. For Y = { x ∈ X : x  = 0 } , we have g − 1 ( x ) = − 1 x . 64. If n < m , there are no one-to-one functions; and if m ≤ n , there are P ( n, m ) = n ( n − 1)( n − 2) · · · ( n − m + 1) one-to-one functions. 68. Let X = { 1 } , Y = { 2 , 3 } , and Z = 4. Define f : X → Y by f ( x ) = 2 for all x ∈ X and g : Y → Z by g ( y ) = 4 for all y ∈ Y . 10

  17. Page 17
    Read page 17 as text

    2.5 Mathematical Induction 2.5 MATHEMATICAL INDUCTION 2. 7, 9, 13, 21, 37, 69 4. x n = { x if n = 1 x · x n − 1 if n ≥ 2 6. Let x n denote the n th odd positive integer. Then x n = { 1 if n = 1 x n − 1 + 2 if n ≥ 2. 8. If k = 1, the sets { x 1 , x 2 , . . . , x k } and { x 2 , x 3 , . . . , x k +1 } are disjoint. 10. If k = 0, the induction hypothesis cannot be applied to a k − 1 . 28. s 0 + s 1 + · · · + s n = ( n + 1) ( s 0 + nd 2 ) 2.6 APPLICATIONS 2. 56 4. 924 6. 120 8. 715 10. n 12. r ! 14. 31 16. 4096 18. 128 20. 15 22. 36 24. 286 26. 126 28. 64 44. There are n 2 + n + 2 2 regions. 11

  18. Page 18
    Read page 18 as text

    Chapter 2 Sets, Relations, and Functions SUPPLEMENTARY EXERCISES 2. { 1 , 2 , 3 , 4 , 5 } 4. { 1 , 2 , 4 } . 6. { 1 , 2 , 4 , 5 , 6 } 8. { 2 , 3 } 10. 12. A B C A B C 14. gf ( x ) = 2( x 3 + 1) − 5 = 2 x 3 − 3 and f g ( x ) = (2 x − 5) 3 + 1 = 8 x 3 − 60 x 2 + 150 x − 124 16. not a function with domain X 18. not a function with domain X 20. neither one-to-one nor onto 22. one-to-one and onto 24. f − 1 does not exist. 26. f − 1 = 3 √ x − 5 28. 84 30. 210 32. { 1 , 7 } , { 2 , 6 } , { 3 , 5 } , { 4 } , { 8 } 34. the sets of positive and negative real numbers 36. 5 38. 6 40. (b) a = ± 1 42. reflexive only 48. x ∨ x = x for all x ∈ S , 1 ∨ y = y ∨ 1 = y for all y ∈ S , 2 ∨ 3 = 3 ∨ 2 = 6, 2 ∨ 4 = 4 ∨ 2 = 4, 2 ∨ 6 = 6 ∨ 2 = 6, 3 ∨ 6 = 6 ∨ 3 = 6, x ∨ y is undefined in all other cases 12

  19. Page 19
    Read page 19 as text

    Chapter 2 Supplementary Exercises 52. Let S denote the set of all subsets of { 1 , 2 , 3 } that contain at most two elements, and let R be the relation “is a subset of.” If A = { 1 } , B = { 2 } , and C = { 3 } , then A ∨ B = { 1 , 2 } , B ∨ C = { 2 , 3 } , and A ∨ C = { 1 , 3 } , but ( A ∨ B ) ∨ C does not exist. 54. [ n ] = {− n, n } 56. f ( x ) = ⎧ ⎨ ⎩ x if x ≡ 0 (mod 3) x − 1 if x ≡ 1 (mod 3) x − 2 if x ≡ 2 (mod 3) 13

  20. Page 20
    Read page 20 as text

    Chapter 3 Coding Theory 3.1 CONGRUENCE 2. The quotient q is 3, and the remainder r is 0. 4. q = 12 and r = 7 6. q = − 4 and r = 17 8. q = − 6 and r = 9 10. p  ≡ q (mod m ) 12. p ≡ q (mod m ) 14. p ≡ q (mod m ) 16. p  ≡ q (mod m ) 18. [5] 20. [4] 22. [2] 24. [8] 26. [3] 28. [5] 30. [3] 32. [6] 34. [1] 36. [4] 38. 11 A.M. 40. 5 42. 3 44. February, March, and November 46. [2] = [10] = [ − 6]; [7] = [39] = [ − 1] = [ − 17]; [45] = [ − 3] 14

  21. Page 21
    Read page 21 as text

    3.2 The Euclidean Algorithm 48. In Z 6 , [2]  = 0 and [3]  = 0, but [2] · [3] = [0]. 50. (a) T 6 T 5 T 8 T 7 T 9 T 4 T 3 T 2 T 1 1 2 3 4 5 7 8 9 6 1 3 4 6 8 7 15 10 13 (b) The whole project can be completed in 15 days. (c) The critical path is T 1 – T 2 – T 4 – T 8 . 52. (b) Take a = 1 4 , b = 0, c = 1, x = 2, y = 0, and m = 2. 3.2 THE EUCLIDEAN ALGORITHM 2. − 54 , − 27 , − 18 , − 9 , − 6 , − 3 , − 2 , − 1 , 1 , 2 , 3 , 6 , 9 , 18 , 27 , 54 4. − 24 , − 12 , − 8 , − 6 , − 4 , − 3 , − 2 , − 1 , 1 , 2 , 3 , 4 , 6 , 8 , 12 , 24 6. i r i − 1 341 0 217 1 124 2 93 3 31 4 0 [Print 31] 8. i r i − 1 451 0 143 1 22 2 11 3 0 [Print 11] 15

  22. Page 22
    Read page 22 as text

    Chapter 3 Coding Theory 10. i r i − 1 89 0 55 1 34 2 21 3 13 4 8 5 5 6 3 7 2 8 1 9 0 [Print 1] 12. 30 14. i q i r i x i y i − 1 2030 1 0 0 899 0 1 1 2 232 1 − 2 2 3 203 − 3 7 3 1 29 4 − 9 4 7 0 − 31 70 [Print 29, 4, − 9] 16. i q i r i x i y i − 1 231 1 0 0 182 0 1 1 1 49 1 − 1 2 3 35 − 3 4 3 1 14 4 − 5 4 2 7 − 11 14 5 2 0 26 − 33 [Print 7, − 11, 14] 18. i q i r i x i y i − 1 555 1 0 0 2146 0 1 1 0 555 1 0 2 3 481 − 3 1 3 1 74 4 − 1 4 6 37 − 27 7 5 2 0 58 − 15 [Print 37, − 27, 7] 20. (a) yes (b) no 22. (a) yes (b) yes 24. x = 95, y = − 133 26. impossible 16

  23. Page 23
    Read page 23 as text

    3.3 The RSA Method 3.3 THE RSA METHOD 2. 10, 12, 14 4. 46, 7, 15 6. Q R r 1 r 2 p e 1 30 29 14 1 33 30 33 14 7 0 18 18 7 3 1 18 30 18 3 1 1 18 30 18 1 0 1 18 30 18 0 [Print 30] 8. Q R r 1 r 2 p e 1 7 53 26 1 49 7 49 26 13 0 64 64 13 6 1 37 79 37 6 3 0 16 16 3 1 1 10 34 10 1 0 1 100 94 100 0 [Print 94] 10. Q R r 1 r 2 p e 1 12 101 50 1 144 12 144 50 25 0 523 523 25 12 1 59 331 1103 6 3 0 262 262 3 1 1 871 1114 871 1 0 1 59 70 59 0 [Print 70] 12. 120 14. 264 16. 5 18. 11 20. 21 22. 77 24. 8 30. a = b = 2, x = 1, x ′ = 2 3.4 ERROR-DETECTING AND ERROR-CORRECTING CODES 2. 0 4. 1 6. 0 8. 0 10. .9415 12. .0746 14. .0042 16. .9135 17

  24. Page 24
    Read page 24 as text

    Chapter 3 Coding Theory 18. 1 20. 5 22. 2 24. 6 26. 1100 28. 10111 30. 3 32. 4 34. (a) 12 (b) 6 36. (a) 19 (b) 9 40. Let the message word x be c 11 c 12 . . . c 1 s c 21 c 22 . . . c 2 s . . . c s 1 c s 2 . . . c ss . Choose b i = 0 or b i = 1 so that c i 1 c i 2 . . . c is + b i is even for i = 1 , 2 , . . . , s , and choose d k = 0 or d k = 1 so that c 1 k c 2 k . . . c sk + d k is even for k = 1 , 2 , . . . , s . Let the codeword corresponding to x be c 11 c 12 . . . c 1 s c 21 c 22 . . . c 2 s . . . c s 1 c s 2 . . . c ss b 1 b 2 . . . b s d 1 d 2 . . . d s . This is an ( s 2 , s 2 + 2 s )-block code in which the minimal distance between codewords is at least 3. 3.5 MATRIX CODES 2. 64 4. 1024 6. 00111111 8. 01111010 10. 11 × 7 12. 13 × 6 14. 7 11 16. 00000, 01111, 10011, 11100 18. 000000, 001011, 010110, 011101, 100101, 101110, 110011, 111000 20. 0000000, 0011101, 0101011, 0110110, 1000111, 1011010, 1101100, 1110001 22. 24. ⎡ ⎢ ⎢ ⎢ ⎢ ⎣ 1 0 1 1 1 0 1 0 0 0 1 0 0 0 1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎦ ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 0 0 1 0 1 1 1 1 1 1 0 0 0 1 0 0 0 1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ 18

  25. Page 25
    Read page 25 as text

    3.6 Matrix Codes That Correct All Single-Digit Errors 26. 28. ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 1 1 1 1 0 1 1 0 1 1 0 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ 30. ⎡ ⎢ ⎢ ⎣ 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 1 1 0 ⎤ ⎥ ⎥ ⎦ 32. yes 34. no, 1101 36. yes 38. no, 1011 40. (a) The codewords determined by z and w are [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. ⎡ ⎢ ⎢ ⎣ 1 0 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 ⎤ ⎥ ⎥ ⎦ 3.6 MATRIX CODES THAT CORRECT ALL SINGLE-DIGIT ERRORS 2. 1001, 10 4. 1100, ?? 6. 0000, 10 8. 0110, 00 10. 0000, 111 12. 0111, ?? 14. 1000, 011 16. 1101, 111 18. 0000, 101 20. 0010, 001 22. 1111, ?? 24. 1010, 101 26. 0000, 010 28. 0110, 010 30. 10, 01, 10, ?? 19

  26. Page 26
    Read page 26 as text

    Chapter 3 Coding Theory 32. 14 34. 30 36. k = 26 and n = 31 38. k = 1013 and n = 1023 40. (a) (1 − p ) 4 (b) (1 − p ) 7 + 7 p (1 − p ) 6 SUPPLEMENTARY EXERCISES 2. true 4. false 6. [8] 8. [3] 10. 11 12. 2 and 1 14. 4 16. 15 18. 47 20. 2 = 41 a − 76 b 22. 47 = 6 a + 11 b 24. 10, 6, 23, 21 26. Q R r 1 r 2 p e 1 25 11 5 1 31 25 31 5 2 1 4 16 4 2 1 0 16 16 1 0 1 25 25 25 0 [Print 25] 28. 1680 30. 16 32. 0 34. .00000005572 36. 3 38. The minimal Hamming distance between codewords cannot exceed the number of 1s in the codeword containing the fewest 1s. 40. 2 k 42. C ( n, 0) + C ( n, 1) + · · · + C ( n, s ). 44. 001011111 46. 0000, 0111, 1000, 1111 20

  27. Page 27
    Read page 27 as text

    Chapter 3 Supplementary Exercises 48. 50. ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 1 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ 52. ⎡ ⎢ ⎢ ⎣ 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 ⎤ ⎥ ⎥ ⎦ 54. 0111, 110 56. 0101, ?? 58. 1101, ?? 60. 1011, 010 62. (a) 57 × 63 (b) 63 × 6 64. 5 66. 1, 2, 4, 8, 16, 32, and 64 pounds 68. No; consider a = 4, b = 2, and c = 8. 21

  28. Page 28
    Read page 28 as text

    Chapter 4 Graphs 4.1 GRAPHS AND THEIR REPRESENTATIONS 2. V = { F, G, H } ; E = {{ F, G }} 4. V = { A, B, C, D } ; E = {{ A, C } , { A, D } , { B, C } , { B, D }} 6. 8. W X Y Z A B Y X 10. no 12. yes 14. no 18. 1 2 3 4 5 6 7 8 9 10 22

  29. Page 29
    Read page 29 as text

    4.1 Graphs and Their Representations 20. none, 0; C , 1 24. no 26. ⎡ ⎢ ⎢ ⎣ 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 ⎤ ⎥ ⎥ ⎦ V 1 : V 2 , V 3 , V 4 V 2 : V 1 , V 3 , V 4 V 3 : V 1 , V 2 , V 4 V 4 : V 1 , V 2 , V 3 28. ⎡ ⎢ ⎢ ⎣ 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 ⎤ ⎥ ⎥ ⎦ V 1 : V 2 , V 3 , V 4 V 2 : V 1 , V 3 V 3 : V 1 , V 2 , V 4 V 4 : V 1 , V 3 30. V 1 V 2 V 3 V 4 V 5 32. V 3 V 1 V 4 V 5 V 2 34. There are no edges. 36. no 42. (a) yes (b) no (c) no 44. 23

  30. Page 30
    Read page 30 as text

    Chapter 4 Graphs 46. 48. [2,3] [2,4] [1,3] [1,4] [3,4] [1,2] 50. n 52. the vertices corresponding to primes p such that p > n 2 4.2 PATHS AND CIRCUITS 2. not a graph 4. a graph 6. parallel edges: a, b, c ; loops: f 8. parallel edges: none; loops: none 10. (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

  31. Page 31
    Read page 31 as text

    4.2 Paths and Circuits 12. no 14. yes 16. no 18. no 20. yes; a, g, d, e, h, b, c, i, f 22. no 24. yes, a, b, h, i, m, k, e, d, f, j, g, c 26. no 28. no 30. no 32. yes 34. yes 36. no 38. no 40. 1, 2, 3, 4, 5, 13, 12, 11, 10, 9, 8, 7, 6, 16, 17, 18, 19, 20, 14, 15, 1 42. 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000 44. 25

104 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Mathematics study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.