Randomized Algorithms

Front Cover
Cambridge University Press, Aug 25, 1995 - Computers - 476 pages
5 Reviews
For many applications, a randomized algorithm is either the simplest or the fastest algorithm available, and sometimes both. This book introduces the basic concepts in the design and analysis of randomized algorithms. The first part of the text presents basic tools such as probability theory and probabilistic analysis that are frequently used in algorithmic applications. Algorithmic examples are also given to illustrate the use of each tool in a concrete setting. In the second part of the book, each chapter focuses on an important area to which randomized algorithms can be applied, providing a comprehensive and representative selection of the algorithms that might be used in each of these areas. Although written primarily as a text for advanced undergraduates and graduate students, this book should also prove invaluable as a reference for professionals and researchers.
  

What people are saying - Write a review

User ratings

5 stars
2
4 stars
2
3 stars
0
2 stars
1
1 star
0

Review: Randomized Algorithms

User Review  - DJ - Goodreads

Nice book on randomized algorithms recommended by Nielsen and chuang, but as Nick mentions, the maths required are still one grad analysis class beyond me Read full review

Review: Randomized Algorithms

User Review  - dead letter office - Goodreads

i'll just say you should be suspicious of any textbook that misspells the author's name on the spine. Read full review

Contents

Introduction
3
GameTheoretic Techniques
28
Moments and Deviations
43
Tail Inequalities
67
The Probabilistic Method
101
Markov Chains and Random Walks
127
Algebraic Techniques
161
Data Structures
197
Approximate Counting
306
Parallel and Distributed Algorithms
335
Online Algorithms
368
Number Theory and Algebra
392
Appendix A Notational Index
429
Basic Probability Theory
438
References
447
Index
467

Geometric Algorithms and Linear Programming
234
Graph Algorithms
278

Common terms and phrases

Popular passages

Page 463 - JP Schmidt, A. Siegel, and A. Srinivasan. Chernoff-Hoeffding bounds for applications with limited independence. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 331-340, 1993.
Page 451 - U. Manber and G. Myers. Suffix arrays: A new method for on-line string searches. In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, pages 319-327, 1990.
Page 452 - KL Clarkson. A Las Vegas algorithm for linear programming when the dimension is small. In Proc. 29th Annu. IEEE Sympos. Found. Comput. Sei., pages 452-456, 1988. [21] KL Clarkson and PW Shor. Applications of random sampling in computational geometry, II.

References to this book

All Book Search results »

About the author (1995)

fm.author_biographical_note1

fm.author_biographical_note2

Bibliographic information