《RANDOMIZED ALGORITHMS》

Ⅰ Tools and Techniques1

1 Introduction3

1.1 A Min-Cut Algorithm7

1.2 Las Vegas and Monte Carlo9

1.3 Binary Planar Partitions10

1.4 A Probabilistic Recurrence15

1.5 Computation Model and Complexity Classes16

Notes23

Problems25

2 Game-Theoretic Techniques28

2.1 Game Tree Evaluation28

2.2 The Minimax Principle31

2.3 Randomness and Non-uniformity38

Notes40

Problems41

3 Moments and Deviations43

3.1 Occupancy Problems43

3.2 The Markov and Chebyshev Inequalities45

3.3 Randomized Selection47

3.4 Two-Point Sampling51

3.5 The Stable Marriage Problem53

3.6 The Coupon Collector's Problem57

Notes63

Problems64

4 Tail Inequalities67

4.1 The Chernoff Bound67

4.2 Routing in a Parallel Computer74

4.3 A Wiring Problem79

4.4 Martingales83

Notes96

Problems97

5 The Probabilistic Method101

5.1 Overview of the Method101

5.2 Maximum Satisfiability104

5.3 Expanding Graphs108

5.4 Oblivious Routing Revisited112

5.5 The Lovasz Local Lemma115

5.6 The Method of Conditional Probabilities120

Notes122

Problems124

6 Markov Chains and Random Walks127

6.1 A 2-SAT Example128

6.2 Markov Chains129

6.3 Random Walks on Graphs132

6.4 Electrical Networks135

6.5 Cover Times137

6.6 Graph Connectivity139

6.7 Expanders and Rapidly Mixing Random Walks143

6.8 Probability Amplification by Random Walks on Expanders151

Notes155

Problems156

7 Algebraic Techniques161

7.1 Fingerprinting and Freivalds' Technique162

7.2 Verifying Polynomial Identities163

7.3 Perfect Matchings in Graphs167

7.4 Verifying Equality of Strings168

7.5 A Comparison of Fingerprinting Techniques169

7.6 Pattern Matching170

7.7 Interactive Proof Systems172

7.8 PCP and Efficient Proof Verification180

Notes186

Problems188

Ⅱ Applications195

8 Data Structures197

8.1 The Fundamental Data-structuring Problem197

8.2 Random Treaps201

8.3 Skip Lists209

8.4 Hash Tables213

8.5 Hashing with O(1) Search Time221

Notes228

Problems229

9 Geometric Algorithms and Linear Programming234

9.1 Randomized Incremental Construction234

9.2 Convex Hulls in the Plane236

9.3 Duality239

9.4 Half-space Intersections241

9.5 Delaunay Triangulations245

9.6 Trapezoidal Decompositions248

9.7 Binary Space Partitions252

9.8 The Diameter of a Point Set256

9.9 Random Sampling258

9.10 Linear Programming262

Notes273

Problems275

10 Graph Algorithms278

10.1 All-pairs Shortest Paths278

10.2 The Min-Cut Problem289

10.3 Minimum Spanning Trees296

Notes302

Problems304

11 Approximate Counting306

11.1 Randomized Approximation Schemes308

11.2 The DNF Counting Problem310

11.3 Approximating the Permanent315

11.4 Volume Estimation329

Notes331

Problems333

12 Parallel and Distributed Algorithms335

12.1 The PRAM Model335

12.2 Sorting on a PRAM337

12.3 Maximal Independent Sets341

12.4 Perfect Matchings347

12.5 The Choice Coordination Problem355

12.6 Byzantine Agreement358

Notes361

Problems363