• Title Notes on Randomized Algorithms
• Author(s) James Aspnes
• Publisher: Arxiv.org and Yale University
• License(s): CC BY-SA 4.0
• Paperback N/A
• eBook PDF (459 pages)
• Language: English
• ISBN-10: N/A
• ISBN-13: N/A
• Share This:  

Book Description

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. Discusses tools from probability theory, including random variables and expectations, union bound arguments, concentration bounds, applications of martingales and Markov chains, and the Lovasz Local Lemma.

Algorithmic topics include analysis of classic randomized algorithms such as Quicksort and Hoare's FIND, randomized tree data structures, hashing, Markov chain Monte Carlo sampling, randomized approximate counting, derandomization, quantum computing, and some examples of randomized distributed algorithms.

• James Aspnes is a professor in the Computer Science Department at Yale. He is also the Director of Undergraduate Studies for the Computer Science department. His main area of research is distributed algorithms.

• Amazon

• Algorithms and Data Structures
• Probability Theory and Stochastic Processes
• Computational Complexity
• Discrete Mathematics

• Notes on Randomized Algorithms (James Aspnes)
• The Mirror Site (1) - PDF (Current Edition)

• The Design of Approximation Algorithms (D. P. Williamson)
• Introduction to Probability, Statistics, and Random Processes
• Lecture Notes for the Algorithms (Jeff Erickson)
• Introduction to Design Analysis of Algorithms (K. Raghava Rao)
• Elementary Algorithms (Xinyu Liu)