Algorithms

About These Notes......Page 3
0.1 What is an algorithm?......Page 7
0.2 A Few Simple Examples......Page 8
0.3 Writing down algorithms......Page 11
0.4 Analyzing algorithms......Page 12
0.5 A Longer Example: Stable Matching......Page 14
Exercises......Page 20
1.1 Simplify and delegate......Page 22
1.2 Tower of Hanoi......Page 23
1.3 MergeSort......Page 24
1.4 Quicksort......Page 26
1.5 The Pattern......Page 27
1.6 Median Selection......Page 28
1.7 Multiplication......Page 29
1.8 Exponentiation......Page 31
Exercises......Page 32
2.1 Polynomials......Page 40
2.2 Alternate Representations......Page 41
2.3 Converting Between Representations......Page 42
2.4 Divide and Conquer......Page 44
2.5 The Discrete Fourier Transform......Page 45
2.6 Inverting the FFT......Page 46
2.7 Fast Multiplication......Page 47
Exercises......Page 48
3.1 n Queens......Page 49
3.2 Subset Sum......Page 50
3.3 Longest Increasing Subsequence......Page 52
3.4 Optimal Binary Search Trees......Page 53
Exercises......Page 55
4.1 3SAT......Page 57
4.2 Maximum Independent Set......Page 60
Exercises......Page 62
5.1 Fibonacci Numbers......Page 63
5.2 Longest Increasing Subsequence......Page 66
5.3 The Pattern: Smart Recursion......Page 68
5.5 Edit Distance......Page 69
5.6 Optimal Binary Search Trees......Page 73
5.7 Dynamic Programming on Trees......Page 75
Exercises......Page 77
6.1 Saving Space: Divide and Conquer......Page 89
6.2 Saving Time: Sparseness......Page 90
6.3 Saving Time: Monotonicity......Page 92
Exercises......Page 93
7.1 Storing Files on Tape......Page 95
7.2 Scheduling Classes......Page 96
7.4 Huffman Codes......Page 99
Exercises......Page 103
8.1 Definitions......Page 107
8.2 Scheduling with Deadlines......Page 110
Exercises......Page 111
9.2 Deterministic vs. Randomized Algorithms......Page 113
9.3 Back to Nuts and Bolts......Page 114
9.4 Finding All Matches......Page 115
9.5 Reductions to and from Sorting......Page 116
9.7 Iterative Analysis......Page 117
9.8 Masochistic Analysis
......Page 119
Exercises......Page 121
10.1 Treaps......Page 128
10.2 Skip Lists......Page 133
Exercises......Page 136
11.1 Markov’s Inequality......Page 140
11.3 Chernoff Bounds......Page 141
11.4 Back to Treaps......Page 142
Exercises......Page 144
12.2 Chaining......Page 145
12.3 Universal Hashing......Page 147
12.4 High Probability Bounds: Balls and Bins
......Page 148
12.5 Perfect Hashing......Page 150
12.6 Open Addressing......Page 151
Exercises......Page 153
13.1 Setting Up the Problem......Page 154
13.2 Blindly Guessing......Page 155
13.4 Not-So-Blindly Guessing......Page 156
13.5 Solving the Karger/Stein recurrence
......Page 158
Exercises......Page 159
14.2 Counting from 0 to n......Page 160
14.3 Incrementing and Decrementing......Page 163
14.4 Gray Codes
......Page 164
Exercises......Page 165
15.1 Definitions......Page 169
15.3 Insertions: Partial Rebuilding......Page 170
15.4 Scapegoat Trees......Page 171
15.6 Splay Trees......Page 172
15.7 Other Optimality Properties
......Page 174
15.8 Splay Tree Conjectures
......Page 176
Exercises......Page 177
16.1 Reversed Trees......Page 181
16.2 Shallow Threaded Trees......Page 182
16.3 Path Compression......Page 184
16.4 O(log*n) Amortized Time
......Page 185
16.5 Turning the Crank
......Page 188
16.6 The Ackermann Function and its Inverse
......Page 189
16.7 To infinity. . . and beyond!......Page 190
Exercises......Page 191
17.1 Definitions......Page 193
17.2 Abstract Representations and Examples......Page 194
17.3 Graph Data Structures......Page 196
17.4 Traversing connected graphs......Page 197
17.5 Examples......Page 198
17.6 Searching disconnected graphs......Page 199
Exercises......Page 200
18.2 The Only Minimum Spanning Tree Algorithm......Page 204
18.3 Boruvka’s Algorithm
......Page 206
18.4 Jarník’s (‘Prim’s’) Algorithm
......Page 207
18.6 Kruskal’s Algorithm......Page 208
Exercises......Page 210
19.1 Introduction......Page 213
19.2 Warning!......Page 214
19.3 The Only SSSP Algorithm......Page 215
19.5 The A* Heuristic
......Page 216
19.6 Shimbel’s Algorithm (‘Bellman-Ford’)......Page 217
19.7 Shimbel’s Algorithm as Dynamic Programming......Page 219
Exercises......Page 220
20.2 Lots of Single Sources......Page 224
20.4 Johnson’s Algorithm......Page 225
20.5 Dynamic Programming......Page 226
20.7 Aside: ‘Funny’ Matrix Multiplication......Page 228
20.8 Floyd and Warshall’s Algorithm......Page 229
Exercises......Page 231
21: Maximum Flows and Minimum Cuts
......Page 234
21.1 Flows......Page 235
21.3 The Max-Flow Min-Cut Theorem......Page 236
Exercises......Page 238
22.1 Ford-Fulkerson augmenting path......Page 240
22.2 Edmonds-Karp: Fat Pipes......Page 241
22.3 Dinits/Edmonds-Karp: Short Pipes......Page 242
22.5 Further Progress......Page 243
Exercises......Page 244
23.2 Vertex Capacities and Vertex-Disjoint Paths......Page 246
23.3 Maximum Matchings in Bipartite Graphs......Page 247
23.5 Baseball Elimination......Page 248
23.6 Project Selection......Page 250
Exercises......Page 252
18.1 Maximum Flows with Edge Demands
......Page 256
18.2 Node Supplies and Demands......Page 258
18.3 Minimum-Cost Flows......Page 259
18.4 Maximum-Weight Matchings......Page 260
Exercises......Page 262
25: Linear Programming
......Page 264
25.1 The Geometry of Linear Programming......Page 265
25.2 Example 1: Shortest Paths......Page 267
25.4 Linear Programming Duality......Page 268
25.5 Duality Example......Page 269
25.6 Strong Duality......Page 270
Exercises......Page 272
26.1 Bases, Feasibility, and Local Optimality......Page 274
26.2 The Primal Simplex Algorithm: Falling Marbles......Page 275
26.4 Computing the Initial Basis......Page 276
26.5 Linear Expected Time for Fixed Dimensions......Page 278
Exercises......Page 279
27.1 Huh? Whuzzat?......Page 282
27.2 Decision Trees......Page 283
27.4 But wait a second. . .......Page 284
27.6 Finding the Maximum and Adversaries......Page 285
Exercises......Page 286
28.2 n-Card Monte......Page 288
28.3 Finding Patterns in Bit Strings......Page 289
28.5 Connectedness Is Evasive......Page 290
28.6 An Evasive Conjecture......Page 291
28.8 Finding the Median
......Page 292
Exercises......Page 293
29.1 ‘Efficient’ Problems......Page 296
29.3 NP-hard, NP-easy, and NP-complete......Page 297
29.4 Formal Definition (HC SVNT DRACONES)
......Page 298
29.5 Reductions and SAT......Page 299
29.6 3SAT (from SAT)
......Page 301
29.7 Maximum Independent Set (from 3SAT)......Page 302
29.8 Clique (from Independent Set)......Page 303
29.10 Graph Coloring (from 3SAT)......Page 304
29.11 Hamiltonian Cycle (from Vertex Cover)......Page 306
29.12 Subset Sum (from Vertex Cover)......Page 307
29.13 Other Useful NP-hard Problems......Page 308
29.14 On Beyond Zebra
......Page 310
Exercises......Page 312
30.1 Load Balancing......Page 319
30.3 Greedy Vertex Cover......Page 321
30.4 Set Cover and Hitting Set......Page 322
30.5 Vertex Cover, Again......Page 323
30.7 Traveling Salesman: The Good News......Page 324
30.8 k-center Clustering......Page 326
30.9 Approximation Schemes
......Page 327
30.10 An FPTAS for Subset Sum
......Page 328
Exercises......Page 331
Appendix I: Proof by Induction......Page 335
Appendix II: Solving Recurrences......Page 354
Homeworks-Exams-Finals
......Page 375