This Course at MIT

Below, Prof. Demaine describes various aspects of how he teaches 6.851 Advanced Data Structures.

Dynamic Material

• This course is all about how to store your data and how to access it efficiently. There are a lot of different meanings of that, such as what the data could be and what kind of accesses you want to do efficiently. It is a big area of research, and one of the oldest areas of computer science. For every type of query you might want to do on your data, there is a corresponding data structure. Most of these structures we know, but for some of them we still do not know the best way to answer these kinds of queries very efficiently.
• In this course, there is a mixture of material. A lot of old material that was completed in the 70’s was done perfectly, so in those aspects, the subject matter has not changed much. This material is still important, but there has not been much evolution. In general, I try to focus on the newer developments in the field. At least half the course is dedicated to research that was done in the last decade—some of it by me, and some of it by my colleagues. The course, in this sense, is still a moving target.
• The teaching assistants (TA’s) have shaped the content of the class substantially. Nearly every time I have taught the course, I had a TA who knows data structures really well, but in a somewhat different way from how I do; in such cases, I reserved a few lectures for their topics of expertise. Over the years, I have collected all these different influences from TA’s in the lecture content. I can point and say that one group of lectures was introduced by a particular TA, and that the next few lectures were introduced by another TA. These TA’s have really made the course what it is today.
• This course was originally modeled after a class at the University of Waterloo, where I was a graduate student. My advisor had taught a course on advanced data structures so the first time I taught this course at MIT, it was closely modeled after what I had experienced as a student. This course has since evolved many times under the TAs’ influences, though there are still parts of the course that reflect the original iteration. I always incorporate new material produced by researchers in the field, and I also reference the materials that have been produced by people who may have taught a similar topic in the past.

Scribe Notes

• I handwrite notes for all of my lectures and I really like that style of lecture notes. These are the notes that I bring into the classroom and use to write on the blackboard and to remember what to say—though I try not to look at them! Essentially, they are supposed to be what I talk about in class but they are not very detailed. They omit a lot of the things that I remember easily or things that come to me quickly. In the handwritten format, you cannot fill in all the details. The idea of student scribe notes is to be a little more thorough and explain the material in a more textbook-style, especially since there is no official textbook for this course. The exercise is to have students write these scribe notes, which are based on my notes and what was covered in lecture, and try to fill in all the gaps. This is partly just an experience in writing for the students because it is hard to write lecture notes and hard to write a textbook.
• This course has been offered five times over the years, and while sometimes the lectures change, a portion of the lectures are essentially the same as in previous years. There are usually some scribe notes from the past that students can build upon when constructing their own. Two or three students scribe each lecture. These students also collaborate with past versions of the course, which makes things interesting. The hope is that the notes keep iterating and get better each year.

Problem Sets

• Similar to how the course is organized, the problem sets are designed to focus on a particular types of data structure. There are problems that are motivated by different models of time travel, what that means, and whether one can prove that time travel is impossible or possible in different models. As we think about these problems, it makes the scientific research a lot more fun by infusing cool, interesting, quirky problems inside of it.

In Spring 2014, this course was offered in the inverted lecture format, and Prof. Demaine also shares his insights on the changes to the course as a result of this new format.

Lead Instructor (Prof. Erik Demaine)

The lead instructor prepares and delivers all of the lectures for the course. Other responsibilities include working with the teaching assistants to select the problems that are posed in the problem sets. Typically, Prof. Demaine offers his ideas of what would be a good problem, but as a group, the course team chooses the ones that make the best problems. Then, among all of those problems, they organize the problems into groups that form the best problem sets.

Teaching Assistant (mostly PhD students, occasionally Master’s students in computer science)

The TA’s handle administrative aspects of the course such as making sure all of the problem sets are available when assigned and grading the problem sets. They also play a role in the design of the problem sets.