Computer Science Department

CS 598: Algorithms for Big Data

Chandra Chekuri

Fall 2014

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. Prerequisites: CS 573, good background in (discrete) probability

Administrative Information

Lectures: Tue, Thu 2 to 3.15pm in Siebel Center 1109.

Instructor:  Chandra Chekuri- 3228 Siebel Center, 265-0705, chekuri at illinois dot edu

Office Hours: Wed 10-11am, and by appointment

Grading Policy: There will be 4-5 homeworks, roughly once every two weeks and final course project. Course projects could involve research on a specific problem or topic, a survey of several papers on a topic (summarized in a report and/or talk), or an experimental evaluation. I also expect students to scribe one lecture in latex.

Prerequisites: This is a graduate level class and a reasonable background in algorithms and discrete mathematics would be needed. Knowledge and exposure to probability and linear algebra is necessary.

Reference/Study material:

Potential Topics:

  • Streaming, Sketching and Sampling for Signals.
  • Dimensionality Reduction
  • Streaming for Graphs
  • Numerical Linear Algebra
  • Compressed Sensing
  • Map-Reduce model and basic algorithms
  • Introduction to Property Testing
  • Lower Bounds via Communication Complexity


Note: The above list is suggestive/tentative and we will cover only a subset of the topics.

Piazza site for questions and discussion
Moodle site for submitting homeworks.


Homework 1 given on Thursday 09/2/14, due in class on Thursday, 9/11/14.

Homework 2 given on Friday 09/12/14, due on Thursday, 9/23/14.

Homework 3 given on Friday 10/10/14, due on Thursday, 10/23/14.

Homework 4 given on Friday 11/7/14, due on Thursday, 11/20/14.


Sample LaTeX file and algo.sty

Warning: Notes may contain errors. Please bring those to the attention of the instructor.

Course Project Information