Discrete Mathematics for Computer Scientists

Cover......Page 1
Title Page......Page 4
Copyright......Page 5
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