The course with the Cockertoo...
Randomized Algorithms
CSCE 658, Course Information, Spring 2018
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 TW 1:30-2:30pm 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
- Minimum Cut Algorithms
- Expectation, Variance, Tail Inequalities
- Conditional Expectation
- Quicksort (Analysis with Conditional Expectation)
- Computational Complexity
- Chernoff Bounds
- Probability Generating Functions
- Permutation Routing
- Skip Lists
- Review for Midterm
- The Probabilistic Method
- The Lovasz Local Lemma
- Markov Chains
- Monte Carlo Methods
- Coupling of Markov Chains
Homework
- hw1.tex hw1.pdf
- hw2.tex hw2.pdf
- hw3.tex hw3.pdf
- hw4.tex hw4.pdf
- hw5.tex hw5.pdf
- hw6.tex hw6.pdf
- hw7.tex hw7.pdf
Schedule
| R | Jan 18 | Introduction, Primality Tests |
| T | Jan 23 | Basics of Probability Theory |
| R | Jan 25 | Borel sets, Random Variables |
| T | Jan 30 | Random Variables, Minimum Cuts |
| R | Feb 01 | Minimum Cut Algorithms |
| T | Feb 06 | Expectation, Variance, Tail Inequalities |
| R | Feb 08 | Quicksort, Conditional Expectation |
| T | Feb 13 | Conditional Expectation given a Random Variable |
| R | Feb 15 | Conditional Expectation given a Sigma-Algebra, Quicksort (analysis w/ cond. expectation) |
| T | Feb 20 | Complexity Classes |
| R | Feb 22 | Complexity Classes, Chernoff Bounds |
| T | Feb 27 | Chernoff Bounds, Probability Generating Functions |
| R | Mar 01 | Probability Generating Functions, Permutation Routing on Graphs |
| T | Mar 06 | Permutation Routing |
| R | Mar 08 | Permutation Routing, Skip Lists |
| T | Mar 13 | Spring Break, no classes |
| R | Mar 15 | Spring Break, no classes |
| T | Mar 20 | Review |
| R | Mar 22 | Midterm |
| T | Mar 27 | Solution to midterm exam, Probabilistic Method |
| R | Mar 29 | Probabilistic Method |
| T | Apr 03 | The Lovasz Local Lemma |
| R | Apr 05 | Markov Chains |
| T | Apr 10 | Markov Chains, Markov Chain Monte Carlo |
| R | Apr 12 | Monte Carlo Methods |
| T | Apr 17 | Coupling of Markov Chains, Mixing Time |
| T | Apr 19 | Coupling of Markov Chains |
| T | Apr 24 | Expander Graphs |
| R | Apr 26 | Expander Graphs |