CSE 525: Randomized Algorithms and Probabilistic Analysis (WI 08)
[course description
| lectures
| assignments
| related material]
course description
Instructor: James
Lee,
CSE 640, tel. 616 4368
Time: Mondays and
Wednesdays in CSE 403, 12-1:20pm
Office hours: By appointment
Teaching assistant: Alexander Jaffe
Office hours: M 230-330, W 130-230
Course evaluation: Scribe notes, a few homeworks, and a
final exam.
About this course:
Randomization and probabilistic analysis have become fundamental tools
in modern Computer Science,
with applications ranging from combinatorial optimization to machine
learning to cryptography to
complexity theory to the design of protocols for communication
networks. Often randomized algorithms
are more efficient, and conceptually simpler and more elegant than
their deterministic counterparts.
We will cover some of the most widely used techniques for the
analysis of randomized
algorithms and the behavior of random structures from a rigorous
theoretical perspective. A (non-random)
sample of topics to be covered includes elementary examples like
randomized pattern matching and
primality testing, large-deviation inequalities, the probabilistic
method, martingales, random graphs,
random geometric algorithms, and the analysis of Markov chains. Tools
from discrete probability will be
illustrated via their application to problems like randomized rounding,
hashing of high-dimensional data, and
load balancing in distributed systems.
Here is the template for the scribe notes.
schedule of classes
rough overview:
- Introduction - types of randomized algorithms, elementary examples
- Linearity of expectation, Markov's inequality, and the probabilistic method
- Variance, Chebyshev's inequality, and threshold phenomena in graphs
- The Laplace transform, Chernoff bounds, and applications: Low-congestion routing, randomized rounding
- Balls in bins, the power of two choices, load balancing
- Geometric concentration, random projections, dimension reduction
- More geometry: High-dimensional search and compressed sensing
- The Lovasz Local Lemma
- Martingales: Doob, Azuma, and applications
- Random walks and Markov chain Monte Carlo
schedule:
[Note: These scribe notes have not been proofread or corrected. Read at your own risk.]
- January 7 [pdf] Randomness in computation, polynomial identity testing, and perfect matchings.
Look here for the MVV parallel matching algorithm based on determinants of the Tutte matrix.
- January 9 [pdf] Fingerprints and pattern matching, start of primality testing.
Terry Tao's description of Wigderon's lecture on randomness in computation.
The AKS deterministic primality testing algorithm.
- January 14 [pdf] Miller-Rabin algorithm for primality testing, linearity of expectation, Markov's inequality.
- Jaunary 16 [pdf] The probabilistic method, crossing numbers, monotone circuits for majority
- January 21 MLK day - no class
- January 23 [pdf] Threshold phenomena in random graphs and Chebyshev's inequality
- January 28 [pdf] Chernoff bounds
- January 30 [pdf] Randomized rounding, min-congestion routing, and L_2 congestion in planar graphs.
- Feburary 4 [pdf] Routing in the hypercube.
- February 6 [pdf] Concentration of measure, isoperimetric inequalities, and tail bounds. The Johnson-Lindenstrauss lemma.
- February 11 [pdf] Hoeffding-Azuma inequality, proof of JL with discrete random matrices.
- February 13 [pdf] The power of two choices.
- February 25 Introduction to martingales, Azuma's inequality.
- February 27 Random geometric TSP. Doob-Kolmogorov inequality.
- March 3 Random walks on graphs and electrical networks.
- March 5 Markov chains and mixing times.
- March 10 Rapid mixing and coupling arguments.
- March 12 Sampling random graph colorings.
related material
Required text:
Probability
and Computing: Randomized Algorithms and Probabilistic Analysis
by Michael Mitzenmacher and Eli Upfal.
Courses at other schools:
Suggested references:
assignments
- Homework #1 due Monday, Feb 11.
- Homework #2 due Wednesday, Feb 27.
- Homework #3 due Wednesday, Mar 12.