6.851: Advanced Data Structures (Spring'10)

Prof. Erik Demaine     Dr. André Schulz     TA: Aleksandar Zlateski

[Home] [Lectures] [Assignments] [Project] [Problem Session]

Data structures play a central role in modern computer science. You interact with data structures much more often than with algorithms (think of Google, your mail server, and even your network routers). In addition, data structures are essential building blocks in obtaining efficient algorithms. This course will cover major results and current directions of research in data structures:



The recommended prerequisite is 6.854, Advanced Algorithms. This is the entry-level graduate course in Theory/Algorithms, and it should be taken before jumping into any deeper graduate courses. However, we recognize that some highly qualified students have not yet taken 6.854 for objective reasons. Therefore, we will try to accommodate students who have only taken 6.046, and we will not rely on 6.854 material. In order to use this option, you must have a strong understanding of algorithms at the undergraduate level; such a level of understanding can be reached through an A in 6.046, relevant UROP, involvement in computer competitions, etc.


There are three requirements (other than attending lectures):

LaTeX Help

Homework solutions, scribe notes, and final projects must be typeset in LaTeX. If you are not familiar with LaTeX, there is no need to worry. Start with this good introduction. You need to know very little to start writing problem sets in LaTeX: just skim through the mathematics section in the introduction, and download this template. On Athena, you can compile with latex and view the resulting DVI files with xdvi (which will refresh automatically when you recompile). When you're ready to submit, compile with pdflatex and send us the PDF.

Past and Future

The class is offered once every two years. It was given in Spring 2003 and Spring 2005 as 6.897, and in Spring 2007 as 6.851. Later, it was given in Spring 2012 and Spring 2014.