Algorithms Appendix

A.1 Polynomials......Page 1
A.2 Alternate Representations......Page 3
A.3 Converting btw Representations......Page 4
A.4 Divide & Conquer......Page 6
A.5 The Discrete Fourier Transform......Page 7
A.6 More General Factoring......Page 9
A.7 Inverting the FFT......Page 11
A.8 Fast Polynomial Multiplication......Page 12
A.9 Inside the Radix-2 FFT......Page 13
Exercises......Page 14
Faster Exponential Algorithms......Page 18
B.1 3Sat......Page 19
B.2 Maximum Independent Set......Page 25
B.3 Dynamic Programming......Page 28
Exercises......Page 30
C.2 NFA Acceptance......Page 32
C.4 CFG Parsing......Page 35
D.1 Saving Space - Divide & Conquer......Page 38
D.2 Saving Time - Sparseness......Page 40
D.3 Saving Time - Monotonicity......Page 43
D.4 Saving Time - more Monotoniticy......Page 44
D.5 Saving more Time - Total Monotonicity......Page 46
D.6 The SMAWK algorithm......Page 48
D.7 Using SMAWK......Page 51
Exercises......Page 53
E.1 Definitions......Page 56
E.2 Scheduling with Deadlines......Page 60
Exercises......Page 62
F.1 Unbalanced Flows......Page 64
F.2 Reduction to Maximum Flow......Page 65
F.3 Pseudoflows......Page 67
F.4 Variations on a Theme......Page 69
F.5 Push-Relabel......Page 71
Exercises......Page 74
G.1 Minimum-Cost Circulations......Page 76
G.2 Successive Shortest Paths......Page 79
G.3 Node Potentials & Reduced Costs......Page 82
G.4 Transshipment & Transportation......Page 85
Exercises......Page 88
H.1 Introduction......Page 91
H.2 Geometry of Linear Programming......Page 93
H.3 Examples......Page 95
H.4 Linear Programming Duality......Page 98
H.5 The Fundamental Theorem......Page 101
H.6 Another Duality Example......Page 102
H.7 Strong Duality......Page 104
H.8 Complementary Slackness......Page 106
Exercises......Page 107
Linear Programming Algorithms......Page 112
Bases, Feasibility & Local Optimality......Page 113
The Simplex Algorithm......Page 114
Computing the Initial Basis......Page 116
Network Simplex......Page 118
Linear Expected Time for Fixed Dimensions......Page 121
Exercises......Page 123
J.1 Load Balancing......Page 127
J.3 Greedy Vertex Cover......Page 130
J.4 Set Cover & Hitting Set......Page 132
J.6 Lightest Vertex Cover - LP Rounding......Page 133
J.7 Randomized LP Rounding......Page 135
J.8 Traveling Salesman - Bad News......Page 136
J.9 Traveling Salesman - Good News......Page 137
J.10 k-center Clustering......Page 139
J.11 Approximation Schemes......Page 141
J.12 FPTAS for Subset Sum......Page 142
Exercises......Page 145