6.851: Advanced Data Structures (Spring'10)
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
- 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 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.
- Geometric data structures: segment trees, range trees,
partition trees, dynamic convex hull, etc. In particular, range
queries have surprising equivalences to problems on trees.
- Data structures for querying large collections of large
strings (think Google and DNA sequences).
- Self-adjusting data structures, persistent data structures
and retroactive data structures.
- 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
- 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: Tuesday & Thursday
- First lecture: Tuesday, February 2, 2010
- Lecture room:
- Units: 3-0-9, H-level & EC credit
- Registration: Subscribe to 6851-students
mailing list on the web.
- Contact: Email
- Optional open-problem session:
some Thursdays at 4–6pm:
• Feb. 18 in 32-124
• Mar. 11 in 32-124
• Mar. 18 in 8-205
• Apr. 1 in 32-124
• Apr. 15 in 4-145
• Apr. 22 in 32-124
• May 6 in 32-124
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.
GradingThere are three requirements (other than
- 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
as 6.897, and in
as 6.851. Later, it was given in