Applied Algorithms (Algorithms for Large Data)


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]