The Steam Powered Turing Machine University of Washington Department of Computer Science & Engineering
 CSE 522: Sublinear (and Streaming) Algorithms
  CSE Home  About Us    Search    Contact Info 
  Presentation Topics/Papers
  Notes Lectures 1-17
  Problem Set 1
  Problem Set 2

Our increased ability to gather data has resulted in data sets so large that many of our traditional algorithmic methods break down. Sorting, or even reading the entire data set can be prohibitively expensive. Under these conditions, we cannot use our standard exact algorithms, and must be content with approximate solutions that come with strong guarantees. This course will look at a range of methods and associated algorithms that use sub-linear time in the size of their input data, as well as on data stream algorithms that can perform a number of data analyses using only a single pass through the data and much less than linear space. We will also consider the limitations of these methods.

Instructor: Paul Beame, CSE 668, beame at Office hours: Mondays after class.

Lecture: MW 1:30-2:50    MGH 254

Resources: The website has links to open problems and links to papers and other course materials on the subject matter for this course. It will serve as the closest thing to a text for the course.

Portions of the CSE 522 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE 522 Web: © 1993-2014, Department of Computer Science and Engineering, University of Washington.