Randomized AlgorithmsPDF电子书下载

Ⅰ Tools and Techniques 1

1 Introduction 3

1.1 A Min-Cut Algorithm 7

1.2 Las Vegas and Monte Carlo 9

1.3 Binary Planar Partitions 10

1.4 A Probabilistic Recurrence 15

1.5 Computation Model and Complexity Classes 16

Notes 23

Problems 25

2 Game-Theoretic Techniques 28

2.1 Game Tree Evaluation 28

2.2 The Minimax Principle 31

2.3 Randomness and Non-uniformity 38

Notes 40

Problems 41

3 Moments and Deviations 43

3.1 Occupancy Problems 43

3.2 The Markov and Chebyshev Inequalities 45

3.3 Randomized Selection 47

3.4 Two-Point Sampling 51

3.5 The Stable Marriage Problem 53

3.6 The Coupon Collector’s Problem 57

Notes 63

Problems 64

4 Tail Inequalities 67

4.1 The Chernoff Bound 67

4.2 Routing in a Parallel Computer 74

4.3 A Wiring Problem 79

4.4 Martingales 83

Notes 96

Problems 97

5 The Probabilistic Method 101

5.1 Overview of the Method 101

5.2 Maximum Satisfiability 104

5.3 Expanding Graphs 108

5.4 Oblivious Routing Revisited 112

5.5 The Lovasz Local Lemma 115

5.6 The Method of Conditional Probabilities 120

Notes 122

Problems 124

6 Markov Chains and Random Walks 127

6.1 A 2-SAT Example 128

6.2 Markov Chains 129

6.3 Random Walks on Graphs 132

6.4 Electrical Networks 135

6.5 Cover Times 137

6.6 Graph Connectivity 139

6.7 Expanders and Rapidly Mixing Random Walks 143

6.8 Probability Amplification by Random Walks on Expanders 151

Notes 155

Problems 156

7 Algebraic Techniques 161

7.1 Fingerprinting and Freivalds’ Technique 162

7.2 Verifying Polynomial Identities 163

7.3 Perfect Matchings in Graphs 167

7.4 Verifying Equality of Strings 168

7.5 A Comparison of Fingerprinting Techniques 169

7.6 Pattern Matching 170

7.7 Interactive Proof Systems 172

7.8 PCP and Efficient Proof Verification 180

Notes 186

Problems 188

Ⅱ Applications 195

8 Data Structures 197

8.1 The Fundamental Data-structuring Problem 197

8.2 Random Treaps 201

8.3 Skip Lists 209

8.4 Hash Tables 213

8.5 Hashing with O（1）Search Time 221

Notes 228

Problems 229

9 Geometric Algorithms and Linear Programming 234

9.1 Randomized Incremental Construction 234

9.2 Convex Hulls in the Plane 236

9.3 Duality 239

9.4 Half-space Intersections 241

9.5 Delaunay Triangulations 245

9.6 Trapezoidal Decompositions 248

9.7 Binary Space Partitions 252

9.8 The Diameter of a Point Set 256

9.9 Random Sampling 258

9.10 Linear Programming 262

Notes 273

Problems 275

10 Graph Algorithms 278

10.1 All-pairs Shortest Paths 278

10.2 The Min-Cut Problem 289

10.3 Minimum Spanning Trees 296

Notes 302

Problems 304

11 Approximate Counting 306

11.1 Randomized Approximation Schemes 308

11.2 The DNF Counting Problem 310

11.3 Approximating the Permanent 315

11.4 Volume Estimation 329

Notes 331

Problems 333

12 Parallel and Distributed Algorithms 335

12.1 The PRAM Model 335

12.2 Sorting on a PRAM 337

12.3 Maximal Independent Sets 341

12.4 Perfect Matchings 347

12.5 The Choice Coordination Problem 355

12.6 Byzantine Agreement 358

Notes 361

Problems 363

13 Online Algorithms 368

13.1 The Online Paging Problem 369

13.2 Adversary Models 372

13.3 Paging against an Oblivious Adversary 374

13.4 Relating the Adversaries 377

13.5 The Adaptive Online Adversary 381

13.6 The k-Server Problem 384

Notes 387

Problems 389

14 Number Theory and Algebra 392

14.1 Preliminaries 392

14.2 Groups and Fields 395

14.3 Quadratic Residues 402

14.4 The RSA Cryptosystem 410

14.5 Polynomial Roots and Factors 412

14.6 Primality Testing 417

Notes 426

Problems 427

Appendix A Notational Index 429

Appendix B Mathematical Background 433

Appendix C Basic Probability Theory 438

References 447

Index 467