CS6214-001: Randomized Algorithms

Fall 2021

University of Colorado, Boulder

Take-home Final is posted and due Dec 10.



Randomness has proven itself to be a useful resource for developing provably efficient algorithms and protocols. As a result, the study of randomized algorithms has become a major research topic in recent years. This course will explore techniques for effectively using randomization and for analyzing randomized algorithms, as well as examples from a variety of settings and problem areas. A tentative syllabus can be found here.


Mathematical maturity; exposure to advanced undergraduate material in Algorithms, and in Discrete Probability and Combinatorics.

If you are not sure whether your background suffices, please see the instructor. The course is designed for graduate students but may be suitable for advanced undergraduates. Undergraduate students who are interested in taking the course are advised to consult with the instructor before registering.


Alexandra Kolla (alexandra.kolla [at] colorado [dot] edu) 122 ECEE [AK]


Fridays 1:50 -4:20 pm | ECES 114

Office Hours

Alexandra Kolla - TBD


# Date Topic Lecture Slides Reading Material
1 F August 27 Introduction to Randomness Slides Miller - Rabin Randomized Primality Testing
2 F September 3 Events and Probability Slides Chapter 1 from Textbook
3 F September 10 Random Variables and Expectation Chapter 2 from Textbook
4 F September 17 Moments, Deviations Chapter 3 from Textbook
5 F September 14 Chernoff Bounds Chapter 4 from Textbook
6 F October 1 Balls in Bins Chapter 5 from Textbook
7 F October 8 Probabilistic Method Chapter 6.1-6.2 from Textbook
8 F October 15 Probabilistic Method, contd. Chapter 6.3-6.7 from Textbook
9 F October 21 Lovasz Local Lemma, SDP for Max Cut. Chapter 6 from Textbook and this paper
10 F October 29 Lovasz Local Lemma, SDP for Max Cut cntd. MaxCut notes and Constructive LLL paper
11 F November 5 Markov Chains Chapter 7 from Textbook
12 F November 12 Random walks on graphs and eigenvalues Look at these notes
13 F November 19 Martingales Chapter 10 from Textbook




Homework # Due Homework Solutions
HW 1 September 17 -
HW 2 September 24 -
HW 3 October 1 -
HW 4 October 8 -
HW5 October 21 -
HW6 October 29 -
HW7 November 5 -


Part 1: Discrete probability

(approximately over the first 6 weeks)

-Monte Carlo, Las Vegas Algorithms.

-First and Second Moment method, coupon collector problem.

-Probabilistic Method (expanders, Lovasz Local Lemma, Method of conditional probabilities).

-Chernoff Bound and applications.

-Martingales and Azuma.

Part 2:

High-dimensional probability

(approximately over weeks 7-9)

-Bourgain's embedding.

-Curse of Dimensionality, Dimension Reduction.

-Matrix Concentration (Golden-Thompson, Bernstein).

-Random Graph eigenvalues via matrix concentration.

-Spectral Graph Sparsification via Sampling.

Part 3:

Random Walks, Markov Chains

(approximately over weeks 10-12)

-Random Walks: hitting times, cover times etc.

-Markov Chains and Mixing.

-Eigenvalues, Expanders and Mixing.

Part 4:

Advanced Topics

(remaining time)

-Lifts and Expanders, Interlacing Families of Polynomials.

-Stochastic Block Models, Planted Partition Models.

-Other Topics on Random Graphs.