6.897: Advanced Data Structures (Spring 2003)

Prof. Erik Demaine


See requirements for details on the goal, scope of topics, allowed collaboration, and format of projects. You do not have to be taking the class for credit to work on a project or the open problems posed here; just let me know that you are.

Step 1: Choosing a problem. The first step in your project is picking the topic and the specific problem to work on. This is both difficult and important; you want to choose a topic that's interesting (both to you and some community), not too easy, not too difficult, fun, not yet solved, etc. Expect to spend some time finding a good problem to work on. Of course, I'm here to help think up ideas, discuss whether an idea is appropriate, etc.

This page is mainly to help with this first step. Specifically, it contains

Step 2: Solving your problem. Once you've picked a problem, tell it to me. Then the second step is to solve it. This may involve

I want to stress this last point--collaboration--because it is often essential to research in theoretical computer science. You are allowed to collaborate with anyone: students taking the class for credit, students listening to the class, students not in the class, students not at MIT, faculty (including me), etc. The only constraint for the class is that your own contribution should be substantial enough, both in terms of solving problems and writing it up. To evaluate "substantial enough", you should talk to me.

Project Ideas

Here are some random ideas for data structures open problems to work on. I'll be adding to this list as I think up more open problems.

Sources for Project Ideas

One good general source is to look at recent papers about data structures, and look at the conclusion (or elsewhere) for the open problems. Another possibility is to look at an algorithms paper with a high running time and think about whether you could make it go faster using some more sophisticated data structures. To find such papers in algorithms and data structures, here are some general methods:

Students' Projects

As students choose projects, their titles will be listed here, to avoid overlap, and facilitate the possibility of collaboration. Please let me know if there are any inaccuracies (unlisted projects, mislisted projects).