CS590 Sublinear Algorithms

Tu/Th 1:30-2:45pm on Zoom


Elena Grigorescu, elena-g purdue.edu

Office Hours: by appointment.


Welcome to CS590 Sublinear Algorithms!

Course description

Algorithms that compute with a sublinear amount of resources (time, space, communication) lie at the foundations of data science. They can be used to analyze data across domains that span from social networks, financial transactions, or genomic data, to satellite communications or astronomical data. In this course we will study several sublinear models, including the sublinear-time model of Property Testing, sublinear-space streaming models, and sublinear-communication models. We will introduce many of the combinatorial, algebraic and geometric techniques commonly used in analyzing very fast algorithms for mathematical objects such as graphs, strings, distributions, and error-correcting codes. 

Prerequisites: A course on discrete math, undergraduate algorithms, and mathematical maturity.


  • 4-5 homework sets 40%
  • Semester-long research project 45%
  • Scribe notes for 2-3 lectures + peer grading 10% (template scribe .tex and .pdf)
  • Class participation 5%
Similar courses elsewhere