Randomized Algorithms.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：7.35M 资料格式：pdf 举报版权申诉

euleri-5184995-4744302543001199352.pdf-第1页.png

第1页 / 共488页

euleri-5184995-4744302543001199352.pdf-第2页.png

第2页 / 共488页

euleri-5184995-4744302543001199352.pdf-第3页.png

第3页 / 共488页

euleri-5184995-4744302543001199352.pdf-第4页.png

第4页 / 共488页

euleri-5184995-4744302543001199352.pdf-第5页.png

第5页 / 共488页

euleri-5184995-4744302543001199352.pdf-第6页.png

第6页 / 共488页

euleri-5184995-4744302543001199352.pdf-第7页.png

第7页 / 共488页

euleri-5184995-4744302543001199352.pdf-第8页.png

第8页 / 共488页

Title Page

Contents

Preface

PART ONE. Tools and Techniques

CHAPTER 1 Introduction

1.1. A Min-Cut Algorithm

1.2. Las Vegas and Monte Carlo

1.3. Binary Planar Partitions

1.4. A Probabilistic Recurrence

1.5. Computation Model and Complexity Classes

1.5.1. RAMs and Turing Machines

1.5.2. Complexity Classes

Notes

Problems

CHAPTER 2 Game-Theoretic Techniques

2.1. Game Tree Evaluation

2.2. The Minimax Principle

2.2.1. Game Theory

2.2.2. Yao's Technique

2.2.3. Lower Bound for Game Tree Evaluation

2.3. Randomness and Non-uniformity

Notes

Problems

CHAPTER 3 Moments and Deviations

3.1. Occupancy Problems

3.2. The Markov and Chebyshev Inequalities

3.3. Randomized Selection

3.4. Two-Point Sampling

3.5. The Stable Marriage Problem

3.6. The Coupon Collector's Problem

3.6.1. An Elementary Analysis

3.6.2. The Poisson Heuristic

3.6.3. A Sharp Threshold

Notes

Problems

CHAPTER 4 Tail Inequalities

4.1. The Chernoff Bound

4.2. Routing in a Parallel Computer

4.3. A Wiring Problem

4.4. Martingales

4.4.1. A Simple Definition

4.4.2. A General Definition

4.4.3. Martingale Tail Inequalities

Problems

CHAPTER 5 The Probabilistic Method

5.1. Overview of the Method

5.2. Maximum Satisfiability

5.3. Expanding Graphs

5.3.1. Probability Amplification

5.4. Oblivious Routing Revisited

5.5. The Lovasz Local Lemma

5.6. The Method of Conditional Probabilities

Problems

CHAPTER 6 Markov Chains and Random Walks

6.1. A 2-SAT Example

6.2. Markov Chains

6.3. Random Walks on Graphs

6.4. Electrical Networks

6.5. Cover Times

6.6. Graph Connectivity

6.6.1. Undirected Graphs

6.6.2. Directed Graphs

6.7. Expanders and Rapidly Mixing Random Walks

6.7.1. Expanders and Eigenvalues

6.7.2. Random Walks on Expanders

6.8. Probability Amplification by Random Walks on Expanders

Problems

CHAPTER 7 Algebraic Techniques

7.1. Fingerprinting and Freivalds' Technique

7.2. Verifying Polynomial Identities

7.3. Perfect Matchings in Graphs

7.4. Verifying Equality of Strings

7.5. A Comparison of Fingerprinting Techniques

7.6. Pattern Matching

7.7. Interactive Proof Systems

7.7.1. Verifying Graph Non-Isomorphism

7.7.2. The Class IP and #3SAT

7.7.3. Arithmetization of Satisfiability

7.7.4. The Interactive Proof System for #3SAT

7.8. PCP and Efficient Proof Verification

7.8.1. Arithmetization Revisited

7.8.2. A Proof of Satisfiability

7.8.3. The Verification

Notes

Problems

PART TWO. Applications

CHAPTER 8 Data Structures

8.1. The Fundamental Data-structuring Problem

8.2. Random Treaps

8.2.1. Mulmuley Games

8.2.2. Analysis of Treaps

8.3. Skip Lists

8.4. Hash Tables

8.4.1. Universal Hash Families

8.4.2. Application to Dynamic Dictionaries

8.4.3. Constructing Universal Hash Families

8.4.4. Strongly Universal Hash Families

8.5. Hashing with 0 (1 ) Search Time

8.5.1. Nearly Perfect Hash Families

8.5.2. Achieving Bounded Query Time

Problems

CHAPTER 9 Geometric Algorithms and LinearProgramming

9.1. Randomized Incremental Construction

9.2. Convex Hulls in the Plane

9.3. Duality

9.4. Half-space Intersections

9.5. Delaunay Triangulations

9.6. Trapezoidal Decompositions

9.7. Binary Space Partitions

9.8. The Diameter of a Point Set

9.9. Random Sampling

9.10. Linear Programming

Problems

CHAPTER 10 Graph Algorithms

10.1. All-pairs Shortest Paths

10.2. The Min-Cut Problem

10.3. Minimum Spanning Trees

Notes

Problems

CHAPTER 11 Approximate Counting

11.1. Randomized Approximation Schemes

11.2. The DNF Counting Problem

11.3. Approximating the Permanent

11.4. Volume Estimation

Notes

Problems

CHAPTER 12 Parallel and Distributed Algorithms

12.1. The PRAM Model

12.2. Sorting on a PRAM

12.3. Maximal Independent Sets

12.4. Perfect Machings

12.5. The Choice Coordination Problem

12.6. Byzantine Agreement

Notes

Problems

CHAPTER 13 Online Algorithms

13.1. The Online Paging Problem

13.2. Adversary Models

13.3. Paging against an Oblivious Adversary

13.4. Relating the Adversaries

13.5. The Adaptive Online Adversary

13.6. The k-Server Problem

Notes

Problems

CHAPTER 14 Num ber Theory and Algebra

14.1. Preliminaries

14.2. Groups and Fields

14.3. Quadratic Residues

14.4. The RSA Cryptosystem

14.5. Polynomial Roots and Factors

14.6. Primality Testing

Notes

Problems

APPENDIX A. Notational Index

APPENDIX B. Mathematical Background

Notation for Asymptotics

Combinatorial Inequalities

Linear Algebra

APPENDIX C. Basic Probability Th1eory

References

Index

Randomized Algorithms Rajeev Motwani Stanford University Raghavan Prabhakar IBM Thomas J. Watson Center Research I :i ..... CAMBRIDGE UNIVERSITY PRESS

by the Press Syndicate Published The Pitt Building, 40 West 20th Street, New York, NY 10011-4211, USA 10 Stamford Road, Oakleigh, Melbourne 3166, Australia of the University Street, Cambridge CB2 1RP Trumpington of Cambridge © Cambridge University Press 1995 First published 1995 Printed in United States of America Library of Congress Cataloguing-in-Publication Data Motwani, Rajeev. Randomized ·algorithms / Rajeev Motwani, Prabhakar Raghavan. p. em. Includes bibliographical references �.SBN 0-521-47465-5 1. Stochastic processes-Data processing. and index. 2. Algorithms. I. Raghavan, Prabhakar. II. Title. QA274.M68 1995 004'.01'5192-dc20 94-44271 A catalog record for this book is available from the British Library. ISBN 0-521-47465-5 hardback TAG

Randomized Algorithms

The Stanford-Cambridge Program is an between ing from the collaboration University and its Press. innovative publishing venture result Cambridge University Press and Stanford Cambridge University Press publishes and distributes books in the Stanford Cambridge Program throughout the world. The Program provides a new international imprint . Drawing for the teaching on Stanford's eminent and of pure and applied communication faculty and associated quality of teaching and research sciences books within the Program at Stanford University. at undergraduate sciences. graphs, across a broad range of the institutions, reflect the high The Program includes textbooks level, and research mono

Contents Preface I Tools and Techniques 1 Introduction Planar 1.1 A Min-Cut Algorithm 1.2 Las Vegas and Monte Carlo 1.3 Binary 1.4 A Probabilistic 1.5 Computation Notes Problems Partitions Recurrence Model and Complexity Classes 2 Game-Theoretic Techniques 2.1 Game Tree Evaluation 2.2 The Minimax 2.3 Randomness Notes Problems Principle and Non-unif ormity 3 Moments and Deviations Problems IX 1 3 7 9 10 15 16 23 25 28 28 31 38 40 41 43 43 Selection 3.1 Occupancy 3.2 The Markov and Chebyshev 3.3 Randomized 3.4 Two-Point 3.5 The Stable 3.6 The Coupon Notes Problems Sampling Problem Marriage Collector's Problem Inequalities 45 47 51 53 57 63 64 67 67 4.1 The Chernoff Bound 4 Tail Inequalities v

C ON T EN T S in a Parallel Computer 4.2 Routing 4.3 A Wiring Problem 4.4 Martingales Notes Problems 5 The Probabilistic Method 5.1 Overview of the Method 5.2 Maximum Satisfiability 5.3 Expanding Graphs 5.4 Oblivious Routing Revisited 5.5 The Lovasz Local Lemma 5.6 The Method of Conditional Notes Problems Probabilities 6 Markov Chains and Random Walks 74 79 83 96 97 101 101 104 108 112 115 120 122 124 127 Networks 6.1 A 2-SAT Example 6.2 Markov Chains 6.3 Random Walks on Graphs 6.4 Electrical 6.5 Cover Times 6.6 Graph Connectivity and Rapidly 6.7 Expanders 6.8 Probability Amplification Notes Problems 128 129 132 135 137 139 143 by Random Walks on Expanders 151 155 156 Mixing Random Walks 7 Algebraic Techniques Technique Equality Identities Polynomial 7.1 Fingerprinting and Freivalds' 7.2 Verifying in Graphs 7.3 Perfect Matchings 7.4 Verifying of Strings 7.5 A Comparison 7.6 Pattern Matching 7.7 Interactive 7.8 PCP and Efficient Proof Verification Notes Problems Proof Systems of Fingerprinting Techniques II Applications 8 I>ata Structures 8.1 The Fundamental Data-structuring Problem vi 161 162 163 167 168 169 170 172 180 186 188 195 197 197

C O N TE N TS 8.2 Random Treaps 8.3 Skip Lists 8.4 Hash Tables 8.5 Hashing with 0( 1) Search Time Notes Problems 9 Geometric Algorithms and Linear Programming Construction Intersections Triangulations Decompositions 9.1 Randomized Incremental 9.2 Convex Hulls in the Plane 9.3 Duality 9.4 Half-space 9.5 Delaunay 9.6 Trapezoidal 9.7 Binary Space Partitions 9.8 The Diameter 9.9 Random Sampling 9.10 Linear Programming Notes Problems of a Point Set 10 Graph Algorithms Shortest Paths 10.1 All-pairs 10.2 The Min-Cut Problem 10.3 Minimum Spanning Trees Notes Problems 1 1 Approximate Counting Approximation Schemes 11.1 Randomized 11.2 The DNF Counting Problem 11.3 Approximating the Permanent 11.4 Volume Estimation Notes Problems 12 Parallel and Distributed Algorithms 12.1 The PRAM Model 12.2 Sorting on a PRAM 12.3 Maximal Independent 12.4 Perfect Matchings 12.5 The Choice Coordination 12.6 Byzantine Agreement Notes Problems Problem Sets vii 201 209 213 221 228 229 234 234 236 239 241 245 248 252 256 258 262 273 275 278 278 289 296 302 304 306 308 310 315 329 331 333 335 335 337 341 347 355 358 361 363

分享到：

赞收藏

资料库

Randomized Algorithms.pdf

相关推荐

课程资源

热门标签

最新资料