CS:4980:0002 (22C:196:002) Topics in Computer Science II: Randomized Algorithms
12:30-1:45 TTh Room 302 Lindquist Center (LC)
Instructor:
Sriram V. Pemmaraju
101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956
Office Hours: 1:00 to 2:30 MW and by appointment.
Course webpage: homepage.cs.uiowa.edu/~sriram/196/fall13/
Randomization has played a powerful role in computer science over the last 3
decades, both in foundational areas such as algorithms,
complexity theory, learning theory, etc., and in applied
areas such as networks and data mining.
In this course we will study the use of randomization in the design of algorithms.
Specifically, we will study:
- various fundamental principles in the design of
randomized algorithms such as the first and second moment
method, random sampling, hashing, probability amplification, etc.,
- tools for analysis such as the tail bounds of Markov, Chebyshev,
Chernoff, and Hoeffding, the Lovasz Local Lemma, Martingale tail bounds, randomized
rounding of linear and semi-definite programs, etc.,
- applications to network routing, combinatorial optimization,
random walks, social networks, data streaming, etc.,
Syllabus document,
Announcements,
Homeworks and Exams,
Weekly Topics,
Online Resources
- The midterm exam will be on Thursday, 10/17 from 6:30 pm to 8:30 pm in 110 MLH.
Here is some information about the exam.
- The final will be on Wednesday, 12/18 from 8:00 pm to 10:00 pm in 302 LC (our regular classroom).
- Here is some information about the final exam.
- Week 1: 8/26-8/30 Introduction: what randomized algorithms are, motivation for the
design and use of randomized algorithms, examples of randomized algorithms,
types of randomized algorithms (Las Vegas and Monte Carlo), example: Fermat's Little Theorem
primality testing algorithm.
- Week 2: 9/2-9/6 Events and probability, axioms of probability, the union bound, inclusion-exclusion
principle, example: the balls and bins problem, conditional events, Bayes Law,
example: Karger's randomized min-cut algorithm (Chapter 1, Section 5.2, Mitzenmacher and Upfal).
- Week 3: 9/9-9/13 Discrete Random Variables (Bernoulli, Binomial, Geometric), expectation,
linearity of expectation, independence of random variables, conditional expectation,
example: coupon collector's problem, example: analysis of randomized quick sort (Chapter 2, Mitzenmacher and Upfal).
- Week 4: 9/16-9/20 Markov's inequality, variance, covariance, Chebyshev's inequality,
example: coupon collector's problem revisited, example: randomized algorithm for median finding (Chapter 3,
Mitzenmacher and Upfal).
- Week 5: 9/23-9/27 Analysis of randomized median finding algorithm via Chebyshev's inequality (Section 3.4),
three useful forms of Chernoff-Hoeffding bounds, simple examples of applications of these bounds: coin tossing,
balls and bins (Chapter 1 from Dubhashi and Panconesi).
- Week 6: 9/30-10/4 Applying Chernoff-Hoeffding bounds to the analysis of randomized quicksort
and the skip list data structure. Proof of Chernoff-Hoeffding bounds (Chapter 2 from Dubhashi and Panconesi).
- Week 7: 10/7-10/11 Proof of basic form of the Chernoff bound; proofs of more useful forms.
- Week 8: 10/14-10/18 Analysis of a randomized routing algorithm on a parallel computer.
Midterm.
- Week 9: 10/21-10/25 Chernoff bounds in settings where the underlying random variables are not independent:
d-bounded dependence, random variables that exhibit negative correlation.
- Week 10: 10/28-11/1 The probabilistic method. The first moment method. Examples: satisfiability of k-SAT, graphs
with high girth and high chromatic number.
- Week 11: 11/4-11/8 The second moment method. Example: threshold behavior in random graphs. The Lovasz Local Lemma (symmetric form). Examples: Satisfiability.
- Week 12: 11/11-11/15 Proof of symmetric form of the Lovasz Local Lemma. Beck's algorithmic version of
the Lovsz Local Lemma. The Moser-Tardos algorithmic version of the local lemma.
- Week 13: 11/18-11/22 Introduction to approximation algorithms. 1/2-approximation for MAXSAT. Derandomization
of this algorithm using method of conditional expectations. (1-1/e)-approximation for MAXSAT using LP-relaxation
plus randomized rounding.