Computer Science 49/149
Where: Sudikoff 115
When: 10A hour: TTh 10:00-12:00, X-hr W 15:00-16:05
Who: Instructor: Amit Chakrabarti,
Sudikoff 107, Office hours: MF 9:00-10:30
What: This course studies algorithms that process massive amounts of data; so massive that they will not fit in a computer's storage. As we shall see, this forces one to rethink even very basic algorithmic problems, such as counting the number of distinct elements, selection, and sorting. We shall study techniques to summarize such large amounts of data into succinct "sketches" that nevertheless retain important and useful information. We shall introduce the necessary mathematical tools along the way. Most techniques we shall study come from research in the last decade or so, although a few date as far back as the 1970s. The techniques we shall study have been applied successfully to web data compression, approximate query processing in databases, network measurement and signal processing. The course itself will focus on the underlying techniques rather than the specific applications.
Prerequisites: An undergraduate-level course
in Algorithms (such as our CS 31)
Lecture Plan: The following is a rough outline, and will very likely be changed once the course gets going.
Textbooks: There is no set textbook for this course, but we have some evolving in-house course notes, thanks to the scribing efforts of students from the previous offering of the course. A good fraction of the material we shall study only resides in research papers. There is a good survey by Muthukrishnan, somewhat dated at this point, but still very useful for the basics.
Homework Sets: We will have 4 homework sets in total.
Class Presentation: In lieu of a final exam, students are required to read up on an advanced topic in data stream algorithms (usually represented by a research paper), and give a short, 15-minute presentation on its main ideas. Each presentation should be given by a team of 2 students. Below is a list of suggested papers for such a presentation.
We now have a schedule for the class presentations. Please note that all students should be present for all presentations. The presentation is in lieu of a final exam and does count towards your grade, with 20% weight.
Class Presentation: In lieu of a final exam,
TA and Office Hours: Our TA will be Ranganath Kondapally. Office hours for the TA and instructor are announced at the top of this page. Additionally, feel free to drop by and chat with us about the course whenever our doors are open.