CS:5360 Randomized Algorithms

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

Homeworks and Exams

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

Announcements

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

Weekly Topics

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

Online Resources

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