Algorithms for Big Data

Chandra Chekuri

CS498ABD, Spring 2019

Course Summary

This course will describe some algorithmic techniques developed for handling large amounts of data that is often available in limited ways. Topics that will be covered include data stream algorithms, sampling and sketching techniques, and sparsification, with applications to signals, matrices, and graphs. Emphasis will be on the theoretical aspects of the design and analysis of such algorithms.

This version of the course is directed at senior level undergraduate students and beginning graduate students, and hence will not assume background in randomized algorithms. The pace of the course and the topics will be commensurately adjusted.

Instructor: Chandra Chekuri (3228 Siebel Center, chekuri at

Teaching assistants: Patrick Lin (plin15 at and Kent Quanrud (quanrud2 at

Office hours: Siebel 3rd floor theory loung. Chandra (Fri 1:00-2:00pm), Kent (Tue 3:00 - 4:00 ), Patrick (Mon 3:00 - 4:00)

Grading policy: 50% Homework, 25% Midterm, 25% Project

Prerequisites: CS 374 and CS 361, or comparable understanding and facility with algorithms and probability.

Links: Piazza; Gradescope (self-enrollment code: 9NY3ZN)

Projects: Instructions and paper list



Additional references and study material