Course outline
The course will focus on algorithms for large data. We will cover topics such as streaming algorithms for estimating
frequency moments and other interesting features of large data, dimension reduction and norm computation
problems for large data, algorithms for large graphs and lower bounds using communication complexity
and information theory.
Detailed outline [pdf]
Lecture notes
The course is divided into four modules.
Module 1
In this module we focus on streaming algorithms for frequency moment computations. Draft notes
are available here.
[pdf]
Module 2
In this module we study ideas related to dimension reduction and algorithms for norm computation.
Module 3
In this module we design algorithms for graph problems such as graph matchings and graph spanners.
Module 4
In this module we use communication complexity and information theory to prove streaming lower bounds.
Problem sets
Here are a few assignments and tutorials.
[pdf]