Web resources: College course materials

I plan to spend a little bit of time each week reviewing different web resources related to theoretical computer science. I've got a number of links that I've been accumulating, but my bookmarks are a complete mess and I need to spend the time to organize them, as much for my own sanity as for the purpose of sharing them here.

Let's start with one of the most important categories (from the perspective of someone trying to self-instruct in computer science), college course materials. It stands to reason that computer science faculty would be early adopters of using computers and the web as means to communicate with their students, and a lot of this material is freely accessible. Syllabi, lecture notes, and problem sets can be found on nearly any subject (although problem solutions are often password-protected). For example, if I Google on "complexity theory class notes", I get hundreds, maybe even thousands, of relevant hits.

Since there is so much good material, and also since the links have a tendency to move over time, I won't attempt to create a list of individual class notes. But I would like to list a few course repositories, for lack of a better term, and also mention a couple of specific course sites that caught my eye.

The big daddy of course repositories is MIT's OpenCourseWare project. This site contains class materials for over a thousand of MIT's courses and is still growing. Class syllabi, lecture notes, problem sets, solution sets (sometimes), and occasionally multimedia presentations can be found for each class.

Courses are organized by department. Of particular interest for us would be the Mathematics and the Electrical Engineering and Computer Science departments (many of the theory courses are actually co-listed in both areas). There is so much good stuff here that I would have to pretty much copy the entire course list to mention everything worthwhile, but let me pick out just a few:

• Ron Rivest's Automata, Computability and Complexity
  
• Dan Spielman's Advanced Complexity Theory
  
• Albert Meyer's Computability Theory of and with Scheme

One last course that I must mention is Gilbert Strang's Linear Algebra class. What makes this one interesting is that there is streaming video of all of the lectures. The quality of the video is also rather remarkable. The lectures were filmed in a large hall, with a camera at the back of the room with a wide-angle view of Prof. Strang at the front of the class, and a second camera which zoomed in on the text as it was written on the blackboards. This avoids the motion-sickness inducing panning back and forth that can occur with a single camera following a teacher in a small classroom. The editing between the two cameras is very well done. This course really stands out as an example of the potential of the OpenCourseWare project, and I would love to see the other courses get the same treatment.

Moving on, the next course repository is much smaller but more focused in scope, and is my personal favorite. ArsDigita University was a product (and victim) of the dot-com boom. This school was a combination teaching experiment and recruiting tool created by Philip Greenspun and the ArsDigita Corporation. It had a highly focused curriculum designed to provide the equivalent of an undergraduate education in computer science in a one-year program. The school only existed for one year, but all of the course materials (including video of most of the classes) has been preserved online. The quality of the materials is uneven, but the courses most relevant to studying theory, Discrete Math, Algorithms, and Theory of Computing, are quite good. These were all taught by Shai Simonson, who also served as director of the program.

The last course repository I'd like to mention is something relatively new, Rice University's Connexions project. This site utilizes a software environment specifically designed for the project to organize and present the course material, so every course has a consistent "look and feel". Anyone can contribute to the project, not just Rice University faculty.

There is not very much relevant coursework on this site yet, and it's hard to find what is available, because the courses are not organized by discipline. But I think there is some potential here. To get idea of what this site has to offer, check out the Intro to Logic course.

Now, here are a few of the many, many available individual online course sites that I thought were worth a special mention:

Video of the Structure and Interpretation of Computer Programs course by Harold Abelson and Gerald Jay Sussman themselves can be found here. As you may have gotten the impression, I love courses that provide video of the lectures, and these are very good. An online version of the classic text is also available here.

Christos Papadimitriou's course Reading the Classics consists of reading many of the original papers that have shaped theoretical computer science. Links to online versions of most of the papers can be found here. I love the idea of this course. I also think it would be great if this could be turned into a text. Like Martin Davis' The Undecidable, which contains classic papers on computability, this text could contain the classics of algorithms and complexity theory.

Finally, the site www.complexitytheory.com, despite the somewhat official sounding domain name, is the course website for Steven Rudich's graduate complexity theory class. In some ways this is a pretty run-of-the-mill site, but it does contain nice lecture notes covering advanced topics in complexity theory. The highlight, I think, is the final lecture which covers Rudich and Razborov's Natural Proofs paper.

Enjoy!