The course with the Cockertoo...
Randomized Algorithms
CSCE 658, Course Information, Fall 2011
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 MT 2:00-2:50pm or by appointment
General Information
- Syllabus
- [MU] M. Mitzenmacher, E. Upfal: Probability and Computing, Cambridge University Press, 2005
Lecture Notes
- Algorithmic Appetizers
- Probability Theory
- Minimum Cut
- Graphs with High Girth and High Chromatic Number
Homework
Schedule
| M | Aug 29 | Introduction |
| W | Aug 31 | Minimum Cut |
| F | Sep 02 | Minimum Cut |
| M | Sep 05 | Random Variables |
| W | Sep 07 | Markov's and Chebychev's inequality |
| F | Sep 09 | Indicator Random Variables, First Moment Principle |
| M | Sep 12 | Probabilistic Method |
| W | Sep 14 | Geometric Random Variables |
| F | Sep 16 | Quicksort |
| M | Sep 19 | Quicksort |
| W | Sep 21 | Chernoff bounds |
| F | Sep 23 | Chernoff bounds |
| M | Sep 26 | Packet Routing in Hypergraphs |
| W | Sep 28 | Packet Routing in Hypergraphs |
| F | Sep 30 | Probabilistic Method |
| M | Oct 03 | Randomized Algorithm for Median |
| W | Oct 05 | Randomized Algorithm for Median |
| F | Oct 07 | Problem Session |
| M | Oct 10 | Problem Session |
| W | Oct 12 | Probabilistic Method, Graphs with high girth and high chromatic number |
| F | Oct 14 | Midterm exam |
| M | Oct 17 | Probabilistic Method |
| W | Oct 19 | Probabilistic Method |
| F | Oct 21 | Random Graphs |
| M | Oct 24 | Random Graphs |
| W | Oct 26 | Threshold Behavior of Random Graphs |
| W | Oct 28 | Threshold Behavior of Random Graphs |
| M | Oct 31 | Lovasz Local Lemma |
| W | Nov 02 | Lovasz Local Lemma |
| W | Nov 02 | Constructive Lovasz Local Lemma |
| F | Nov 04 | Markov Chains |
| M | Nov 07 | Markov Chains, 2-SAT |
| W | Nov 09 | Markov Chains |
| F | Nov 11 | Random Walks |