22C:296 Seminar on Randomization
2:30-3:20 MWF Room 110 MLH
Instructor:
Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 319-353-2956
Office Hours: 11:30 to 12:20
This course will explore the use of randomization in graph theory
and combinatorics and in the design and analysis of algorithms.
We will study a variety of techniques from probability theory
that have become extremely useful to theoretical computer scientists.
Examples include
- The Markov Inequality (the first moment method)
- The Chebyshev Inequality (the second moment method)
- The Lovasz Local Lemma
- The Chernoff-Hoeffding concentration bounds, and
- Martingales and Azuma's inequality
Using these techniques we will study topics that include
- Random graphs
- Random walks
- Approximate counting using Markov Chain Monte Carlo methods and
- Approximation algorithms via randomized rounding.
22C:153 or an equivalent course taken elsewhere is a prerequisite.
Some knowledge of probability and some mathematical maturity will
definitely help.
Sources:
- The Probabilistic Method, N. Alon, J.H. Spencer, and P. Erdos, John
Wiley, 1991.
- Probabilistic Methods for Algorithmic Discrete Mathematics, edited by
M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, Springer-Verlag
Berlin, 1998.
- Approximation Algorithms for NP-Hard Problems, edited by Dorit S. Hochbaum, PWS Publishing Company, 1997.
- Modern Graph Theory (Graduate Texts in Mathematics), B. Bollobas,
Springer.
I need to hear from anyone who has a disability, which may require some
modification of seating, testing or other class requirements so that
appropriate arrangements may be made. Please see me after class.
Grading Policy,
Lecture Notes,
Announcements,
Homeworks and Exams,
Online Resources
There are three components that will determine your grade.
- Scribe Notes: 20% For each class one student will be responsible
for taking down notes. This student will then type these notes up and send
me a LaTeX file that I will process and post on the course page.
Depending on how many students
we end up with, each student will be responsible for 3-4 classes.
Each student will have two days to type up the scribe notes and send them to
me. We will figure out a schedule for scribe note-takers on the first day of
classes.
- Homeworks: 40% I will assign 3-4 problem sets, and you will have
about 3 weeks for each problem set.
- Paper presentation: 40% Each student will make a 1 hour presentation
on a research paper whose core idea involves randomization.
While my treatment of the material will be somewhat theoretical, these papers can
be fairly applied, provided they involve a non-trivial use of randomization.
For example, students might present papers on randomized distributed algorithms or
new random graph models for the internet or randomized data structures, etc.
- Introduction to the probabilistic method:
pdf, latex, 8/25.
- Introduction to the probabilistic method (continued):
pdf, latex, 8/27.
- The first moment method; k-SAT example:
pdf, latex, 8/29.
- The first moment method; the existence of graphs with high girth and high chromatic number:
pdf, latex, 9/3.
- Applications of the first moment method; Turan's theorem:
pdf, latex, 9/8.
- Second moment method; number theory example: pdf, latex, 9/10.
- Second moment method; Lazy Selection example:
pdf, latex, 9/15.
- Lovasz Local lemma; Application to vertex disjoint cycles: pdf, latex, 9/17.
- Algorithmic version of the Lovasz Local lemma; Beck's result: pdf, latex, 9/22.
- Algorithmic version of the Lovasz Local lemma; Beck's result (continued): pdf, latex, 9/24.
- Chernoff bounds; the basic result: pdf, 9/29.
- Application of Chernoff bounds to oblivious routing: pdf, latex, 10/1.
- Application of Chernoff bounds and Lovasz Local Lemma to an edge disjoint cycles problem: pdf, latex, 10/6.
- Application of Chernoff bounds and Lovasz Local Lemma to an edge disjoint cycles problem (contd.): pdf, latex, 10/8.
- Application of Chernoff bounds and Lovasz Local Lemma to an edge disjoint cycles problem (contd.): pdf, latex, 10/13.
- Random walks: pdf, latex, 10/15.
I have minimally edited the lecture notes above the horizontal line for consistency and correctness.
- Until further notice, for the rest of the semester, we will meet from 2:30 to 3:45 in N103 LC.
- Some suggestions for paper presentations. These will start on 11/17 and the schedule
is: Dasgupta 11/17, Hou 11/19, Pandit 11/21, Penumatcha 12/1, Raman 12/3, Schipper 12/5, Shen 12/8, Venkataraman 12/10, Zhang 12/12.
There are no online resources yet.