6.897: Advanced Data Structures (Spring'05)
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:
- Classic comparison-based data structures. The area is still rich
with open problems, such as whether there is a single best
(dynamically optimal) binary search tree.
- Dynamic graph problems. In almost any network, a link's
availability and speed are anything but a constant, which has led to
a re-evaluation of the common understanding of graph problems: how
to maintain essential information such as a minimum-weight spanning
forest while the graph changes.
- Integer data structures: beating the O(lg n) barrier in
sorting and searching. If you haven't seen this before, beating
O(lg n) may come as a surprise. If you have seen this
before, you might think that it's about a bunch of grudgy
bit-tricks. In fact, it is about fundamental issues regarding
information and communication. We hope to give a cleaner and more
modern view than you might have seen before.
- Data structures for range queries (and other geometric problems)
and problems on trees. There are surprising equivalences between
such problems, as well as interesting solutions.
- Data structures for querying large collections of large strings
(think Google and DNA sequences).
- Succinct data structures. Optimizing space is essential as data
size reaches new orders of magnitude (again think Google and DNA).
Some data structures require no space beyond the raw data (carefully
ordered) and still answer queries relatively quickly.
- Data structures optimized for external memory, and
cache-oblivious data structures. Any problem (e.g., sorting,
priority queues) is different when you're dealing with disk instead
of main memory, or you care about cache performance. Memory
hierarchies have become important in practice because of the recent
escalation in data size.
- Lecture time: Tuesdays & Thursdays 2:30-4
- Lecture room: 32-141 (Stata)
- Units: 3-0-9, H-level & EC credit
- Registration: email mip#at#mit.edu, to join
the class mailing list.
Assuming there is interest, there will be an optional problem
solving session, in which we will discuss and try to solve current
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 accomodate students
who have only taken 6.046, and we will not rely on 6.854
material. Nonetheless, in order to use this option, you must have an
excellent 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):
- 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
- 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. A good introduction can be found here.
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. In Athena, you
can compile with latex and view the resulting DVI files with
xdvi (this 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 in the process of entering the MIT standard
curriculum, and is expected to be offered once every two years.
You can get a feeling for the course by looking at the
website from Spring 2003.
Note however, that that was the first offering of the course,
and we plan to change several aspects of it based on past experience.