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!

Cascading style sheeeeeit

Hello again,

As I mentioned a few posts ago, when I decided to set up this blog on its own domain, one of my goals was to have an accompanying website where I can collect various resources relating to theoretical computer science. There is a limit to how many links you can stuff into the sidebar of a blog.

I initially was using some old html that I had left over from several years ago for the website. The overall structure was frames-based, and it used tables to provide some of the formating. (At the time when I originally wrote it, CSS was not yet in widespread use.) So I decided that before I start adding content to the site, I better rewrite it using current techniques.

I went to my local bookstore and selected a book on HTML and CSS, and began working through it. The first thing that struck me is that HTML itself is pretty much unchanged from 6 years ago. The other thing is that web design nowadays looks nothing at all like what I was familiar with. Well, I dutifully worked through the examples in the text, created a simple layout with a masthead, sidebar and main body area, and tried it out. It was utterly unreadable. I also found that making (seemingly) minor tweaks to the CSS resulted in drastic changes to the layout, with the sidebar switching sides, the contents disappearing from view, and other generally bad things happening.

Finally, I punted. I copied the CSS from my Blogger template and stripped out most of the Blogger-specific stuff, and used that. Eventually I'll learn how to properly use CSS (I've got a new, better book to read) and redo the site, but for now it's workable, and aesthetically it matches the blog.

Since I was tinkering around with the Blogger template anyway, I also went ahead and added some tweaks to that. Recent comments now appear in the sidebar, and there are trackback links (via Technorati) at the bottom of each post. Now I just have to wait for someone to link to a post so I can try it out. I promise that my next post will deal with something actually connected to theoretical computer science, so there might be some content worth linking to!

The ultimate iPod

Before I say anything else, let me just mention that I've gotten linked to for the first time! (Or at least, this is the first one that I'm aware of.) Woo-hoo! Thanks, Jeff/Ernie.

I received an ad for the following item in my email today:


Now if you've been meaning to get yourself an iPod, and you're a big Harry Potter fan, and you have a nice wad of money burning a hole in your pocket, you might want to check out this item at the Apple Store. (BTW, since these links will undoubtedly break at some point in the future, if you're reading this in the archives months from now, this ad shows the Harry Potter Collector's iPod with the Complete Harry Potter audiobook collection. The iPod has the Hogwarts crest etched on the back.) This ad reminded me of how I'm slowly assembling the ultimate collector's iPod. Let me explain:

A number of years ago I was browsing at my local bookstore and came across Richard Feynman's Six Easy Pieces. After skimming through the book, I bought it, but for some reason I never got around to listening to the lectures and it languished on my bookshelf. Maybe a year later I stumbled across it again and finally put the first lecture in my stereo. I was instantly mesmerized. I thought it was just incredible – if I had heard this while I was still in college, I probably would have changed my major to physics.

For those of you not familiar with it, Six Easy Pieces contains the introductory lectures from the The Feynman Lectures on Physics. These were recorded and transcribed from a two-year beginning physics course that Feynman taught at CalTech from 1961 to 1963. In trying to describe this, it's hard to do justice to the combination of sheer joy and absolute clarity that Feynman brought to the lectures. If you've never heard it before, you owe it to yourself to get ahold of the audio version of Six Easy Pieces and listen to it.

So anyway, after I listened to the introductory lectures, I immediately ran out and bought the (print version) of The Feynman Lectures on Physics. However, I quickly discovered that reading the printed lectures just didn't convey the same emotional impact as listening to Feynman speak. So I looked into getting the audio versions of the lectures and realized that there were a couple of problems. First, it would be very expensive to collect all the audio cassettes for the 100+ lectures. Second, the publisher for whatever reason had bundled the cassettes into sets of 6 which did not follow the ordering of the original course. So to listen to the lectures in order, I would have to buy the whole collection and then shuffle the cassettes around to get them into their proper places.

Well, a couple of things have happened since then. First, the publisher has slowly been converting the analog recordings to digital CD format (for example, here is the first set). They're now bundled into sets of 12, making them (somewhat) more affordable. The other thing that happened was the iPod phenomenon. And this gave me the ideal solution to how to manage all of that audio: I've been dutifully aquiring the lectures as they're released and transfering them onto my iPod. As I do this, I relabel the lectures so that they will appear in their proper sequence. Once all of the lectures have been converted to digital, I will finally be able to listen to them the way that they were originally delivered by Feynman. And the whole package will fit into my shirt pocket!

Once I'm done with this project, I think I'll have the back of my iPod etched with some nice Feynman diagrams to create my own "collector's edition."

Blogging 101

Hi again everyone,

Well, I'm sad to say that I've spent most of my free time for the past week just learning the basics of blogging. The Blogger interface itself is intuitive and you can pretty much just learn it as you use it. But as with other technological innovations, there is a temptation to fritter away one's time by endlessly tweaking the interface. So far I've done only the very basics, by adding some links to my sidebar and registering the blog with Technorati, a company that indexes and tracks links between blogs. Blogger maintains a page called BloggerHacks that includes code you can add to your blog template. One neat thing you can do is to add a 'recent comments' section to your sidebar in a fashion similar to the 'recent posts'. I'll have to implement that one when I have the time. Something else I've come across that I want to add to this blog are trackbacks. A trackback is essentially the inverse of a link — it shows who is linking to your page. Probably no need to hurry on implementing this one, though, since at the moment there probably isn't anyone else linking here at all.

For those of you for whom this is all old hat, please excuse my naiveté. I tried looking in a few books on blogging for the technical details of this stuff, without too much luck. It seems the best way to learn the details is by looking at other people's blogs. One of the best examples I've come across is The Geomblog by Suresh Venkatasubramanian. Lots and lots of technical goodies on Suresh's blog. Of course, I don't want to make it seem like the technical glitz is more important than the actual content of a blog. From the point of view of helping one to learn theoretical computer science, I think the best blog by far is Lance Fortnow's Computational Complexity, which is on the low end of the 'glitz' scale.

One downside of the time I've spent playing around with the blog is that I haven't actually studied any TCS in the past week. I'm starting to feel withdrawal pangs. But reading blogs and randomly following links from blog to blog is extremely addictive, more so I think than for regular Web content.

Here's a real nice goody I came across in my travels: ASCIIMathML is a JavaScript utility that will dynamically transform LaTeX-style math formulas in a web page into MathML markup. This looks like a very promising solution to the problem of how to render mathematics on this blog. I'll be trying this out in a future post. Of course, the reader still needs to have their browser configured properly to display MathML, but presumably someone seeking out a computer science blog would be able to take care of that.

New Home

Just a short post tonight to point out the obvious, which is that this blog now has a new URL and a new name: Learning Computation.

I was thinking about the fact that eventually there may be a lot of images embedded in these posts, and there needs to be a place to store those images (which is something that blogspot doesn't provide). I didn't want the location to be tied to my current ISP or some other domain that is subject to change, so I decided to create a dedicated domain name for the blog. This is amazingly easy and inexpensive to do nowadays. Even so, when it came time to enter the domain name in the application form, I had to pause for a moment and think about the purpose of this blog, and I decided to change its name slightly to broaden its scope.

You may have also noticed the accompanying website. Please excuse the roughness of the design; it should improve greatly over time as I develop it. This is where I plan to put links and other kinds of resources for theoretical computer science. If you know of any great sites that you'd like to see linked there, please pass them along to me. (And thanks, Troy, for the links you've already sent me. I'll be adding them when I have a chance.)