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

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

TIME TRAVEL | We can remember the past efficiently (a technique called persistence), but in general it's difficult to change the past and see the outcomes on the present (retroactivity). So alas, Back To The Future isn't really possible. |
---|---|

GEOMETRY | When data has more than one dimension (e.g. maps, database tables). |

DYNAMIC OPTIMALITY | Is there one binary search tree that's as good as all others? We still don't know, but we're close. |

MEMORY HIERARCHY | Real computers have multiple levels of caches. We can optimize the number of cache misses, often without even knowing the size of the cache. |

HASHING | Hashing is the most used data structure in computer science. And it's still an active area of research. |

INTEGERS | Logarithmic time is too easy. By careful analysis of the information you're dealing with, you can often reduce the operation times substantially, sometimes even to constant. We will also cover lower bounds that illustrate when this is not possible. |

DYNAMIC GRAPHS | A network link went down, or you just added or deleted a friend in a social network. We can still maintain essential information about the connectivity as it changes. |

STRINGS | Searching for phrases in giant text (think Google or DNA). |

SUCCINCT | Most “linear size” data structures you know are much larger than they need to be, often by an order of magnitude. Some data structures require almost no space beyond the raw data but are still fast (think heaps, but much cooler). |

**Lecture time:**Tuesday & Thursday 11–12:30**First lecture:***Tuesday, February 7, 2012***Lecture room:**4-163**Units:**3-0-9, H-level & EC credit**Registration:**Subscribe to 6851-students mailing list on the web.**Contact:**Email`6851-staff#at#csail.mit.edu`

**Optional open-problem session:**6-8pm on Thursdays in 32-G575

The required prerequisite is 6.046, Design and Analysis of Algorithms or an equivalently thorough undergraduate algorithms class from another school (e.g., covering much of CLRS). The recommended prerequisite is 6.854, Advanced Algorithms. This is the broad entry-level graduate course in Theory/Algorithms, and it normally makes sense to start there before jumping into deeper graduate courses. If you haven't taken 6.854, you must have a strong understanding of algorithms at the undergraduate level, such as receiving an A in 6.046, having had a relevant UROP, involvement in computer competitions, etc.

- Scribing one, maybe two, lectures. See the lectures page for more details. Note in particular that scribe notes are due on the day of the lecture. The entire calendar for the course has been posted, so you can select a lecture that interests you. We will circulate a sign-up sheet during the second week. Listeners may also be required to scribe one lecture.
- Lightweight homework assignments. See the assignments page for details. Problems will be posted there weekly, and will not be distributed otherwise.
- Research-oriented final project (paper and presentation). We allow theoretical, experimental and survey final projects. See the project page for more details.

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.

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