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

- Homework 1, due 9/24 in class.
- Homework 2, due 10/17 in class.
- Homework 3, due 11/21 in class.
- Homework 4, due 12/18 in class at final exam.

- 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.

- An excellent introduction to randomized algorithms due to Karp: An introduction to randomized algorithms, Discrete Applied Mathematics 34 (1991) 165-201.
- Azar, Broder, Karlin, and Upfal, Balanced Allocations, SIAM J. on Computing 29 (1999), 180-200.