Discrete Mathematics for Computer Scientists

Clifford Stein is a Professor of IEOR at Columbia University. He also holds an appointment in the Department of Computer Science. He is the director of Undergraduate Programs for the IEOR Department. Prior to joining Columbia, he spent 9 years as an Assistant and Associate Professor in the Dartmouth College Department of Computer Science.

His research interests include the design and analysis of algorithms, combinatorial optimization, operations research, network algorithms, scheduling, algorithm engineering and computational biology. Professor Stein has published many influential papers in the leading conferences and journals in his field, and has occupied a variety of editorial positions including the journals ACM Transactions on Algorithms, Mathematical Programming, Journal of Algorithms, SIAM Journal on Discrete Mathematics and Operations Research Letters. His work has been supported by the National Science Foundation and Sloan Foundation. He is the winner of several prestigious awards including an NSF Career Award, an Alfred Sloan Research Fellowship and the Karen Wetterhahn Award for Distinguished Creative or Scholarly Achievement. He is also the co-author of two textbooks: Discrete Math for Computer Science with Scot Drysdale and Introduction to Algorithms, with T. Cormen, C. Leiserson and R. Rivest—the best-selling textbook in algorithms, which has been translated into 8 languages.

(Robert L.) Scot Drysdale, III is a professor of Computer Science at Dartmouth College and served as Chair of the Computer Science department for eight years. His main research area is algorithms, primarily computational geometry. He is best known for papers describing algorithms for computing variants of a geometric structure called the Voronoi Diagram and algorithms that use the Voronoi Diagram to solve other problems in computational geometry. He has also developed algorithms for planning and testing the correctness of tool path movements in Numerical Control (NC) machining. His work has been supported by grants from the National Science Foundation and Ford Motor Company and he was awarded a Fulbright Fellowship.

He has also made contributions to education. He is a winner of the Dartmouth Distinguished Teaching award. He was a member of the development committee for the AP exam in computer science for four years during its transition from C++ to Java and then chaired the committee for three years. He has been Principal Lecturer for DIMACS and NSF workshops and was co-director of a DIMACS institute. He was a faculty member of the ACM/MAA Institute for Retraining in Computer Science for five years.

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
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
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
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
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
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
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
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
Matching in Bipartite Graphs 417
Searching for Augmenting Paths in Bipartite Graphs 417
The Augmentation-Cover Algorithm 420
Efficient Algorithms 426
Important Concepts, Formulas, and Theorems 427
Problems 428
6.5 Coloring and Planarity 430
The Idea of Coloring 430
Interval Graphs 433
Planarity 435
The Faces of a Planar Drawing 437
The Five-Color Theorem 441
Important Concepts, Formulas, and Theorems 444
Problems 445

APPENDIX A Derivation of the More General Master Theorem 449
More General Recurrences 449
Recurrences for General n 451
Removing Floors and Ceilings 452
Floors and Ceilings in the Stronger Version of the Master Theorem 453
Proofs of Theorems 453
Important Concepts, Formulas, and Theorems 457
Problems 458
APPENDIX B Answers and Hints to Selected Problems 461
Bibliography 477
Index 479