More Algorithms

Discrete Probability Spaces......Page 1
Random Variables......Page 5
Common Probability Distributions......Page 8
Coin Flips......Page 9
Pokémon Collecting......Page 11
Random Permutations......Page 13
Exercises......Page 15
Deterministic vs Randomized Algorithms......Page 23
Back to Nuts & Bolts......Page 24
Finding all Matches......Page 25
Recursive Analysis......Page 26
Iterative Analysis......Page 27
Masochistic Analysis......Page 29
Exercises......Page 30
Treaps......Page 36
Skip Lists......Page 41
Exercises......Page 45
Markov Inequality......Page 50
Independence......Page 51
Chebyshev Inequality......Page 52
Chernoff Bounds......Page 53
Coin Flips......Page 55
Back to Treaps 1......Page 56
Back to Treaps 2......Page 57
Exercises......Page 59
Introduction......Page 60
But Not Too Random......Page 61
Chaining......Page 63
Multiplicative Hashing......Page 64
High Probability Bounds - Balls & Bins......Page 69
Perfect Hashing......Page 70
Open Addressing......Page 71
Linear and Binary Probing......Page 72
Analysis of Binary Probing......Page 73
Exercises......Page 76
Bloom Filters......Page 78
False Positive Rate......Page 79
The Count-Min Sketch......Page 80
Estimating Distinct Items......Page 81
Exercises......Page 82
Brute Force......Page 84
Strings as Numbers......Page 85
Karp-Rabin Fingerprinting......Page 86
Random Prime Numbers......Page 87
Redundant Comparisons......Page 88
Finite State Machines......Page 89
Computing the Failure Function......Page 91
Optimizing the Failure Function......Page 93
Exercises......Page 95
Setting up the Problem......Page 98
Blindly Guessing......Page 99
Blindly Guessing over & over......Page 100
Not-So-Blindly Guessing......Page 101
Solving the Karger-Stein Recurrence......Page 102
Exercises......Page 103
Incrementing a Binary Counter......Page 105
Counting from 0 to n......Page 106
Incrementing & Decrementing......Page 109
Gray Codes......Page 110
Exercises......Page 111
Definitions......Page 119
Insertions - Partial Rebuilding......Page 120
Splay Trees......Page 122
Other Optimality Properties......Page 124
Splay Tree Conjectures......Page 126
Refs......Page 127
Exercises......Page 128
Reversed Trees......Page 134
Shallow Threaded Trees......Page 135
Path Compression......Page 137
Amortized Time......Page 139
Turning the Crank......Page 141
Ackermann Function & its Inverse......Page 143
Exercises......Page 144
Huh? Whuzzat?......Page 148
Decision Trees......Page 149
But wait a second. . .......Page 150
Finding the Maximum & Adversaries......Page 151
Exercises......Page 152
n-Card Monte......Page 154
Finding Patterns in Bit Strings......Page 155
Connectedness Is Evasive......Page 156
Evasive Conjecture......Page 157
Finding the Median......Page 158
Exercises......Page 159
1 Prime Divisors - Proof by Smallest Counterexample......Page 162
2 Axiom of Induction......Page 166
3 Stamps & Recursion......Page 167
4 More on Prime Divisors......Page 170
5 Summations......Page 171
6 Tiling with Triominos......Page 173
7 Binary Numbers Exist......Page 176
9 Fibonacci Parity......Page 179
11 Trees......Page 180
Exercises......Page 182
1 Introduction......Page 192
Tower of Hanoi......Page 193
Fibonacci numbers......Page 194
Mergesort......Page 195
An uglier divide-and-conquer example......Page 196
3 Divide & Conquer Recurrences (Recursion Trees)......Page 197
4 The Nuclear Bomb......Page 201
Operators......Page 203
Annihilators......Page 205
Annihilating Recurrences......Page 206
6 Transformations......Page 208
Exercises......Page 211