The course with the Cockertoo...
Randomized Algorithms
CSCE 658, Course Information, Spring 2019
The course gives an introduction to randomized algorithms. Randomization allows to design efficient algorithms, which are often of elegant simplicity. Selected tools and techniques from probability theory and game theory are reviewed, with a view towards algorithmic applications. The main focus is a thorough discussion of the main paradigms, techniques, and tools in the design and analysis of randomized algorithms. A detailed analysis of numerous algorithms will illustrate the abstract concepts and techniques. You will learn about random walks, Markov chains, the probabilistic method, discrepancy theory, etc. The basics of probability theory will be reviewed.
Instructor Dr. Andreas Klappenecker,
Office HRBB 509B
Office hours T 10:30am-11:30am, W 11:00am-noon or by appointment
General Information
- [MU] M. Mitzenmacher, E. Upfal: Probability and Computing, Cambridge University Press, 2nd edition, 2017
- M. Capinski, E. Kopp, Measure, Integral, and Probability, Springer, 2004 (optional, you can find it on libcat)
- A. Gut Probability: A Graduate Course, Springer, 2005 (optional, you can find it on libcat)
- J.K. Hunter, Measure Theory (optional, skim chapters 1-3 if you want to know more about measure theory).
Lecture Notes or Slides
- Primality Tests
- Basic of Probability Theory
- Random Variables
- Why Sigma-Algebras are Needed
- Minimum Cut Algorithms
- Expectation, Variance, Tail Inequalities
- Conditional Expectation
- Quicksort
- Complexity
- Chernoff Bounds
- Probability Generating Functions
- Permutation Routing
- Skiplists
- The Probabilistic Method
- Review
- Markov Chains
- Coupling
Homework
- hw1.tex hw1.pdf
- hw2.tex hw2.pdf
- hw3.tex hw3.pdf
- hw4.tex hw4.pdf
- hw5.tex hw5.pdf (hw5.tex corrected)
- hw6.tex hw6.pdf
Schedule
| R | Jan 15 | Introduction, Primality Tests |
| T | Jan 17 | Basics of Probability Theory |
| R | Jan 22 | Basics of Probability Theory |
| T | Jan 24 | Random Variables |
| T | Jan 29 | Random Variables, Minimum Cuts |
| R | Jan 31 | Minimum Cuts |
| T | Feb 05 | Expectation, Variance, Tail Inequalities, |
| R | Feb 07 | Conditional Expectation, Quicksort |
| T | Feb 12 | Computational Complexity Quicksort |
| R | Feb 14 | Computational Complexity |
| T | Feb 19 | Chernoff Bounds, Probability Generating Functions |
| R | Feb 21 | Probability Generating Functions, Permutation Routing on Graphs |
| T | Feb 26 | Permutation Routing on Graphs |
| R | Feb 28 | Skiplists, Probabilistic Method |
| T | Mar 05 | Probabilistic Method, Review |
| R | Mar 07 | Midterm |
| T | Mar 12 | Spring Break |
| R | Mar 14 | Spring Break |
| T | Mar 19 | The Lovász Local Lemma |
| R | Mar 21 | The Lovász Local Lemma |
| T | Mar 26 | Markov Chains |
| R | Mar 28 | Markov Chains, Coupling |
| R | Apr 02 | Markov Chains, Coupling |