Discrete mathematics for computer scientists

Cover......Page 1
Contents......Page 10
List of Theorems, Lemmas, and Corollaries......Page 20
Preface......Page 22
  The Sum Principle......Page 32
  Summing Consecutive Integers......Page 34
  The Product Principle......Page 35
  Two-Element Subsets......Page 37
  Important Concepts, Formulas, and Theorems......Page 38
  Problems......Page 39
  Using the Sum and Product Principles......Page 41
  Lists and Functions......Page 43
  The Bijection Principle......Page 45
  k-Element Permutations of a Set......Page 46
  Counting Subsets of a Set......Page 47
  Important Concepts, Formulas, and Theorems......Page 49
  Problems......Page 51
  Pascal’s Triangle......Page 53
  A Proof Using the Sum Principle......Page 55
  The Binomial Theorem......Page 57
  Labeling and Trinomial Coeficients......Page 59
  Important Concepts, Formulas, and Theorems......Page 60
  Problems......Page 61
  What Is a Relation?......Page 63
  Properties of Relations......Page 64
  Equivalence Relations......Page 67
  Partial and Total Orders......Page 70
  Important Concepts, Formulas, and Theorems......Page 72
  Problems......Page 73
  The Symmetry Principle......Page 74
  Equivalence Relations......Page 76
  Equivalence Class Counting......Page 77
  Multisets......Page 79
  The Bookcase Arrangement Problem......Page 81
  The Number of k-Element Multisets of an n-Element Set......Page 82
  Using the Quotient Principle to Explain a Quotient......Page 83
  Important Concepts, Formulas, and Theorems......Page 84
  Problems......Page 85
  Introduction to Cryptography......Page 90
  Private-Key Cryptography......Page 91
  Public-Key Cryptosystems......Page 94
  Arithmetic Modulo n......Page 96
  Cryptography Using Addition mod n......Page 99
  Cryptography Using Multiplication mod n......Page 100
  Important Concepts, Formulas, and Theorems......Page 102
  Problems......Page 103
  Solutions to Equations and Inverses mod n......Page 106
  Inverses mod n......Page 107
  Converting Modular Equations to Normal Equations......Page 110
  Greatest Common Divisors......Page 111
  Euclid’s Division Theorem......Page 112
  Euclid’s GCD Algorithm......Page 115
  Extended GCD Algorithm......Page 116
  Computing Inverses......Page 119
  Important Concepts, Formulas, and Theorems......Page 120
  Problems......Page 121
  The Rules of Exponents......Page 124
  Fermat’s Little Theorem......Page 127
  The RSA Cryptosystem......Page 128
  The Chinese Remainder Theorem......Page 132
  Important Concepts, Formulas, and Theorems......Page 133
  Problems......Page 135
  Practical Aspects of Exponentiation mod n......Page 137
  How Long Does It Take to Use the RSA Algorithm?......Page 140
  Finding Large Primes......Page 141
  Important Concepts, Formulas, and Theorems......Page 144
  Problems......Page 145
  Equivalence of Statements......Page 148
  Truth Tables......Page 151
  DeMorgan’s Laws......Page 154
  Implication......Page 156
  If and Only If......Page 157
  Important Concepts, Formulas, and Theorems......Page 160
  Problems......Page 162
  Variables and Universes......Page 164
  Quantifiers......Page 165
  Standard Notation for Quantification......Page 167
  Rewriting Statements to Encompass Larger Universes......Page 169
  Proving Quantified Statements True or False......Page 170
  Negation of Quantified Statements......Page 171
  Implicit Quantification......Page 174
  Proof of Quantified Statements......Page 175
  Important Concepts, Formulas, and Theorems......Page 176
  Problems......Page 178
  Direct Inference (Modus Ponens) and Proofs......Page 180
  Rules of Inference for Direct Proofs......Page 182
  Contrapositive Rule of Inference......Page 184
  Proof by Contradiction......Page 186
  Important Concepts, Formulas, and Theorems......Page 189
  Problems......Page 190
  Smallest Counterexamples......Page 192
  The Principle of Mathematical Induction......Page 196
  Strong Induction......Page 200
  Induction in General......Page 202
  A Recursive View of Induction......Page 204
  Structural Induction......Page 207
  Important Concepts, Formulas, and Theorems......Page 209
  Problems......Page 211
  Recursion......Page 214
  Examples of First-Order Linear Recurrences......Page 216
  Iterating a Recurrence......Page 218
  Geometric Series......Page 219
  First-Order Linear Recurrences......Page 222
  Important Concepts, Formulas, and Theorems......Page 226
  Problems......Page 228
  Divide and Conquer Algorithms......Page 229
  Recursion Trees......Page 232
  Three Different Behaviors......Page 240
  Important Concepts, Formulas, and Theorems......Page 241
  Problems......Page 243
  Master Theorem......Page 245
  Solving More General Kinds of Recurrences......Page 248
  Extending the Master Theorem......Page 249
  Important Concepts, Formulas, and Theorems......Page 251
  Problems......Page 252
  Recurrence Inequalities......Page 253
  The Master Theorem for Inequalities......Page 254
  A Wrinkle with Induction......Page 256
  Further Wrinkles in Induction Proofs......Page 258
  Dealing with Functions Other Than n[sup(c)]......Page 261
  Important Concepts, Formulas, and Theorems......Page 263
  Problems......Page 264
  The Idea of Selection......Page 266
  A Recursive Selection Algorithm......Page 267
  Selection without Knowing the Median in Advance......Page 268
  An Algorithm to Find an Element in the Middle Half......Page 270
  An Analysis of the Revised Selection Algorithm......Page 273
  Uneven Divisions......Page 275
  Important Concepts, Formulas, and Theorems......Page 277
  Problems......Page 278
  Why Study Probability?......Page 280
  Some Examples of Probability Computations......Page 283
  Complementary Probabilities......Page 284
  Probability and Hashing......Page 285
  The Uniform Probability Distribution......Page 287
  Important Concepts, Formulas, and Theorems......Page 290
  Problems......Page 291
  The Probability of a Union of Events......Page 293
  Principle of Inclusion and Exclusion for Probability......Page 296
  The Principle of Inclusion and Exclusion for Counting......Page 302
  Important Concepts, Formulas, and Theorems......Page 304
  Problems......Page 305
  Conditional Probability......Page 307
  Independence......Page 311
  Independent Trials Processes......Page 313
  Tree Diagrams......Page 315
  Primality Testing......Page 319
  Important Concepts, Formulas, and Theorems......Page 320
  Problems......Page 321
  What Are Random Variables?......Page 323
  Binomial Probabilities......Page 324
  A Taste of Generating Functions......Page 326
  Expected Value......Page 327
  Expected Values of Sums and Numerical Multiples......Page 330
  Indicator Random Variables......Page 333
  The Number of Trials until the First Success......Page 335
  Important Concepts, Formulas, and Theorems......Page 337
  Problems......Page 338
  Expected Number of Items per Location......Page 341
  Expected Number of Empty Locations......Page 342
  Expected Number of Collisions......Page 343
  Expected Maximum Number of Elements in a Location of a Hash Table......Page 346
  Important Concepts, Formulas, and Theorems......Page 351
  Problems......Page 352
  When Running Times Depend on More than Size of Inputs......Page 356
  Conditional Expected Values......Page 358
  Randomized Algorithms......Page 360
  Selection Revisited......Page 362
  QuickSort......Page 364
  A More Careful Analysis of RandomSelect......Page 367
  Important Concepts, Formulas, and Theorems......Page 370
  Problems......Page 371
  Distributions of Random Variables......Page 374
  Variance......Page 377
  Important Concepts, Formulas, and Theorems......Page 385
  Problems......Page 386
 6.1 Graphs......Page 390
  The Degree of a Vertex......Page 394
  Connectivity......Page 396
  Cycles......Page 398
  Other Properties of Trees......Page 399
  Important Concepts, Formulas, and Theorems......Page 402
  Problems......Page 404
  Spanning Trees......Page 406
  Breadth-First Search......Page 408
  Rooted Trees......Page 413
  Important Concepts, Formulas, and Theorems......Page 417
  Problems......Page 418
  Eulerian Tours and Trails......Page 420
  Finding Eulerian Tours......Page 425
  Hamiltonian Paths and Cycles......Page 426
  NP-Complete Problems......Page 432
  Proving That Problems Are NP-Complete......Page 434
  Important Concepts, Formulas, and Theorems......Page 437
  Problems......Page 438
  The Idea of a Matching......Page 441
  Making Matchings Bigger......Page 445
  Searching for Augmenting Paths in Bipartite Graphs......Page 448
  The Augmentation-Cover Algorithm......Page 451
  Efficient Algorithms......Page 457
  Important Concepts, Formulas, and Theorems......Page 458
  Problems......Page 459
  The Idea of Coloring......Page 461
  Interval Graphs......Page 464
  Planarity......Page 466
  The Faces of a Planar Drawing......Page 468
  The Five-Color Theorem......Page 472
  Important Concepts, Formulas, and Theorems......Page 475
  Problems......Page 476
 More General Recurrences......Page 480
 Recurrences for General n......Page 482
 Removing Floors and Ceilings......Page 483
 Proofs of Theorems......Page 484
 Important Concepts, Formulas, and Theorems......Page 488
 Problems......Page 489
APPENDIX B: Answers and Hints to Selected Problems......Page 492
Bibliography......Page 508
 B......Page 510
 C......Page 511
 E......Page 513
 F......Page 514
 H......Page 515
 I......Page 516
 L......Page 517
 M......Page 518
 P......Page 519
 R......Page 521
 S......Page 523
 T......Page 524
 V......Page 525
 Z......Page 526