Spinning Yarns

It was quite possible that, upon reading the subject of this message, your first reaction was something like “Gesundheit!” Rather than a sneeze, however, Abu ‘Abd Allah Muhammad ibm Musa al-Khwarizmi was an Arabic mathematician of the mid-8th Century, who first wrote down, for the Western world, the Hindu principles of mathematics we now learn as children under the name “arithmetic.” His name, through a timeless legacy of bastardization, has given rise to the modern word “algorithm,” which is essentially the mathematician’s word for “recipe.”

To those who study computer science, algorithms are meat and drink — the whole field of computer science can basically be described as the art of transforming problems into mathematical abstractions so that they can be solved by purely mechanical means. In short, computer science is the art of finding the proper wrench to use to pound in the correct screw. To most people, however, the term “algorithm” sounds like the name of some funky kind of dance.*

* Contrary to the implications of recent press coverage, it is not a contraction of “Al Gore-ism”. While Mr. Gore may claim to have funded the invention of the Internet, he most certainly didn’t invent arithmetic.

In actuality, however, an algorithm is nothing more than a well-defined and repeatable sequence of simple instructions for solving a problem. As an example, suppose you had a standard pack of cards, and your task was to find the King of Hearts. Here is an algorithm which will solve this problem. Follow it step by step, except where it tells you to jump to a different step:

1. Place the pack of cards in your left hand, face-up
2. If there are no cards in your left hand, stop: The card is missing!
3. If the top card is the King of Hearts, stop: You found the card!
4. Remove the top card from the pack and place it aside
5. Go to step (2)

Obviously, this is such a trivial example, that you might be tempted to wonder why anyone would bother — but rest assured, this is just an example, and many other problems have much more complex solutions than this. I just wanted to give you an idea of what I’m talking about here.

Now, I can hear you asking, “why the hell should I care about algorithms?” After all, we know how to solve the simple problems in our daily lives, and we all know that no algorithms exist to solve more complex problems like “how do I explain to my girlfriend why I came home with lipstick all over my collar last night?”** Well, I’m going to give you an example of how algorithms affect our daily lives.

** “Honey, you were drunk and you missed my neck.”

Last night, while I was driving home, I occasioned to be passing through Hanover, New Hampshire. In doing so, I stopped at a certain traffic light, behind a boxy little SUV which was already waiting there when I arrived. The street to the left of us had the green light, and there was a gray car sitting there, but its driver was waiting for someone else to return from a nearby house, and so had no need or desire to go forward at that particular time.

You are probably aware that most modern traffic lights work in conjunction with sensors buried in the roadbed near the intersection they control. These sensors detect when there is something heavy (like a car) sitting on the road, waiting for the light to turn — and this is used to make the lights operate more efficiently. Unfortunately, in this particular case, the gray car was sitting on the sensor pad for the adjoining street, making the light think it was waiting to go forward.

On top of that, the SUV in front of me was too far back to activate the sensor pad for the road we were on. Thus, the light was thinking, “gosh, well, there’s nobody who wants to go straight along the road, and there’s definitely someone waiting to enter from the left, so I’ll just hold the light green for them, until either they go, or someone else wants to use the intersection.” That’s actually a pretty reasonable design for a traffic light, since it tends to minimize the amount of waiting drivers have to do when traffic is light.

Unfortunately for me, however, the driver of the SUV did not seem to realize what was happening. He sat there for fully three minutes (during which time I figured out what was going on) until I finally got out of my car, and went up to tell him to pull forward. Once he did that, the light cycled almost immediately, and we were able to move on with our lives. But considering that he had been there for some time before I arrived, I wonder how long he would have stayed there (I had seen him from the previous intersection, several hundred yards up the street, while I had been waiting at that traffic light). I suppose eventually he would have gotten entirely sick of waiting for the light, and just gone … it’s not like I haven’t done the same thing, in other circumstances. But the point of this example is to illustrate how just a little understanding of how algorithms work, can save you the risk of being pulled over for a moving violation, by the friendly local constabulary.**

**(This is New Hampshire, not Los Angeles, so “being pulled over for a moving violation” does not mean that they pull you over in order to beat you up.)

Now, you could argue that the old-fashioned “dumb” traffic lights, the ones that just operated on a timer and cycled through all the combinations, would not have been faced with this trouble. That’s true, of course, but that would also mean that every time you got to that stop light, you would have to wait an average of half the length of the complete cycle for your turn to come around. That would be really annoying for too much of the time, just for the ability to avoid the pathological case I’ve described here.

So how could this have been avoided?

The simple solution is, “make sure you’re reasonably close to the white line at a traffic light.” That’s why they put those lines there, after all. But how could you have designed the system to do better — given someone like this SUV driver, who didn’t do that — without making it annoying to the rest of the drivers?

One difficulty with these traffic lights is that they can’t usually tell the difference between one car sitting there obstinately on the sensor pad, and a stream of cars passing over it in close succession. So, the obvious solution, of having it give up if someone just sits there, would actually result in random-seeming light changes even when there was nobody at the other side of the intersection. So how about replacing the sensor pads with an “electric eye” system, that can differentiate between a car just sitting there and many cars moving? Unfortunately, such an “eye” cannot distinguish between a car and, say, a mischievous pedestrian — so that would clearly not be suitable (pedestrians can’t fool the current system because, with a few notable exceptions, they do not weigh enough to trigger the sensor pads — and besides, they’d have to stand in the middle of the road.)

As you can see, even a very simple problem like this has hidden intricacies, that could make it interesting — or at least amusing — to consider in more depth than might at first seem merited. I have found that almost everything in this world has some interesting puzzles lurking inside it, and that is a source of endless amusement for me. As a former roommate’s former roommate used to say, “a simple mind is a toy forever,” and by that reasoning, I will never be bored.

The point of all of this isn’t to try to convince you to study these puzzles mathematically, as some do, but rather to encourage you to keep your eyes and your mind open to the interesting complexity of the world around us. It’s a fascinating place to live, and if you keep your wits about you, it can be an endless source of entertainment.

And speaking of entertainment, I should probably go finish my homework.

Filed by Michael at 16:44 under Personal
Comments Off