Religious wars and LaTeX tools

On his blog, Lance Fortnow recently mentioned that for several years he has been happily using Windows instead of Unix. This provoked a lot of fervent comments, some of which are pretty funny.

I try not to take sides in OS debates. I use a Windows PC at home because my wife and I occasionally need to take work home from the office, and that's what is used there. In my youth, I used to enjoy tinkering more with the hardware and software, and for a while I was using a dual-boot Windows and Linux setup. But nowadays I find the whole issue distracting. Computers have become a commodity in the economic sense, but not in a functional sense. When I use my computer, I want to be able to use it as a tool to do my work and not have to give a second thought about what OS I'm using, and how it needs to be tweaked to work properly with my applications, what security patches I need to apply, etc. Application software should be platform independent (to the extent possible), and data should be stored using open standard file formats. We have a long way to go to reach this point.

I really feel let down by Larry Ellison and Scott McNealy. It's been about 10 years since Java and the Internet Appliance were promoted as the solution to this problem, and I'm still waiting. They promised way too much, way too soon, and I think it really soured everyone on the whole idea. But now that broadband internet access is finally becoming widespread, maybe we'll see another attempt at popularizing this concept.

The one thing about the Java phenomenon that has kind of surprised me is that it was seen as primarily a boon for software developers and not hardware developers. I think this should be just the reverse: the JVM totally opens the door for hardware innovation. PCs get a little faster each year, but it's been a long time since we've seen anything truly new in PC hardware. Nor should we expect anything new. PC designers need to accomodate Windows' requirements, and that limits what the engineers can do. But once a critical mass of Java applications exists, the sky is the limit as far hardware is concerned. A JVM will need to be written for each new hardware platform, but this should not be too hard. All the applications, as well as the UI layers of the OS which are themselves written in Java, will immediately transfer to the new hardware. The performance improvements made possible by radically new hardware designs will easily outstrip any inefficiencies introduced by the VM layer. This has yet to happen on the desktop, but I think it is happening to some extent at the small end of the spectrum, in cellphones.

But I digress... Of the comments to Lance's post, of particular interest to me were several that described tools for using LaTeX on Windows. It was reassuring to see WinEdt described as being a nicer editor for handling LaTeX than the Unix-based Emacs (although this is probably not a majority opinion), since this is what I'm going to be using. WinEdt acts as a front-end to the MikTeX software package which does the actual typesetting.

WinEdt is a text-based editor; a couple of WYSIWYG editors were also mentioned in the comments. Scientific Workplace is a commercial package which, due to its high cost, is not an option for me. LyX is an open-source document processor which seems very interesting. Lyx was developed for Unix, but there is a Windows port available. I'm going to stick with WinEdt for now, mainly to force myself to learn LaTeX code, but perhaps in the future I'll take another look at using LyX.

While I'm on the subject of LaTeX, let me mention the books I plan on using to learn this. Learning LaTeX by David F. Griffiths and Desmond J. Highman, and First Steps in LaTeX by George Grätzer, are both tiny texts which promise to get me up and running quickly. I'll let you know how it goes.

My next post will be on graphics tools to provide diagrams for my LaTeX documents. In the meantime, if you have a favorite LaTeX program or book, please let me know!

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!