22C:196 Randomization in Computer Science
12:30-1:20 MWF Room 132 MLH
Instructor:
Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 319-353-2956
Office Hours: 11:00 to 12:20 MW and by appointment.
Course webpage: www.cs.uiowa.edu/~sriram
Randomization has played a power 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, data mining, data streaming, etc.
In this course we will study:
- various fundamental principles in the design of
randomized algorithms such as the first moment method, the second moment
method, random sampling, hashing, etc.,
- tools for analysis such as the bounds of Markov, Chebyshev,
Chernoff, and Hoeffding, the Lovasz Local Lemma, etc.,
- applications to network routing, combinatorial optimization,
random walks, social networks, data streaming, etc.,
A more detailed list of topics appears in the syllabus.
Syllabus document,
Announcements,
Homeworks and Exams,
Weekly Topics,
Links to Papers
- 8/25: Read Chapter 1 of the textbook.
- 9/3: Read Chapter 2 of the textbook.
- 9/3: HW 1 is due on 9/5 in class.
- 9/10: Read Chapter 3 of the textbook.
- 9/22: Read Chapter 4 of the textbook.
As practice, you might want to solve Problem 3.3 and Problems 4.2, 4.3, and
4.4.
- 10/3: Read until the end of Section 2 in the Leighton-Maggs-Rao
paper.
- 10/3: Read Section 1 in the survey on randomized rounding
posted below.
- 10/14: Read Sections 6.1-6.4 on the probabilistic method.
- 10/14: Take home midterm (with 3 problems) will be handed out
on Friday 10/17 and again on Friday 10/24. Due back on Monday, three days
later. One problem on Chebyshev's Inequality, one on Chernoff Bounds, and
one on randomized rounding.
- Homework 1: Problems 1.16, 1.19. 1.25, 2.26, and 2.32. Due on
Friday, September 5th, in class.
- Homework 2: Problems 3.16, 3.21, 4.18, 4.20, and 4.21. Due on
Friday, October 3rd, in class.
- Homework 3: Problems 4.19, 6.10, 6.12, 6.18, and one more
on Total Coloring.
Due on Monday, Dec 1st, in class.
- Homework 4: Problems 7.6, 7.9, 7.10, 7.21, 7.24. Due on
Monday, Dec 15th, by 5 pm in my office or in my mailbox.
Weekly Topics
- Week 1: 8/25-8/29 Events and probability, axioms of probability, conditional events,
Bayes Law, Karger's randomized min-cut algorithm
- Week 2: 9/1-9/5 The probabilistic method (lower bound on Ramsey numbers), Expectation of discrete random variables, linearity of expectation,
geometric random variables
- Week 3: 9/8-9/12 The coupon collector's problem, analysis of randomized QuickSort, Markov's Inequality, Chebyshev's Inequality, the Coupon
Collector revisited
- Week 3: 9/15-9/19 Application of Chebyshev's Inequality to Randomized Selection, Introduction to Chernoff Bounds
- Week 4: 9/22-9/26 Moments and Moment Generating Functions,
Derivation of Chernoff Bounds, Application of Chernoff Bounds to Packet
Routing
- Week 5: 9/29-10/3 Extensions of Chernoff bounds (to random
variables with negative correlation, bounded random variables, random
variables with limited dependence), Overview of types of randomized
algorithms (Monte Carlo and Las Vegas), Overview of randomized complexity
classes (RP, BPP, ZPP)
- Week 6: 10/6-10/10 Randomized rounding for solving combinatorial
optimization problems (Set Cover, MAX-SAT, st-min-cut, etc.), independent
rounding vs dependent rounding
- Week 7: 10/13-10/17 Finishing up discussion of randomized
rounding schemes, introduction to the probabilistic method.
- Week 8: 10/20-10/24 The probabilistic method via sample-and-modify:
existence of large independent sets and existence of graphs with large
girth and large chromatic number. The probabilistic method via the
second moment: a threshold function for Erdos-Renyi random graphs.
- Week 9: 10/27-11/1 Lovasz Local Lemma (LLL), its proof, and some of
its many applications.
- Week 10: 11/3-11/7 A bound of total chromatic number via LLL and Chernoff Bounds.
- Week 11: 11/10-11/14 k-SAT: Algorithmic version of LLL.
- Week 12: 11/17-11/21 Markov Chain based algorithms for 2-SAT and 3-SAT.
- Week 13: 12/1-12/5 Stationary distributions, Fundamental Theorem of Markov Chains, Random Walks, Cover Time
- Week 14: 12/8-12/12 Algorithms for Data Streams