Discrete Math for Computer Science Students

Contents
1 Counting 1
1.1 Basic Counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
The Sum Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Summing Consecutive Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
The Product Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Two element subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 6
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Counting Lists, Permutations, and Subsets. . . . . . . . . . . . . . . . . . . . . . 9
Using the Sum and Product Principles . . . . . . . . . . . . . . . . . . . . . . . . 9
Lists and functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
The Bijection Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
k-element permutations of a set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Counting subsets of a set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 15
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3 Binomial Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Pascal’s Triangle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
A proof using the Sum Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
The Binomial Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Labeling and trinomial coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 24
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.4 Equivalence Relations and Counting (Optional) . . . . . . . . . . . . . . . . . . . 27
The Symmetry Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
The Quotient Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Equivalence class counting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Multisets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
The bookcase arrangement problem. . . . . . . . . . . . . . . . . . . . . . . . . . 32
The number of k-element multisets of an n-element set. . . . . . . . . . . . . . . 33
Using the quotient principle to explain a quotient . . . . . . . . . . . . . . . . . . 34
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 34
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2 Cryptography and Number Theory 39
2.1 Cryptography and Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . 39
Introduction to Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Private Key Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Public-key Cryptosystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Arithmetic modulo n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Cryptography using multiplication mod n . . . . . . . . . . . . . . . . . . . . . . 47
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 48
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.2 Inverses and GCDs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
Solutions to Equations and Inverses mod n . . . . . . . . . . . . . . . . . . . . . 52
Inverses mod n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Converting Modular Equations to Normal Equations . . . . . . . . . . . . . . . . 55
Greatest Common Divisors (GCD) . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Euclid’s Division Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
The GCD Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Extended GCD algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Computing Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 62
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.3 The RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Exponentiation mod n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
The Rules of Exponents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
Fermat’s Little Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
The RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
The Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 73
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
2.4 Details of the RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
Practical Aspects of Exponentiation mod n . . . . . . . . . . . . . . . . . . . . . 76
How long does it take to use the RSA Algorithm? . . . . . . . . . . . . . . . . . . 77
How hard is factoring? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Finding large primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 81
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3 Reflections on Logic and Proof 83
3.1 Equivalence and Implication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
Equivalence of statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
Truth tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
DeMorgan’s Laws . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
Implication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 92
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.2 Variables and Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Variables and universes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
Standard notation for quantification . . . . . . . . . . . . . . . . . . . . . . . . . 98
Statements about variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Rewriting statements to encompass larger universes . . . . . . . . . . . . . . . . . 100
Proving quantified statements true or false . . . . . . . . . . . . . . . . . . . . . . 101
Negation of quantified statements . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
Implicit quantification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Proof of quantified statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 105
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
3.3 Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
Direct Inference (Modus Ponens) and Proofs . . . . . . . . . . . . . . . . . . . . 108
Rules of inference for direct proofs . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Contrapositive rule of inference. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
Proof by contradiction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 114
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4 Induction, Recursion, and Recurrences 117
4.1 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
Smallest Counter-Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
The Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . 120
Strong Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
Induction in general . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 125
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
4.2 Recursion, Recurrences and Induction . . . . . . . . . . . . . . . . . . . . . . . . 128
Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
First order linear recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
Iterating a recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
Geometric series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
First order linear recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 136
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
4.3 Growth Rates of Solutions to Recurrences . . . . . . . . . . . . . . . . . . . . . . 139
Divide and Conquer Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
Recursion Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
Three Different Behaviors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 148
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
4.4 The Master Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
Master Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
Solving More General Kinds of Recurrences . . . . . . . . . . . . . . . . . . . . . 152
More realistic recurrences (Optional) . . . . . . . . . . . . . . . . . . . . . . . . . 154
Recurrences for general n (Optional) . . . . . . . . . . . . . . . . . . . . . . . . . 155
Appendix: Proofs of Theorems (Optional) . . . . . . . . . . . . . . . . . . . . . . 157
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 159
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.5 More general kinds of recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
Recurrence Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
A Wrinkle with Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Further Wrinkles in Induction Proofs . . . . . . . . . . . . . . . . . . . . . . . . . 165
Dealing with Functions Other Than nc . . . . . . . . . . . . . . . . . . . . . . . . 167
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 171
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
4.6 Recurrences and Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
The idea of selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
A recursive selection algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
Selection without knowing the median in advance . . . . . . . . . . . . . . . . . . 175
An algorithm to find an element in the middle half . . . . . . . . . . . . . . . . . 177
An analysis of the revised selection algorithm . . . . . . . . . . . . . . . . . . . . 179
Uneven Divisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
mportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 182
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
5 Probability 185
5.1 Introduction to Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
Why do we study probability? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
Some examples of probability computations . . . . . . . . . . . . . . . . . . . . . 186
Complementary probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
Probability and hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
The Uniform Probability Distribution . . . . . . . . . . . . . . . . . . . . . . . . 188
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 191
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
5.2 Unions and Intersections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
The probability of a union of events . . . . . . . . . . . . . . . . . . . . . . . . . 194
Principle of inclusion and exclusion for probability . . . . . . . . . . . . . . . . . 196
The principle of inclusion and exclusion for counting . . . . . . . . . . . . . . . . 200
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 201
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
5.3 Conditional Probability and Independence . . . . . . . . . . . . . . . . . . . . . . 204
Conditional Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
Independent Trials Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
Tree diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 212
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
5.4 Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
What are Random Variables? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
Binomial Probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
Expected Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
Expected Values of Sums and Numerical Multiples . . . . . . . . . . . . . . . . . 220
The Number of Trials until the First Success . . . . . . . . . . . . . . . . . . . . 222
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 224
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
5.5 Probability Calculations in Hashing . . . . . . . . . . . . . . . . . . . . . . . . . 227
Expected Number of Items per Location . . . . . . . . . . . . . . . . . . . . . . . 227
Expected Number of Empty Locations . . . . . . . . . . . . . . . . . . . . . . . . 228
Expected Number of Collisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
Expected maximum number of elements in a slot of a hash table (Optional) . . . 230
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 234
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
5.6 Conditional Expectations, Recurrences and Algorithms . . . . . . . . . . . . . . . 237
When Running Times Depend on more than Size of Inputs . . . . . . . . . . . . 237
Conditional Expected Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
Randomized algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
A more exact analysis of RandomSelect . . . . . . . . . . . . . . . . . . . . . . . 245
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 247
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
5.7 Probability Distributions and Variance . . . . . . . . . . . . . . . . . . . . . . . . 251
Distributions of random variables . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
Variance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 258
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
6 Graphs 263
6.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
The degree of a vertex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
Other Properties of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 272
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
6.2 Spanning Trees and Rooted Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
Breadth First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
Rooted Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 283
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
6.3 Eulerian and Hamiltonian Paths and Tours . . . . . . . . . . . . . . . . . . . . . 288
Eulerian Tours and Trails . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
Hamiltonian Paths and Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
NP-Complete Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 297
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
6.4 Matching Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
The idea of a matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
Making matchings bigger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
Matching in Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
Searching for Augmenting Paths in Bipartite Graphs . . . . . . . . . . . . . . . . 306
The Augmentation-Cover algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 307
Good Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 310
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
6.5 Coloring and planarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
The idea of coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
Interval Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
Planarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
The Faces of a Planar Drawing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
The Five Color Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
Iportant Concepts, Formulas, and Theorems . . . . . . . . . . . . . . . . . . . . 323
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324

Another The Core of CS
Download