6.897: Advanced Data Structures (Spring 2003)
Everyone is welcome to audit/sit in/listen to the class.
Students taking the class for credit have the following requirements:
- Attend: You must attend (almost all) lectures.
- Scribe: Write lecture notes for a few classes
(how many depends on class size).
- Project: Write a paper of 10 or so pages, as described below.
- Presentation: Give a brief talk about your project
near the end of the semester.
The notes you write should cover all the material covered during the relevant
lecture, plus real references to the papers containing the covered material.
Your notes should be understandable to someone who has not been to the lecture.
You should write in full sentences where appropriate; point form
(like I write on the board) is often too terse to follow without a sound track
(though occasionally it is appropriate).
Use numbered sections, subsections, etc. to organize the material
hierarchically and with meaningful titles.
If you feel it is appropriate, use nested bullets to organize
material hierarchically even deeper.
Try to preserve the motivation, difficulties, solution ideas, failed attempts,
and partial results obtained along the way in the actual lecture.
I will bring you a copy of my hand-written personal lecture notes to the
lecture itself, which you can use as a starting point. But be warned that
these notes record, for the most part, only what I would write on the board
(and that only roughly). You are expected to "fill in the gaps" by completing
sentences, turning the rough ideas I've written down into the more precise
ideas I'll say out load, etc.
If you want to see an example of scribe notes from another class,
take a look at
this tar file
(from a related class by
Write your notes using LaTeX, with figures in Encapsulated PostScript
(generated from xfig or Adobe Illustrator or whatever you want).
Start from the provided scribe template,
which sets the style.
Try to write the lecture notes for a class on the same day, because that will
save you time. You should finish the first draft of your notes and send it to
me by two days after the lecture. Then I'll either send you comments via email
or we'll schedule a meeting to go over your write-up, I'll make suggestions,
you'll make a second pass, and send it to me. I'll make the final pass,
and post it on the webpage. The goal will be to get the notes out by one week
after the corresponding class.
The main requirement of the class is the project.
The ideal outcome of the project is to have a publishable paper,
or something that can be polished into such a paper, at the end of the class.
This ideal is meant to be an attractive goal rather than a worry of
involving too much work.
The idea is that the class project will help you achieve the (more important!)
goal of doing research and publishing papers.
You do not have to achieve the ideal outcome--that is the nature of
research!--but that should be your philosophical goal.
If you do not achieve good results, your write-up should instead describe good
approaches or ideas for solving the problem that you tried and why they don't
The project does not have to be exclusively about data structures,
but the topic should have data structural content. For example, you might take
a data structural stance on a topic within your main area of research.
I will be available for brainstorming about possible topics of interest.
It is a requirement that the topic is of interest to you :-),
and you also need to check with me that it satisfies the course requirements.
You can work in a small group of students in the class if you find common
interests. You are also welcome to collaborate with anyone outside the class,
including me. (Again, that's the nature of research!) But you should tell
me who you are working with ahead of time.
The format of a project is flexible. There should be a paper component,
on the order of 10 pages, let's say in the range 5-20 pages.
And you will give a presentation about your project.
Here are some possible types of projects:
- Learn about an open problem and try to solve it
(and hopefully solve it).
- Invent a good, new open problem.
Here the posing of the problem is the key contribution; but you should
also think about how it might be solved.
- Implement a data structure (or more than one) and experiment with it.
This is the area of experimental algorithmics. Examples of outcomes:
understanding the behavior of a data structure in practice;
comparing two or more data structures in practice;
determining whether a previously unimplemented data structure
- Survey an area of data structures that is normally not brought together,
or with an unusual slant.
One idea I have here is a collection of several (known/important)
open problems throughout data structures or within a specific subarea.
- Something else cool that you invent.