《Randomized Algorithms》求取 ⇩

ⅠTools and Techniques1

1Introduction3

1.1 A Min-Cut Algorithm7

1.2 Las Vegas and Monte Carlo9

1.3 Binary Planar Partitions10

1.4 A Probabilistic Recurrence15

1.5Computation Model and Complexity Classes16

Notes23

Problems25

2Game-Theoretic Techniques28

2.1 Game Tree Evaluation28

2.2 The Minimax Principle31

2.3Randomness and Non-uniformity38

Notes40

Problems41

3Moments 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

4Tail Inequalities67

4.1 The Chernoff Bound67

4.2 Routing in a Parallel Computer74

4.3 A Wiring Problem79

4.4Martingales83

Notes96

Problems97

5The 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.6The Method of Conditional Probabilities120

Notes122

Problems124

6Markov 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.8Probability Amplification by Random Walks on Expanders151

Notes155

Problems156

7Algebraic 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.8PCP and Efficient Proof Verification180

Notes186

Problems188

Ⅱ Applications195

8Data Structures197

8.1 The Fundamental Data-structuring Problem197

8.2 Random Treaps201

8.3 Skip Lists209

8.4 Hash Tables213

8.5Hashing with O（1）Search Time221

Notes228

Problems229

9Geometric 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

10Graph Algorithms278

10.1 All-pairs Shortest Paths278

10.2 The Min-Cut Problem289

10.3 Minimum Spanning Trees296

Notes302

Problems304

11Approximate Counting306

11.1 Randomized Approximation Schemes308

11.2 The DNF Counting Problem310

11.3 Approximating the Permanent315

11.4 Volume Estimation329

Notes331

Problems333

12Parallel 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

13Online Algorithms368

13.1 The Online Paging Problem369

13.2 Adversary Models372

13.3 Paging against an Oblivious Adversary374

13.4 Relating the Adversaries377

13.5 The Adaptive Online Adversary381

13.6 The k-Server Problem384

Notes387

Problems389

14Number Theory and Algebra392

14.1 Preliminaries392

14.2 Groups and Fields395

14.3 Quadratic Residues402

14.4 The RSA Cryptosystem410

14.5 Polynomial Roots and Factors412

14.6 Primality Testing417

Notes426

Problems427

Appendix A Notational Index429

Appendix B Mathematical Background433

Appendix C Basic Probability Theory438

References447

Index467