Notes on Randomized Algorithms

Abstract

| | Table of contents | | | ii | | --- | --- | --- | --- | --- | | | List of figures | | | xiv | | | List of tables | | | xv | | | List of algorithms | | | xvi | | | Preface | | | xvii | | 1 | | Randomized algorithms | | 1 | | | 1.1 | A trivial example | | 2 | | | 1.2 | Verifying polynomial identities | | 3 | | | 1.3 | Randomized QuickSort | | 5 | | | | 1.3.1 Brute force method: solve the recurrence | | 5 | | | | 1.3.2 Clever method: use linearity of expectation | 6 | | | | 1.4 | Where does the randomness come from? | | 8 | | | 1.5 | Classifying randomized algorithms | | 9 | | | | 1.5.1 Las Vegas vs Monte Carlo | | 9 | | | | 1.5.2 Randomized complexity classes | | 10 | | | 1.6 | Classifying randomized algorithms by their methods | | 12 | | 2 | | Probability theory | | 14 | | | 2.1 | Probability spaces and events | | 15 | | | | 2.1.1 General probability spaces | | 15 | | | 2.2 | Boolean combinations of events | | 17 | | | 2.3 Conditional probability | | | 20 | | | 2.3.1 | Conditional probability and independence | | 20 | | | 2.3.2 | Conditional probability and the law of total probability | | 20 | | | 2.3.3 Examples | | | 22 |