• Feb. 23, 2017: Webpage created
  • Aug. 28, 2017: Project instruction posted
  • Aug. 28, 2017: Project proposal due on Sept. 22, 2017, 11:59pm EST
  • Aug. 28, 2017: Data Collection Report (if you choose direction 2) due on Oct. 2, 2017, 11:59pm EST
  • Sept. 6, 2017: Homework 1 is out. Due on Oct. 15, 2017, 11:59pm EST
  • Aug. 28, 2017: Intermediate Report due on Oct. 22, 2017, 11:59pm EST
  • Oct. 3, 2017: Homework 2 is out. Due on Nov. 5, 2017, 5pm EST
  • Aug. 28, 2017: Final Report due on Nov. 26, 2017, 11:59pm EST
  • Aug. 28, 2017: Project presentations on Nov. 27, Nov. 29, Dec. 4, Dec 6 2017, in class

Course summary

In this course we will talk about sublinear algorithms, which has its roots in the study of Big Data that occur more and more frequently in various applications, e.g., analyses of financial transactions, internet traffic, social networks, genome sequences, etc. Concretely, we will talk about:
1. Sublinear space algorithms. In particular, data stream algorithms, namely, algorithms that solve a problem by making one pass over the data set while using small memory. These algorithms are important in many application areas such as databases and networking, where data arrives at a high speed and there is no time and/or need to store it for offline processing.
2. Sublinear time algorithms, that is, algorithms that do not even read the whole input when outputting the answers.
3. Sublinear communication algorithms. The data is stored in multiple machines, who want to jointly compute functions defined on the union of the data sets via communication.
4. Random topics.
Participants are expected to have a good background in algorithm design and probability, and have good programming skills.
The evaluation will be based on homework assignments and individual project/presentation. The list of questions will be handed out in the middle of the course.
Detailed list of topics is available in the course plan below.


Qin Zhang
Office hours: Wed. 4-5pm at LH430A

Associate Instructor:
Ruiyu Zhu
Office hours: Mon. 4-5pm at Lindley Abyss

Time and place

2:30pm - 3:45pm Monday/Wednesday
BH (Ballantine Hall) 005.