6.897: Advanced Data Structures (Spring 2003)

Prof. Erik Demaine


[Home] [General motivation] [Requirements] [Projects] [Scribe notes] [Erik's notes] [Email archive] [Accessibility]

General Motivation

The field of data structures is similar in spirit to algorithms: what's the fastest way to solve problem X? But data structures take a different tact, focusing on ways to organize a typically long-lived corpus of data so that queries can be answered really fast. A typical example are web search engines, which store sophisticated indexes that support a variety of queries (e.g., what documents contain word X?) quickly. In contrast to most algorithmic problems, "linear time" is too slow--you can't afford to scan through the entire web to answer a single query--and the goal is typically logarithmic or even constant time per query. Also, space tends to become a more important issue, because the data corpus is usually big, and you don't really want a data structure that is larger (or even as big as) the data itself.

To me, data structures are particularly exciting because they are so universal and powerful. Almost every algorithmic problem I've encountered has at least a small data structural component, and knowledge about data structures and the literature has made faster algorithms possible.

Here are a couple of examples of very recent and cool data structures, so that you can judge whether these results excite you and you want to take or sit in the class: