NATHANWIEGAND.COM

For years I’ve wanted to write a book. My friend Charles and I thought about writing a book on probability back when I was an undergraduate. Most recently I’ve been thinking about writing a computer science book which is an introduction to algorithms. This was spurred by my teaching exactly such a class this semester.

CS260 at the University of Alabama is entitled “Foundations of Computer Science”. This course is intended to be an introduction to the theoretical aspects of the field, ranging from analysis of algorithms to simple datastructures. This course is for second semester students, so unfortunately they’ve only had one semester of programming and don’t have a very strong math background. This means that we can’t do the more rigorous analysis of algorithms and fun proofs that would need things like counting and inductive proofs. So, I’ve decided to take a different tact. I’m trying to help them develop an intuition of the concepts by starting with the implementation of some algorithm (sorting algorithm, actually) and walking them toward a function which is computes how much work is required without actually doing the work. By then plotting these function they can get a visual representation of how much work is actually being done and see its relation to other mathematical functions. This has actually proven pretty effective at teaching asymptotics without actually teaching asymptotics.

Therefore, the book that I want to write is an introduction to theoretical computer science via empirical analysis. What if someone scoops me because of this? I don’t care. I think that this would actually help a lot of students and if I don’t get enough time to do it, then someone else should. So, I’m going to try to start putting the sketches of sections here. Eventually I’d like to set up a system like Bryan O’Sullivan had for Real World Haskell with random internet users being able to comment on parts of the books with suggestions. Stay tuned!

I just saw a post on /r/programming asking people to describe their dumbest coding mistakes. Instead of just posting one of mine there, I’ll do it here.

Many, many years ago, back in 2005 when I was a green grad student and an all around n00b, I got the opportunity to work on the auto-discovery daemon for OpenMosix (may it rest in peace). OpenMosix was a self-assembling cluster system. You would just install it on several machines in the same subnet, and bam you’d have a cluster that automatically distributed jobs. On with the story.

I don’t remember what part of the daemon I was working on. It was already doing some auto-discovery and self assembly. I was pretty pleased. The basic idea was that it would fork off a listener and have another process that would chatter on broadcast announcing its presence. At some point, about 5 minutes into the run, the whole thing would segfault. More precisely, at 4:38 in, it would segfault. Wait, what? The same exact amount of time to crash? That’s just weird! Well, no kidding.

This killed me for several hours. I had no idea what was up. That’s the day I got familiar with using GDB to attach to running processes. And what did I discover? I out clevered myself. I had code like this:

fprintf(stdout, "This is some stupid debugging \
message that I'll eventually remove\n");

That looks all well and good. Why is a printf breaking? Well, it’s breaking because of this line:

fclose(stdout);

See above where I said that I out-clevered myself. Basically, I wanted to turn off all that annoying debugging chatter. So, what the hell, why not just close stdout? It worked! No more chatter. Well, that’s not all. See, whenever using printf, I was writing to a closed file handler… but it was buffered. So, my program would continue to run, dumping silly messages to this buffer until the buffer ran out of space and it smashed some import part of memory causing the segfault. Oops.

So, what did I learn? Debugging messages are important, but use some kind of clever logging system, even if it’s just a series of macros. Sometimes, if your idea seems really clever, take a step back because it might lead you to more trouble than it’s worth.