COMS 4995: Randomized Algorithms



Course Assistants:

Time/location: 10:10-11:25 AM Mon/Wed in Mudd 545.

Discussion site: We'll be using Piazza.

Prerequisites: Undergraduate algorithms (COMS 4231) or equivalent.

Course Description: Randomness pervades the natural processes around us, from the formation of networks, to genetic recombination, to quantum physics. Randomness is also a powerful tool that can be leveraged to create algorithms and data structures which, in many cases, are more efficient and simpler than their deterministic counterparts. This course covers the key tools of probabilistic analysis, and applications of these tools to understand the behaviors of random processes and algorithms. Emphasis is on theoretical foundations, though we will apply this theory broadly, discussing applications in machine learning and data analysis, networking, and systems.

Textbook: There is no required textbook for the course; lectures are the sole required source of content. Supplementary reading will be posted as part of the lecture schedule, below. You might, however, find one or more of the following books helpful:


Lecture Schedule