CSCI 1951-W: Sublinear Algorithms for Big Data


Instructor: Jasper Lee

Course Description

A huge quantity of data is worth little unless we can extract insights from it. Yet, the large quantities mean that classic algorithms (running in linear, quadratic or even more time) can be infeasible in practice. We must instead turn to new algorithmic approaches and paradigms, which allow us to answer valuable questions about our data in runtime that is still feasible even when the data set is Facebook-sized.

Surprisingly, to answer many computational and statistical questions, sometimes there is no need to read/store every piece of data! This course focuses on this exciting "sublinear" algorithmic regime.

See the course missive for details on assessment and various policies.

Piazza: Link (Access code will be emailed to all students shopping the course before the beginning of the semester)


This is an advanced undergraduate level (1000 level) to graduate level (2000 level) course.

Course prerequisites:

CS155 is recommended but not required: all required materials not taught in CS145 or equivalent will be covered in this class.

Mathematical maturity is essential: we will prove most of the results covered in the class.