Computer ScienceScience & MathematicsEconomics & FinanceBusiness & ManagementPolitics & GovernmentHistoryPhilosophy

Notes on Randomized Algorithms

by James Aspnes

Notes on Randomized Algorithms

Subscribe to new books via telegram channel

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
Chapter 8
Martingales and stopping times
Chapter 9
Markov chains
Chapter 10
Approximate counting
Chapter 11
The probabilistic method
Chapter 12
Chapter 13
Quantum computing
Chapter 14
Randomized distributed algorithms

Book Details

Notes on Randomized Algorithms
Computer Science
PDF Size
3.3 MB

Related Books

Computer and Information Sciences
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...
Elements of Robotics
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. ...
Notes from the excellent lecture on sales that Steli Efti did at Y Combinator....
Algorithmic Aspects of Machine Learning
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...
Intelligent Human Computer Interaction
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...
Collider Physics within the Standard Model
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...