You are previewing Randomized Algorithms.
O'Reilly logo
Randomized Algorithms

Book Description

For many applications a randomized algorithm is either the simplest algorithm available, or the fastest, or both. This tutorial presents the basic concepts in the design and analysis of randomized algorithms. The first part of the book presents tools from probability theory and probabilistic analysis that are recurrent in algorithmic applications. Algorithmic examples are given to illustrate the use of each tool in a concrete setting. In the second part of the book, each of the seven chapters focuses on one important area of application of randomized algorithms: data structures; geometric algorithms; graph algorithms; number theory; enumeration; parallel algorithms; and on-line algorithms. A comprehensive and representative selection of the algorithms in these areas is also given. This first book on the subject should prove invaluable as a reference for researchers and professional programmers, as well as for students.

Table of Contents

  1. Cover
  2. Half Title
  3. Title Page
  4. Copyright
  5. Contents
  6. Preface
  7. I: Tools and Techniques
    1. 1. Introduction
      1. 1.1 A Min-Cut Algorithm
      2. 1.2 Las Vegas and Monte Carlo
      3. 1.3 Binary Planar Partitions
      4. 1.4 A Probabilistic Recurrence
      5. 1.5 Computation Model and Complexity Classes
      6. Notes
      7. Problems
    2. 2. Game-Theoretic Techniques
      1. 2.1 Game Tree Evaluation
      2. 2.2 The Minimax Principle
      3. 2.3 Randomness and Non-uniformity
      4. Notes
      5. Problems
    3. 3. Moments and Deviations
      1. 3.1 Occupancy Problems
      2. 3.2 The Markov and Chebyshev Inequalities
      3. 3.3 Randomized Selection
      4. 3.4 Two-Point Sampling
      5. 3.5 The Stable Marriage Problem
      6. 3.6 The Coupon Collector’s Problem
      7. Notes
      8. Problems
    4. 4. Tail Inequalities
      1. 4.1 The Chernoff Bound
      2. 4.2 Routing in a Parallel Computer
      3. 4.3 A Wiring Problem
      4. 4.4 Martingales
      5. Notes
      6. Problems
    5. 5. The Probabilistic Method
      1. 5.1 Overview of the Method
      2. 5.2 Maximum Satisfiability
      3. 5.3 Expanding Graphs
      4. 5.4 Oblivious Routing Revisited
      5. 5.5 The Lovász Local Lemma
      6. 5.6 The Method of Conditional Probabilities
      7. Notes
      8. Problems
    6. 6. Markov Chains and Random Walks
      1. 6.1 A 2-SAT Example
      2. 6.2 Markov Chains
      3. 6.3 Random Walks on Graphs
      4. 6.4 Electrical Networks
      5. 6.5 Cover Times
      6. 6.6 Graph Connectivity
      7. 6.7 Expanders and Rapidly Mixing Random Walks
      8. 6.8 Probability Amplification by Random Walks on Expanders
      9. Notes
      10. Problems
    7. 7. Algebraic Techniques
      1. 7.1 Fingerprinting and Freivalds’ Technique
      2. 7.2 Verifying Polynomial Identities
      3. 7.3 Perfect Matchings in Graphs
      4. 7.4 Verifying Equality of Strings
      5. 7.5 A Comparison of Fingerprinting Techniques
      6. 7.6 Pattern Matching
      7. 7.7 Interactive Proof Systems
      8. 7.8 PCP and Efficient Proof Verification
      9. Notes
      10. Problems
  8. II: Applications
    1. 8. Data Structures
      1. 8.1 The Fundamental Data-structuring Problem
      2. 8.2 Random Treaps
      3. 8.3 Skip Lists
      4. 8.4 Hash Tables
      5. 8.5 Hashing with O(1) Search Time
      6. Notes
      7. Problems
    2. 9. Geometric Algorithms and Linear Programming
      1. 9.1 Randomized Incremental Construction
      2. 9.2 Convex Hulls in the Plane
      3. 9.3 Duality
      4. 9.4 Half-space Intersections
      5. 9.5 Delaunay Triangulations
      6. 9.6 Trapezoidal Decompositions
      7. 9.7 Binary Space Partitions
      8. 9.8 The Diameter of a Point Set
      9. 9.9 Random Sampling
      10. 9.10 Linear Programming
      11. Notes
      12. Problems
    3. 10. Graph Algorithms
      1. 10.1 All-pairs Shortest Paths
      2. 10.2 The Min-Cut Problem
      3. 10.3 Minimum Spanning Trees
      4. Notes
      5. Problems
    4. 11. Approximate Counting
      1. 11.1 Randomized Approximation Schemes
      2. 11.2 The DNF Counting Problem
      3. 11.3 Approximating the Permanent
      4. 11.4 Volume Estimation
      5. Notes
      6. Problems
    5. 12. Parallel and Distributed Algorithms
      1. 12.1 The PRAM Model
      2. 12.2 Sorting on a PRAM
      3. 12.3 Maximal Independent Sets
      4. 12.4 Perfect Matchings
      5. 12.5 The Choice Coordination Problem
      6. 12.6 Byzantine Agreement
      7. Notes
      8. Problems
    6. 13. Online Algorithms
      1. 13.1 The Online Paging Problem
      2. 13.2 Adversary Models
      3. 13.3 Paging against an Oblivious Adversary
      4. 13.4 Relating the Adversaries
      5. 13.5 The Adaptive Online Adversary
      6. 13.6 The k-Server Problem
      7. Notes
      8. Problems
    7. 14. Number Theory and Algebra
      1. 14.1 Preliminaries
      2. 14.2 Groups and Fields
      3. 14.3 Quadratic Residues
      4. 14.4 The RSA Cryptosystem
      5. 14.5 Polynomial Roots and Factors
      6. 14.6 Primality Testing
      7. Notes
      8. Problems
  9. Appendix A: Notational Index
  10. Appendix B: Mathematical Background
  11. Appendix C: Basic Probability Theory
  12. References
  13. Index