Randomized AlgorithmsPDF|Epub|txt|kindle电子书版本网盘下载

Randomized AlgorithmsPDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

Ⅰ 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

13 Online 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

14 Number 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