Fall 2018, 12:30-1:45 TTh 110 MLH

**Instructor:**
Sriram V. Pemmaraju

101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956

Office Hours: 1:30-2:30 M, 10:30-11:30 W, 2:00-3:00 F (and by appointment).

Course webpage: `homepage.cs.uiowa.edu/~sriram/5360/fall18/`

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 in class, Thu 9/6.
- Homework 2. Due in class, Thu 9/20.
- Homework 3. Due in class, Thu 10/4.
- Final project handout. Due Fri 10/19 and Wed 10/31.
- Homework 4. Due in class, Thu 10/25.
- Final project paper guidelines. Paper due by 5 pm, Dec 7th.

**9/28**The midterm exam is on Thur, Oct 4th in B13 MLH from 6:30 pm to 8:30 pm. Here is some information about the exam: Midterm information.**8/23**No office hours on Friday, 8/24.**8/23**Look in the directory http://homepage.divms.uiowa.edu/~sriram/5360/fall18/template/ for LaTeX template files for scribe notes.

**Week 1: 8/20-8/24**Introduction: what randomized algorithms are, motivation for the design and use of randomized algorithms, types of randomized algorithms (Las Vegas and Monte Carlo), example:*Balanced Partitioning*. Randomized complexity classes: RP, coRP, BPP. example:*Polynomial Identity Testing*of a problem in coRP, but not known to be in P. Mutual and k-wise independence, Conditional probability, Introduction to Karger's mincut algorithm.

Week 1 Lecture Notes.**Week 2: 8/27-8/31**Analysis of Karger's mincut algorithm, use of conditional probabilities in the analysis, another example of probability amplification, random variables, expectation, the use of a*geometric random variable*to analyze expected running time of Las Vegas algorithm for the Balanced Partition problem. Linearity of expectation, proof of this for two variables. Application of Linearity of Expectation to*Coupon Collector's problem*,*Randomized QuickSort*.

Week 2 Lecture Notes.**Week 3: 9/3-9/7**Analysis of*Randomized QuickSort*using Linearity of Expectation. Union Bound and the use of union bound to analyze a Monte Carlo version of Randomized QuickSort. Application of Union Bound the to Balls and Bins problem. Markov's Inequality and its proof. Simple applications of Markov's Inequality.

Week 3 Lecture Notes.**Week 4: 9/10-9/14**Markov's Inequality and its proof, simple applications of Markov's Inequality, Chebyshev's Inequality and its proof, applications of Chebyshev's inequality to the coin tossing problem, coupon collector's problem, and a sampling-based median finding algorithm.

Week 4 Lecture Notes.**Week 5: 9/17-9/21**Using Chebyshev's Inequality to analyze the sampling-based median finding algorithm,**Digression:**another application of sampling, the Karger-Klein-Tarjan sampling-based algorithm for linear-time minimum spanning tree.

Week 5 Lecture Notes.**Week 6: 9/24-9/28**Proof of the Karger-Klein-Tarjan Sampling Lemma and runtime analysis of the Karger-Klein-Tarjan MST algorithm. Introduction to Chernoff bounds and simple applications of Chernoff bounds.

Week 6 Lecture Notes.**Week 7: 10/1-10/5**Another simple application of Chernoff bounds: probability amplification for BPP algorithms. Midterm.**Week 8: 10/8-10/12**Proof of Chernoff Bounds (upper tail), the*Permutation Routing*problem on a hypercube, the deterministic*bit-fixing*protocol for this problem, proving that the bit-fixing protocol is slow in the worst-case, a two-phase randomized variant of the bit-fixing protocol, run-time analysis of this protocol using Chernoff Bounds.

Week 8 Lecture Notes.**Week 9: 10/15-10/19**Using Chernoff bounds to analyze the randomized bit-fixing permutation routing protocol. An example of a randomized data structure: skip lists.

Week 9 Lecture Notes.**Week 10: 10/22-10/26**Using Chernoff bounds to analyze performance of skip lists, extensions of Chernoff bounds to random variables with negative dependence, k-wise independence, limited dependence, etc., Introduction to the*probabilistic*method, the max-cut problem, showing that a graph with m edges has a cut with at least m/2 edges using the*expectation*method.

Week 10 Lecture Notes.**Week 11: 10/29-11/02**A brief glimpse into Ramsey Theory, using the*counting*method to show that R(k, k) is at least 2^{k/2}, the*sample and modify*method, applying this method to show that an n-vertex graph with average degree d has an independent set of size at least n/2d, the*second moment*method, using the second method moment to show a threshhold function for random graphs.

Week 11 Lecture Notes.**Week 12: 11/05-11/09**Turning probabilistic methods proofs into efficient algorithms: a Las Vegas algorithm for max-cut.*Derandomizing*the max-cut algorithm: the*pairwise independence*approach, the*method of conditional probabilities*. The*Lovasz Local Lemma*, statement and simple examples including k-SAT.

Week 12 Lecture Notes.**Week 13: 11/12-11/16**Another example of Lovasz Local Lemma: existence of*list coloring*, proof of Lovasz Local Lemma, Beck's algorithmic version of Lovasz Local Lemma.

- An excellent introduction to randomized algorithms due to Karp: An introduction to randomized algorithms, Discrete Applied Mathematics 34 (1991) 165-201.