Notes on Randomized Algorithms
by James Aspnes
DescriptionTable of ContentsDetailsHashtagsReport an issue 
Book Description
Lecture notes for the Yale Computer Science course CPSC 469/569 Randomized Algorithms. Suitable for use as a supplementary text for an introductory graduate or advanced undergraduate course on 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 Lovász 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.This open book is licensed under a Creative Commons License (CC BY-SA). You can download Notes on Randomized Algorithms ebook for free in PDF format (3.3 MB).
Table of Contents
Chapter 1
Randomized algorithms
Chapter 2
Probability theory
Chapter 3
Random variables
Chapter 4
Basic probabilistic inequalities
Chapter 5
Concentration bounds
Chapter 6
Randomized search trees
Chapter 7
Hashing
Chapter 8
Martingales and stopping times
Chapter 9
Markov chains
Chapter 10
Approximate counting
Chapter 11
The probabilistic method
Chapter 12
Derandomization
Chapter 13
Quantum computing
Chapter 14
Randomized distributed algorithms
Book Details
Title
Notes on Randomized Algorithms
Subject
Computer Science
Publisher
Self-publishing
Published
2020
Pages
459
Edition
1
Language
English
PDF Size
3.3 MB
License
Related Books
This book constitutes the refereed proceedings of the 31st International Symposium on Computer and Information Sciences, ISCIS 2016, held in Krakow, Poland, in October 2016.
The 29 revised full papers presented were carefully reviewed and selected from 65 submissions. The papers are organized in topical sections on smart algorithms; data classific...
This book bridges the gap between playing with robots in school and studying robotics at the upper undergraduate and graduate levels to prepare for careers in industry and research. Robotic algorithms are presented formally, but using only mathematics known by high-school and first-year college students, such as calculus, matrices and probability. ...
This course is organized around algorithmic issues that arise in machine learning. Modern machine learning systems are often built on top of algorithms that do not have provable guarantees, and it is the subject of debate when and why they work. In this class, we focus on designing algorithms whose performance we can rigorously analyze for fundamen...
This book constitutes the thoroughly refereed proceedings of the 9th International Conference on Intelligent Human Computer Interaction, IHCI 2017, held in Evry, France, in December 2017.
The 15 papers presented together with three invited papers were carefully reviewed and selected from 25 submissions. The conference is forum for the presentation...
With this graduate-level primer, the principles of the standard model of particle physics receive a particular skillful, personal and enduring exposition by one of the great contributors to the field. In 2013 the late Prof. Altarelli wrote: The discovery of the Higgs boson and the non-observation of new particles or exotic phenomena have made a big...