Quickselect FTW!

More than a year ago, I answered a question on Stack Overflow about the Quickselect algorithm, which takes some unsorted data and finds the k-th smallest value (that is, the value that would be in position k if you were to sort the data). The person asking the question had seen multiple technical descriptions of the algorithm, but was looking for a simplified explanation that was not expressed as computer code. I tried to illustrate the algorithm in story form, and others seemed to like my story. The surprising part to me has been that votes continue to trickle in even today, and that this deliberately silly story is now my most upvoted answer. I suppose there's a lesson in there somewhere...

You walk into a gymnasium containing 200 children. It is September 8th, so you have a burning desire to find the 98th shortest child. You know that you could line them all up from shortest to tallest, but that would take forever. “I know”, you think, “I could use QUICKSELECT!”

You walk out into the crowd, close your eyes, stick out your finger, and spin around three times. When you open your eyes, you are pointing directly at one of the children, Peter Pivot. You say, “Quickly! Everybody shorter than Peter, come stand over here. And everybody taller than Peter, go stand over there. If you're the same height as Peter, you can go into either group.”

The children shuffle around, and soon they are standing in the two groups. You count and find 120 children in the shorter group, and 79 children in the taller group. You know the 98th shortest child must be in the shorter group, so you tell Peter and the 79 taller children to sit in the bleachers.

You again close your eyes, stick out your finger, and spin around three times. When you open your eyes, you are pointing directly at Peter's sister, Paula Pivot. You say, “Quickly! Those of you who are still standing. If you're shorter than Paula, come stand over here. If you're taller than Paula, go stand over there. If you're the same height, you can go into either group.”

The children shuffle around, and soon they are standing in the two groups. You count and find 59 children in the shorter group, and 60 children in the taller group. You know the 98th shortest child must be in the taller group, so you tell Paula and the 59 shorter children to sit in the bleachers.

You again close your eyes, stick out your finger, and spin around three times. When you open your eyes, you are pointing directly at Paula's cousin, Prudence Pivot. You say, “Quickly! Those of you who are still standing. If you're shorter than Prudence, come stand over here. If you're taller than Prudence, go stand over there. If you're the same height, you can go into either group.”

The children shuffle around, and soon they are standing in the two groups. You count and find 37 children in the shorter group, and 22 children in the taller group. You know that Paula and 59 other shorter children are sitting on the bleachers. Along with the 37 shorter children still standing, you know that a total of 97 children are shorter than Prudence. Therefore, Prudence is the 98th shortest child!

Quickselect FTW!

On Balanced Trees and Car Insurance

I usually don't teach our Data Structures course, but I often give a guest lecture about balanced binary search trees. This comes right after they've learned about plain (unbalanced) binary search trees. Often the previous lesson has ended with an illustration of what happens when values are inserted into the tree in sorted order.

After reviewing that pathological case and how it can easily arise in practice, I dive in and explain how to keep the trees balanced. In my case, I use red-black trees, but the exact choice of balancing scheme isn't critical to my point here. At the end of class, I ask them how much faster they think the balanced trees are than the unbalanced trees. They're shocked when I tell them that, most of the time, the balanced trees are slower than the unbalanced trees. As long as the data arrives in a reasonably random order, the plain binary search trees will actually end up being fairly balanced, without doing any extra work. No mucking around with colors, no rotations—of course the balanced trees are slower!

So why bother?

I tell them that it's like buying car insurance. When you buy car insurance, you hope that you're just throwing your money away. At the end of the year, if you haven't been in any accidents, you're happy to have wasted that money. Why bother? To protect against the uncommon case, to keep one unlucky event from turning into catastrophe. You pay a little bit extra all the time to keep from paying a lot extra every once in a while.

Wrong Number

Is it time to overhaul the user interface of the phone system?

A few months ago we started getting a lot of calls that were wrong numbers. Before that we used to get maybe one a week, but suddenly we were getting 5 or 6 a day. After an initial period of frustration, we eventually started to apply our debugging skills.

Our first guess was that somebody was distributing our phone number on a flyer or something, either as a prank or by accident. But this didn't make sense because every caller was asking for somebody different. “Hello, is Juan there?” “Hi, Elizabeth/Gary/Tanya/Carlos?” Or the ever popular “<pause> Who is this?!!” No, dude, you called me, so you tell first.

Ok, scratch that idea. Hmm, I suppose we could always ask. “Sorry, wrong number, what number are you trying to reach?” At last, some progress. Our phone number is 987-654-3210 (not our real number). The people who were calling us were uniformly dialing 654-321-0xxx. The 654 area code is for an area maybe 20 miles away, so lots of people in our area code were dialing numbers there. Even worse, there are up to 1000 numbers in that area code that match this pattern. No wonder we were getting a lot of calls!

The reason they were getting us was that they were forgetting to dial a 1 first. Without the 1, the phone system was interpreting this as a local call within the 987 area code to 654-3210, with the extra three digits on the end simply being ignored. On many (most?) cell phones the 1 is not necessary, so people lose the habit of dialing it. Then when they use a land line, where the 1 is required, they get us.

With this insight, we contacted the phone company. It took three tries and many patient explanations to even get somebody to understand what the problem was. I asked what had changed in the system recently, because clearly something had changed to cause the sudden increase in wrong numbers.

“Uh, I don't know. I'll ask our tech guy.” A few minutes later. “Our tech guy says the 321 exchange in the 654 area code is a Cingular exchange. You should call them.” “But how is that supposed to help? The phone calls are originating in your system and never getting out of your system, so even if they made a change over there, it wouldn't change what's happening here.” “Well, you should call Cingular.”

Predictably, Cingular couldn't help. They couldn't even tell us if the 321 exchange was new because “our computers don't tell us that”.

The really frustrating thing about the problem is that it's so easy to fix. It should be easy for the system to detect when somebody has dialed a 10 digits but is being connected to a 7-digit number. Give the caller a warning and ask them to redial! It's possible this might break some systems with extensions, where the leftover 3 digits indicate the extension. So perhaps disable the warning if there is a pause between the 7th and 8th digits.

Has anyone else had this problem?

Lessons from Laundry

Several years ago, I was advising a student on some code he had written for a data structures class. This code performed a set of actions on a temporary counter, and he was resetting the counter to zero after the last action so it would be ready for the next cycle of actions. I suggested setting the counter to zero just before the first action instead of just after the last action. He asked why, and this was my explanation.

This is also an example of what Jeanette Wing and others call computational thinking.

You know when you're doing laundry and you have to clean the lint out of the lint trap? Of course, this is not mandatory—the dryer will still work if you don't clean out the lint, but it'll work more efficiently if you do.

Now, you have two basic choices as to when to clean out the lint. You can clean it out when you remove clothes from the dryer, or you can clean it out when you put clothes into the dryer. Either protocol will work fine as long as everybody in the house is following the same protocol.

But suppose you have two people in the house following opposite protocols. Let's say that you follow the clean-after protocol and your housemate follows the clean-before protocol. If you do a load of laundry and clean out the lint trap when you're done, and then your housemate does a load of laundry, then the worst that will happen is that the lint trap will already be clean when your housemate goes to clean it.

On the other hand, if your housemate does a load of laundry and cleans out the lint trap at the beginning, and then you do a load of laundry, now you have a problem. When you go to clean out the lint when you're done, you'll find it extra full. You might even need to run the dryer a second time because your clothes didn't get completely dry.

The point is that some protocols, such as the clean-after protocol, only work if everybody follows the same protocol. Other protocols, such as the clean-before protocol, are more robust; they work fine—at least for you—even if some people follow the other protocol. If you can't guarantee that others will follow (or even remember!) a particular protocol, then you're better off choosing the robust protocol.

Here's a similar example. In college, I used to play a lot of bridge in the dorm lounge. In the hall right outside the lounge, there was a small bathroom. Now, there were two protocols concerning this bathroom. In the first protocol, you lock the door when using the bathroom; in the second protocol, you knock before entering. Somebody following the locked-door protocol may or may not knock, while somebody following the knocking protocol may or may not lock the door.

As long as everybody in the dorm follows the same protocol, there's no problem. But if different people follow different protocols, there can be tragic (or at least embarrassing) consequences!

In this example, perhaps the best course of action is to follow both protocols: lock the door and knock. The same is possible in many other situations where you want to be extra careful: clean the lint after drying but also check it again just before drying, initialize the counter just before the first action but also reset it to zero just after the last action, wear both a belt and suspenders.