6.851: Advanced Data Structures (Spring'07)
[Home] [Lectures] [Assignments]
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
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 messy 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, including
coverage of powerful lower bounds.
Data structures for range queries (and other geometric problems) and problems
on trees. There are surprising equivalences between such problems, as well as
Data structures for querying large collections of large strings (think Google
and DNA sequences).
Self-adjusting data structures, persistent data structures and retroactive data
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: Monday & Wednesday 1–2:30
Lecture room: 56-114
Units: 3-0-9, H-level & EC credit
Registration: Subscribe to 6851-students mailing list on the web.
Assuming there is interest, there will be an optional problem solving session,
in which we will discuss and try to solve current open problems.
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 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.
Past and Future
The class is offered once every two years. It was given in Spring 2003 and in Spring 2005 as 6.897.
Later, it was given in