What is this course about?
Algorithms are the bread and butter of computer science. Nowadays it is very common to encounter datasets so large that they do not fit in the memory of a single machine. In such cases, where we cannot even read or store the entire input, traditional algorithms become infeasible even if they run in linear or quadratic time. This is the focus of the area of sublinear algorithms where the goal is to solve problems using resources that are substantially smaller than the size of the input.
This might sound confusing at first, how do I solve my problem without even reading the entire input?! Take this course to find out!
Tentative list of topics:
There are many flavors of sublinear algorithms, we will touch on some of them including:
Massively Parallel Computing
Streaming Algorithms
Local Computation Algorithms
Property Testing
Tentative Grading
Assignments (40%)
Roughly each part will have its own assignment.
The submission deadline will be announced along with the assignment. Late submissions will not be allowed.
You may discuss with your peers, but you MUST write the solutions on your own.
Paper Reading (20%)
You will be assigned various research papers to read throughout the course.
Your understanding of the paper will be evaluated either by an in-class quiz or through one-on-one discussions.
Final Project and Exam (30%)
You can do a project on a topic of your liking, as long as it is relevant to the spirit of the course.
Exam dates and project deadlines will be announced as the course progresses.
Class participation (10%)
References
I will provide relevant readings and notes for each topic we cover. But here are some generic reference materials to get a feel for the topics we will cover: