People who build tools have a special responsibility to make the tools reliable--one that people who write end-user applications usually do not share.  One reason for this responsibility is that people use those tools to build other applications, and the users of those applications do not communicate directly with the tool builders.  That lack of communication makes it hard for the tool builders

I am a customer of a software company that recently made a surprising announcement:  They had become so dissatisfied with the number of bugs in their product that they were going to suspend all new-feature development and work exclusively on fixing bugs until they were once again satisfied with their product's reliability. It is rare for a company to take such a courageous stand, and it reminded

Recently a friend asked me if I could take some short video clips at a party and splice them together into a souvenir DVD.  I was about to point out that I did not own a video camera when I realized that I actually did own one: a digital camera about the size of a pack of cigarettes that usually hangs on my belt in case something happens that's worth photographing.  I had bought it as a still

Every once in a while, a paper comes along that is both a joke and not a joke at the same time.  One example of this phenomenon is Don Knuth's paper The Complexity of Songs.  The word complexity in this context means algorithmic complexity: the length of the shortest program that is capable of producing a particular song's lyrics as its output.

As people involve computers more in the production of

Here's a situation that I've seen so many times that I've lost count. Someone builds a system with a clean architecture. After a while, users realize that there are important things that the system cannot do.  They ask for new features.  Those features do not fit well in the architecture, but they get shoehorned in anyway as a patch--because they're important.

Lather, rinse, repeat.  After a

If you have ever used music-production software such as Ableton Live or Cakewalk Sonar, you know that one of the important steps in making such a program useful is to choose the appropriate buffer size.  If it is too small, you will get crackles in your speakers whenever your operating system has to do something in the background.  If it is too large, there will be an unacceptable delay between

In my last note, I talked about the idea of something happening "with probability 1."  Such events are bound to happen eventually, even though there is no way to predict just how long it might take.  A similar notion occurs with algorithms that have a worst case that is much worse than average.  Two such algorithms, or categories of algorithms, are quicksort and hashing.

Hashing typically relies

Sometimes people will describe an algorithm by saying that it works "with probability 1."  It is almost true, but nevertheless naive to believe, that such a claim is the same as saying that the algorithm always works.  The difference is subtle, in much the same way as the difference is subtle between the notions of "infinite" and "unbounded."

Here is a simple example.  Suppose you want to cause