Discrete Mathematics for Computer Scientists Stein·Drysdale·Bogart
Brief Contents List of Theorems,Lemmas,and Corollaries xix Preface xxi CHAPTER 1 Counting 1 CHAPTER 2 Cryptography and Number Theory 59 CHAPTER 3 Reflections on Logic and Proof 117 CHAPTER 4 Induction,Recursion,and Recurrences 161 CHAPTER 5 Probability 249 CHAPTER 6 Graphs 359 APPENDIX A Derivation of the More General Master Theorem 449 APPENDIX B Answers and Hints to Selected Problems 461 Bibliography 477 Index 479 vii
Brief Contents List of Theorems, Lemmas, and Corollaries xix Preface xxi CHAPTER 1 Counting 1 CHAPTER 2 Cryptography and Number Theory 59 CHAPTER 3 Reflections on Logic and Proof 117 CHAPTER 4 Induction, Recursion, and Recurrences 161 CHAPTER 5 Probability 249 CHAPTER 6 Graphs 359 APPENDIX A Derivation of the More General Master Theorem 449 APPENDIX B Answers and Hints to Selected Problems 461 Bibliography 477 Index 479 vii
Contents List of Theorems,Lemmas,and Corollaries xix Preface xxi CHAPTER 1 Counting 1 1.1 Basic Counting 1 The Sum Principle 1 Abstraction 3 Summing Consecutive Integers 3 The Product Principle 4 Two-Element Subsets 6 Important Concepts,Formulas,and Theorems 7 Problems 8 1.2 Counting Lists,Permutations,and Subsets 10 Using the Sum and Product Principles 10 Lists and Functions 12 The Bijection Principle 14 k-Element Permutations of a Set 15 Counting Subsets of a Set 16 Important Concepts,Formulas,and Theorems 18 Problems 20 1.3 Binomial Coefficients 22 Pascal's Triangle 22 A Proof Using the Sum Principle 24 The Binomial Theorem 26 Labeling and Trinomial Coefficients 28 Important Concepts,Formulas,and Theorems 29 Problems 30 ix
Contents List of Theorems, Lemmas, and Corollaries xix Preface xxi CHAPTER 1 Counting 1 1.1 Basic Counting 1 The Sum Principle 1 Abstraction 3 Summing Consecutive Integers 3 The Product Principle 4 Two-Element Subsets 6 Important Concepts, Formulas, and Theorems 7 Problems 8 1.2 Counting Lists, Permutations, and Subsets 10 Using the Sum and Product Principles 10 Lists and Functions 12 The Bijection Principle 14 k-Element Permutations of a Set 15 Counting Subsets of a Set 16 Important Concepts, Formulas, and Theorems 18 Problems 20 1.3 Binomial Coefficients 22 Pascal’s Triangle 22 A Proof Using the Sum Principle 24 The Binomial Theorem 26 Labeling and Trinomial Coefficients 28 Important Concepts, Formulas, and Theorems 29 Problems 30 ix
x Contents 1.4 Relations 32 What Is a Relation? 32 Functions as Relations 33 Properties of Relations 33 Equivalence Relations 36 Partial and Total Orders 39 Important Concepts,Formulas,and Theorems 41 Problems 42 1.5 Using Equivalence Relations in Counting 43 The Symmetry Principle 43 Equivalence Relations 45 The Quotient Principle 46 Equivalence Class Counting 46 Multisets 48 The Bookcase Arrangement Problem 50 The Number of k-Element Multisets of an n-Element Set 51 Using the Quotient Principle to Explain a Quotient 52 Important Concepts,Formulas,and Theorems 53 Problems 54 CHAPTER 2 Cryptography and Number Theory 59 2.1 Cryptography and Modular Arithmetic 59 Introduction to Cryptography 59 Private-Key Cryptography 60 Public-Key Cryptosystems 63 Arithmetic Modulo n 65 Cryptography Using Addition mod n 68 Cryptography Using Multiplication mod n 69 Important Concepts,Formulas,and Theorems 71 Problems 72
x Contents 1.4 Relations 32 What Is a Relation? 32 Functions as Relations 33 Properties of Relations 33 Equivalence Relations 36 Partial and Total Orders 39 Important Concepts, Formulas, and Theorems 41 Problems 42 1.5 Using Equivalence Relations in Counting 43 The Symmetry Principle 43 Equivalence Relations 45 The Quotient Principle 46 Equivalence Class Counting 46 Multisets 48 The Bookcase Arrangement Problem 50 The Number of k-Element Multisets of an n-Element Set 51 Using the Quotient Principle to Explain a Quotient 52 Important Concepts, Formulas, and Theorems 53 Problems 54 CHAPTER 2 Cryptography and Number Theory 59 2.1 Cryptography and Modular Arithmetic 59 Introduction to Cryptography 59 Private-Key Cryptography 60 Public-Key Cryptosystems 63 Arithmetic Modulo n 65 Cryptography Using Addition mod n 68 Cryptography Using Multiplication mod n 69 Important Concepts, Formulas, and Theorems 71 Problems 72
Contents xi 2.2 Inverses and Greatest Common Divisors 75 Solutions to Equations and Inverses mod n 75 Inverses mod n 76 Converting Modular Equations to Normal Equations 79 Greatest Common Divisors 80 Euclid's Division Theorem 81 Euclid's GCD Algorithm 84 Extended GCD Algorithm 85 Computing Inverses 88 Important Concepts,Formulas,and Theorems 89 Problems 90 2.3 The RSA Cryptosystem 93 Exponentiation mod n 93 The Rules of Exponents 93 Fermat's Little Theorem 96 The RSA Cryptosystem 97 The Chinese Remainder Theorem 101 Important Concepts,Formulas,and Theorems 102 Problems 104 2.4 Details of the RSA Cryptosystem 106 Practical Aspects of Exponentiation mod n 106 How Long Does It Take to Use the RSA Algorithm? 109 How Hard Is Factoring? 110 Finding Large Primes 110 Important Concepts,Formulas,and Theorems 113 Problems 114 CHAPTER 3 Reflections on Logic and Proof 117 3.1 Equivalence and Implication 117 Equivalence of Statements 117 Truth Tables 120 DeMorgan's Laws 123
Contents xi 2.2 Inverses and Greatest Common Divisors 75 Solutions to Equations and Inverses mod n 75 Inverses mod n 76 Converting Modular Equations to Normal Equations 79 Greatest Common Divisors 80 Euclid’s Division Theorem 81 Euclid’s GCD Algorithm 84 Extended GCD Algorithm 85 Computing Inverses 88 Important Concepts, Formulas, and Theorems 89 Problems 90 2.3 The RSA Cryptosystem 93 Exponentiation mod n 93 The Rules of Exponents 93 Fermat’s Little Theorem 96 The RSA Cryptosystem 97 The Chinese Remainder Theorem 101 Important Concepts, Formulas, and Theorems 102 Problems 104 2.4 Details of the RSA Cryptosystem 106 Practical Aspects of Exponentiation mod n 106 How Long Does It Take to Use the RSA Algorithm? 109 How Hard Is Factoring? 110 Finding Large Primes 110 Important Concepts, Formulas, and Theorems 113 Problems 114 CHAPTER 3 Reflections on Logic and Proof 117 3.1 Equivalence and Implication 117 Equivalence of Statements 117 Truth Tables 120 DeMorgan’s Laws 123
xii Contents Implication 125 If and Only If 126 Important Concepts,Formulas,and Theorems 129 Problems 131 3.2 Variables and Quantifiers 133 Variables and Universes 133 Quantifiers 134 Standard Notation for Quantification 136 Statements about Variables 138 Rewriting Statements to Encompass Larger Universes 138 Proving Quantified Statements True or False 139 Negation of Quantified Statements 140 Implicit Quantification 143 Proof of Quantified Statements 144 Important Concepts,Formulas,and Theorems 145 Problems 147 3.3 Inference 149 Direct Inference (Modus Ponens)and Proofs 149 Rules of Inference for Direct Proofs 151 Contrapositive Rule of Inference 153 Proof by Contradiction 155 Important Concepts,Formulas,and Theorems 158 Problems 159 CHAPTER 4 Induction,Recursion, and Recurrences 161 4.1 Mathematical Induction 161 Smallest Counterexamples 161 The Principle of Mathematical Induction 165 Strong Induction 169 Induction in General 171 A Recursive View of Induction 173
xii Contents Implication 125 If and Only If 126 Important Concepts, Formulas, and Theorems 129 Problems 131 3.2 Variables and Quantifiers 133 Variables and Universes 133 Quantifiers 134 Standard Notation for Quantification 136 Statements about Variables 138 Rewriting Statements to Encompass Larger Universes 138 Proving Quantified Statements True or False 139 Negation of Quantified Statements 140 Implicit Quantification 143 Proof of Quantified Statements 144 Important Concepts, Formulas, and Theorems 145 Problems 147 3.3 Inference 149 Direct Inference (Modus Ponens) and Proofs 149 Rules of Inference for Direct Proofs 151 Contrapositive Rule of Inference 153 Proof by Contradiction 155 Important Concepts, Formulas, and Theorems 158 Problems 159 CHAPTER 4 Induction, Recursion, and Recurrences 161 4.1 Mathematical Induction 161 Smallest Counterexamples 161 The Principle of Mathematical Induction 165 Strong Induction 169 Induction in General 171 A Recursive View of Induction 173
Contents xiii Structural Induction 176 Important Concepts,Formulas,and Theorems 178 Problems 180 4.2 Recursion,Recurrences,and Induction 183 Recursion 183 Examples of First-Order Linear Recurrences 185 Iterating a Recurrence 187 Geometric Series 188 First-Order Linear Recurrences 191 Important Concepts,Formulas,and Theorems 195 Problems 197 4.3 Growth Rates of Solutions to Recurrences 198 Divide and Conquer Algorithms 198 Recursion Trees 201 Three Different Behaviors 209 Important Concepts,Formulas,and Theorems 210 Problems 212 4.4 The Master Theorem 214 Master Theorem 214 Solving More General Kinds of Recurrences 217 Extending the Master Theorem 218 Important Concepts,Formulas,and Theorems 220 Problems 221 4.5 More General Kinds of Recurrences 222 Recurrence Inequalities 222 The Master Theorem for Inequalities 223 A Wrinkle with Induction 225 Further Wrinkles in Induction Proofs 227 Dealing with Functions Other Than ne 230 Important Concepts,Formulas,and Theorems 232 Problems 233
Contents xiii Structural Induction 176 Important Concepts, Formulas, and Theorems 178 Problems 180 4.2 Recursion, Recurrences, and Induction 183 Recursion 183 Examples of First-Order Linear Recurrences 185 Iterating a Recurrence 187 Geometric Series 188 First-Order Linear Recurrences 191 Important Concepts, Formulas, and Theorems 195 Problems 197 4.3 Growth Rates of Solutions to Recurrences 198 Divide and Conquer Algorithms 198 Recursion Trees 201 Three Different Behaviors 209 Important Concepts, Formulas, and Theorems 210 Problems 212 4.4 The Master Theorem 214 Master Theorem 214 Solving More General Kinds of Recurrences 217 Extending the Master Theorem 218 Important Concepts, Formulas, and Theorems 220 Problems 221 4.5 More General Kinds of Recurrences 222 Recurrence Inequalities 222 The Master Theorem for Inequalities 223 A Wrinkle with Induction 225 Further Wrinkles in Induction Proofs 227 Dealing with Functions Other Than nc 230 Important Concepts, Formulas, and Theorems 232 Problems 233
xiv Contents 4.6 Recurrences and Selection 235 The Idea of Selection 235 A Recursive Selection Algorithm 236 Selection without Knowing the Median in Advance 237 An Algorithm to Find an Element in the Middle Half 239 An Analysis of the Revised Selection Algorithm 242 Uneven Divisions 244 Important Concepts,Formulas,and Theorems 246 Problems 247 CHAPTER 5 Probability 249 5.1 Introduction to Probability 249 Why Study Probability? 249 Some Examples of Probability Computations 252 Complementary Probabilities 253 Probability and Hashing 254 The Uniform Probability Distribution 256 Important Concepts,Formulas,and Theorems 259 Problems 260 5.2 Unions and Intersections 262 The Probability of a Union of Events 262 Principle of Inclusion and Exclusion for Probability 265 The Principle of Inclusion and Exclusion for Counting 271 Important Concepts,Formulas,and Theorems 273 Problems 274 5.3 Conditional Probability and Independence 276 Conditional Probability 276 Bayes'Theorem 280 Independence 280 Independent Trials Processes 282 Tree Diagrams 284 Primality Testing 288
xiv Contents 4.6 Recurrences and Selection 235 The Idea of Selection 235 A Recursive Selection Algorithm 236 Selection without Knowing the Median in Advance 237 An Algorithm to Find an Element in the Middle Half 239 An Analysis of the Revised Selection Algorithm 242 Uneven Divisions 244 Important Concepts, Formulas, and Theorems 246 Problems 247 CHAPTER 5 Probability 249 5.1 Introduction to Probability 249 Why Study Probability? 249 Some Examples of Probability Computations 252 Complementary Probabilities 253 Probability and Hashing 254 The Uniform Probability Distribution 256 Important Concepts, Formulas, and Theorems 259 Problems 260 5.2 Unions and Intersections 262 The Probability of a Union of Events 262 Principle of Inclusion and Exclusion for Probability 265 The Principle of Inclusion and Exclusion for Counting 271 Important Concepts, Formulas, and Theorems 273 Problems 274 5.3 Conditional Probability and Independence 276 Conditional Probability 276 Bayes’ Theorem 280 Independence 280 Independent Trials Processes 282 Tree Diagrams 284 Primality Testing 288
Contents xv Important Concepts,Formulas,and Theorems 289 Problems 290 5.4 Random Variables 292 What Are Random Variables? 292 Binomial Probabilities 293 A Taste of Generating Functions 295 Expected Value 296 Expected Values of Sums and Numerical Multiples 299 Indicator Random Variables 302 The Number of Trials until the First Success 304 Important Concepts,Formulas,and Theorems 306 Problems 307 5.5 Probability Calculations in Hashing 310 Expected Number of Items per Location 310 Expected Number of Empty Locations 311 Expected Number of Collisions 312 Expected Maximum Number of Elements in a Location of a Hash Table 315 Important Concepts,Formulas,and Theorems 320 Problems 321 5.6 Conditional Expectations,Recurrences, and Algorithms 325 When Running Times Depend on More than Size of Inputs 325 Conditional Expected Values 327 Randomized Algorithms 329 Selection Revisited 331 QuickSort 333 A More Careful Analysis of RandomSelect 336 Important Concepts,Formulas,and Theorems 339 Problems 340
Contents xv Important Concepts, Formulas, and Theorems 289 Problems 290 5.4 Random Variables 292 What Are Random Variables? 292 Binomial Probabilities 293 A Taste of Generating Functions 295 Expected Value 296 Expected Values of Sums and Numerical Multiples 299 Indicator Random Variables 302 The Number of Trials until the First Success 304 Important Concepts, Formulas, and Theorems 306 Problems 307 5.5 Probability Calculations in Hashing 310 Expected Number of Items per Location 310 Expected Number of Empty Locations 311 Expected Number of Collisions 312 Expected Maximum Number of Elements in a Location of a Hash Table 315 Important Concepts, Formulas, and Theorems 320 Problems 321 5.6 Conditional Expectations, Recurrences, and Algorithms 325 When Running Times Depend on More than Size of Inputs 325 Conditional Expected Values 327 Randomized Algorithms 329 Selection Revisited 331 QuickSort 333 A More Careful Analysis of RandomSelect 336 Important Concepts, Formulas, and Theorems 339 Problems 340
xvi Contents 5.7 Probability Distributions and Variance 343 Distributions of Random Variables 343 Variance 346 Important Concepts,Formulas,and Theorems 354 Problems 355 CHAPTER 6 Graphs 359 6.1 Graphs 359 The Degree of a Vertex 363 Connectivity 365 Cycles 367 Trees 368 Other Properties of Trees 368 Important Concepts,Formulas,and Theorems 371 Problems 373 6.2 Spanning Trees and Rooted Trees 375 Spanning Trees 375 Breadth-First Search 377 Rooted Trees 382 Important Concepts,Formulas,and Theorems 386 Problems 387 6.3 Eulerian and Hamiltonian Graphs 389 Eulerian Tours and Trails 389 Finding Eulerian Tours 394 Hamiltonian Paths and Cycles 395 NP-Complete Problems 401 Proving That Problems Are NP-Complete 403 Important Concepts,Formulas,and Theorems 406 Problems 407 6.4 Matching Theory 410 The Idea of a Matching 410 Making Matchings Bigger 414
xvi Contents 5.7 Probability Distributions and Variance 343 Distributions of Random Variables 343 Variance 346 Important Concepts, Formulas, and Theorems 354 Problems 355 CHAPTER 6 Graphs 359 6.1 Graphs 359 The Degree of a Vertex 363 Connectivity 365 Cycles 367 Trees 368 Other Properties of Trees 368 Important Concepts, Formulas, and Theorems 371 Problems 373 6.2 Spanning Trees and Rooted Trees 375 Spanning Trees 375 Breadth-First Search 377 Rooted Trees 382 Important Concepts, Formulas, and Theorems 386 Problems 387 6.3 Eulerian and Hamiltonian Graphs 389 Eulerian Tours and Trails 389 Finding Eulerian Tours 394 Hamiltonian Paths and Cycles 395 NP-Complete Problems 401 Proving That Problems Are NP-Complete 403 Important Concepts, Formulas, and Theorems 406 Problems 407 6.4 Matching Theory 410 The Idea of a Matching 410 Making Matchings Bigger 414