CSCI 6220/4030 Randomized Algorithms, Fall 2018


Randomized Algorithms are the state of the art in contemporary algorithm design. They are usually simple, sometimes even easy to analyze, and they work well in practice. This course provides an introduction to basic concepts in the design and analysis of randomized algorithms.

Course Logistics

A more detailed version of the syllabus is available as an archival pdf.

Instructor: Alex Gittens (gittea at rpi dot edu)

Lectures: MTh 10am-11:50am; Darrin 239

Office Hours: MTh 12pm-1pm, or by appointment; Lally 316

Course Text: (Recommended, not required) Probability and Computing, by M. Mitzenmacher and E. Upfal.

Grading Criteria:

Students are expected to have writing supplies on hand in each class to complete the in-class pop quizzes. If you are an athlete or for some other reason are not able to attend each class, make alternative arrangements with the instructor in the first two weeks of the course.

Letter grades will be computed from the semester average. Lower-bound cutoffs for A, B, C and D grades are 90%, 80%, 70%, and 60%, respectively. These bounds may be moved lower at the instructors discretion.


We will largely follow Mitzenmacher and Upfal, replacing the more ML-focused content with alternative material.

Lecture Schedule

Corresponding optional readings


All assignments must be typed (preferably in LaTeX) and are due at the start of class (defined as the first 10 minutes). Late assignments will not be accepted, unless you contact the instructor at least two days before the due date to receive a deferral. Deferrals will be granted at the instructor’s discretion, of course.


The details here may change over the next few weeks, so check back regularly.

In teams of two to three individuals, you will give a 20 minute presentation of an interesting or cool result or an algorithm (or class of algorithms) from a course-relevant technical or survey paper to the class; if your research is relevant, that could also be the topic of your presentation. This can be material that requires no background beyond general knowledge of CS, or more niche/applied knowledge; in the latter case, you should quickly explain the relevant concepts and background. See the "Giving Talks" and "Reading Papers" slide decks from the CS RPI Graduate Skills Seminar.

Content: address the following points.

An extremely biased sample of viable project ideas that is not at all representative of all your choices: the kmeans++ algorithm, coresets for geometric or ML problems, triangle counting in graphs; one of Karp's theorems for probabilistic recurrences; some application of The Power of Two Random Choices; random fourier features for kernel approximation in machine learning; fast-mixing Markov Chains for low-rank matrix approximation; one of the many stochastic approaches to optimization of sums of functions; rounding approaches for approximating solutions to LPs, QPs, or SDPs; compressed sensing; matrix completion; formation of minimal spanning trees; min-hash; count-min; how to fake multiply by a Gaussian matrix; an application of MCMC methods; etc. These selections are just examples, feel free to make entirely different choices.

Grading Rubric

Deliverables: these should be submitted in a single github/gitlab repo for each project. Due December 3.


Supplementary Materials