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 illinois.edu).
Teaching assistants: Patrick Lin (plin15 at illinois.edu) and Kent Quanrud (quanrud2 at illinois.edu)
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