6.897: Advanced Data Structures (Spring 2003)

Prof. Erik Demaine

Requirements

Everyone is welcome to audit/sit in/listen to the class.
Students taking the class for credit have the following requirements:

Scribing

Content. 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 Michael Bender).

Format. 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.

Timing. 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.

Project

Goal. 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 work.

Topic. 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.

Groups. 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.

Format. 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: