Interesting Stuff

Warning: this post got embarrassingly long. For the short version, read up through the paragraph that starts with “If you use.”

This is something that’s been bugging me for a while, and I’d like to lay it to rest. If you’ve done any work in C++, you’ve probably heard the riddle about how to swap two integers without using a temporary variable. The question is exactly what it sounds like: you have two integers (call them x and y), you want to swap their values, and you may or may not want to use a third, temporary variable while doing it. Here are some ways of swapping integers that I have actually seen in professional code written by professional coders:

{  // Limit the scope of t
  int t = x;
  x = y;
  y = t;
}

x ^= y;
y ^= x;
x ^= y;

x ^= y ^= x ^= y;

x = x + y;
y = x - y;
x = x - y;

std::swap(x, y);

Try to come up with some answers before reading further.

When you’ve decided on your answers, let’s take a closer look. No, on second thought, this got really long. For those of you who don’t want to read all the way to the end, let me just get my main point out of the way. After that, we’ll take a closer look. If you don’t want to spoil the ending, skip the next paragraph.

If you use this link you will spoil the ending, so skip to the next paragraph after this one. →

This past weekend, Scott, Ronnie, Nick, Jerry, and I hung out. During part of the evening, the conversation turned to brazil nuts (don’t ask me how that happened; I have no clue). A discussion of brazil nuts and a search for the only brazil nut plantation in the world →

For those of you not already familiar with him, let me start off by introducing the visionary futurist Ray Kurzweil. He’s done some amazing things, but I don’t think his whole Singularity thing is right. →

…but this documentary is from the BBC, and seems to be backed up pretty well. The short version: the attack on Pearl Harbor was not a surprise at all, and FDR willingly let thousands of Americans die as an excuse to enter World War Two. Congress wouldn’t allow the US to go to war unless the country was attacked. Instead, they created an oil embargo against Japan. The Japanese needed to get oil from elsewhere, so they started to look at Indonesia and other islands in the pacific. They could easily have been defeated by the US fleet in Hawaii while doing this (I’m still a little hazy on this bit), so they first needed to get rid of the US forces there. The Japanese tried to go the diplomacy route to end the embargo, but when that failed, they sent their fleet to attack. Radio operators all over the Pacific (from California to New Zealand) all intercepted these signals, they all could decipher the code used, and they all knew about the attack several days before it was going to happen. This information was relayed to Washington, but people deliberately prevented it from getting to the commanders at Pearl Harbor itself. The attack happened, thousands of Americans died, but Roosevelt had his excuse to declare war on Japan, and the rest is history.

I found this fascinating, if a little unbelievable at first. In school, I had always been taught that the attack was an unprovoked surprise, but that never jived for me. If the Japanese hadn’t attacked, the Axis would probably have won WWII, and it seemed stupid of them to create more enemies in the war. This documentary at least partly explains things: the Japanese actually had a good reason to attack (they needed the ships out of the way before they could get resources from Indonesia), and the Allies had enough of a spy network that they could actually find out about obvious things like large fleets sailing across the Pacific. I still don’t fully understand why the Japanese couldn’t just get their oil from Indonesia and leave the Americans alone, but at least I have part of the picture now. This brings new meaning to the phrase “December 7, 1941—a date which will live in infamy.”

Whoa! It seems I was totally wrong when I expected the California Supreme Court to uphold the ban on gay marriage. Instead, they struck down the ban as unconstitutional, allowing same sex marriage in the state. Conservatives are already rallying to try to get a constitutional amendment banning it on the ballots in November, but it seems pretty unlikely that they’d be able to get the two thirds majority needed to pass it. Edit: it only takes a simple majority, which seems much easier. I don’t know if it is likely to pass. Hooray, progress!

Also, there is currently some finegaling in Congress these days over funding the Iraq invasion. It would be awesome if the legislators finally grew a spine and started passing bills that would, you know, stop wars of aggression and ban torture and provide education and medical benefits to veterans (admittedly, that last one is not related to Congress, but it’s despicable enough to mention along with the rest of this crap). but unfortunately I doubt this will actually go anywhere, and even if it did, Bush would almost certainly veto any such measure.

In natural disaster news, the cyclone that hit Burma and the earthquake in China have each left tens of thousands dead. Burma is in trouble because it is a poor country that doesn’t have the infrastructure to help the refugees or to rescue the people still trapped. China is in trouble because the areas worst hit are in hard-to-reach mountainous areas, and the earthquake coupled with heavy rains the next day wiped out most of the roads and airports, so it’s hard to send aid to the victims.

Hooray, getting my blog back onto the “Civil Liberties and World News” bit, rather than the “and computer science and stuff” part. I had begun to wonder if I needed to change the title of this blog.

Suppose you could create the specification for your ideal programming language. It must be possible to implement (it can’t solve undecidable problems, etc), but other than that the sky’s the limit. What would you put in it (what kind of syntax, intrinsics, etc)? For what sort of applications would it be used? What other features would it have? Would the interpreter/compiler do anything unusual? Tell me anything you want about your ideal language and the tools that go with it. You’re welcome to answer some of these questions if you don’t have answers to all of them.

I’ve been asking variations of this question to all sorts of people, and it’s fascinating seeing where they agree and where they don’t.

So, even before I get to the what the algorithm does (which is quite interesting on its own, even before you find out how it accomplishes that), the very first intriguing part is its name. It’s officially referred to as the Blum-Floyd-Pratt-Rivest-Tarjan Algorithm. Is your mouth watering yet? I thought so.¹ However, CLRS refers to it as the Select Algorithm (see section 9.3), so that’s what I’m going to call it. If you have an unsorted array of n items, it’s a worst-case O(n) algorithm for finding the i^th largest item (often the median, since that’s a commonly used statistic). Here’s how the algorithm works:

1. Put all the elements of the input into groups of 5 (with one group at the very end that could have less than 5 elements, of course). Find the median of each group.
2. Recursively use the Select algorithm to find the median of all the group-of-5 medians from step 1. Call this median of medians M.
3. Take all the items from the input and partition them into the group of items less than M and the group of items bigger than M.
4. If M is the i^th biggest, that’s the answer, and we’re done. If it’s not, you know which partition contains the i^th biggest item, and you can recursively call Select on that group (with a different i if the group it’s in is the group of items smaller than M).

To give an example of that last statement, suppose we’re looking for the 65th biggest number from a group of 100 numbers, and we find that M is the 53rd largest. There are 47 numbers smaller than M, and when we recurse, we’ll now be looking for the 12th largest element of that set of 47. If instead M had been the 68th largest number, in our recursive step we’d look at the 67 numbers larger than M and continue to look for the 65th largest one.

Now, I claimed the running time is linear, and I’d better back up that claim. The trick is to consider how many items get thrown out in that last step. Half the group-of-5 medians are larger than M, and half are smaller. Without loss of generality, suppose the i^th largest item is in the group that is larger than M. Now, not only do we know that we can henceforth ignore the half of the group-of-5 medians smaller than M, for each of those medians we can ignore the two items in the group of 5 that were smaller than that median. In other words, we can eliminate at least 3/10 of the elements we were searching over (we can eleminate 3/5 of the items in the groups whose median is smaller than M, and half of all the groups fit this category). Sure, I’m eliding an additive constant for the items in the group with M itself (not to mention the items in that last small group at the end when n is not a multiple of 5), but that’s not going to affect the asymptotic running time.

So now we can build the recurrence relation at work here. If T(n) is the amount of work done to perform Select on n items, we have

T(n) = O(n) + T(n/5) + T(7n/10)

That is to say, we do O(n) work in steps 1 and 3, we do T(n/5) work in step 2, and we do T(7n/10) work in step 4 because we know at least 3/10 of the elements are in the wrong partition. I’ll leave it as an exercise to the reader to draw out the recursion tree and find the actual amount of work done, but I assure you T(n) is in O(n).

The crazy part here is that magic number 5: If you do this with 3 items per group, the running time is O(n log n). If you do it with more than 5, the running time is still linear, but slower (you spend more time in step 1 finding all the initial medians). The optimal number of items per group really is 5. Nifty!

[1] For those of you not in the know, these are all really famous algorithms names. Blum is the co-inventor of the CAPTCHA. Floyd is from the Floyd-Warshall all-pairs shortest-paths algorithm, which is a staple in introductory algorithms courses. Pratt is from the Knuth-Morris-Pratt string matching algorithm, which was groundbreaking when it was new but is nearly obsolete now. Rivest is the R in RSA encryption, one of the most widely used encryption schemes around. Tarjan is the co-creator of splay trees, a kind of self-balancing tree with the handy property that commonly accessed items float to the top. Blum, Floyd, Rivest, and Tarjan have each won the Turing Award, which is like the Nobel Prize of computer science.

First off, Flash is vulnerable to by far the most awesome hack I’ve ever seen (there’s also a good summary of that paper). The attack has several different steps with integer overflows and failed memory allocations, but the heart of the matter is that the Flash player uses a 2-step process to validate that the code it’s running is probably safe, and this exploit changes the representation of the code in between the two checkers (it marks more of it as a no-op, so the second checker ignores the code with the exploit in it). This attack is awesome enough that it can carry out its task without disrupting the Flash player, so an unwary user will be none the wiser. and since there’s basically only one Flash player out there, every version of Flash is vulnerable. Yes, on Windows and even on Windows Vista despite their added security systems, as well as in principle on Linux and Mac. Yes, in both IE and Firefox (and presumably Safari also). This is yet another reason to install NoScript and FlashBlock on Firefox, so that sites cannot use Flash unless you give them permission. This is also another reason why standards should be open, so we can have more than one implementation of the Flash player, so not everyone will be vulnerable when something like this comes along.

The second hack I recently read about comes from Defcon celebrity Dan Kaminsky, who recently showed a very dangerous exploit that makes use of the way many ISPs these days turn DNS errors into pages of ads. This practice breaks the Same Origin Policy, so that your browser trusts these pages as though they came from the actual domain you typed in. To give an example, suppose I have an account with Bank of America and I go to ww.bankofamerica.com. Ordinarily, I’d get a DNS error. However, with certain ISPs these days, I would instead get a valid webpage saying the site doesn’t exist, but here are some ads instead. However, my browser asked for a website from bankofamerica.com and got back a website, so it trusts that it came from the bank. Consequently, it trusts the site with any cookies I have from BoA (these cookies are how BoA knows which account I’m logged into). If someone can put an XSS attack on the ISP’s ad injection system, they can grab my cookies and log into the bank as me. Yes, the bank can defend against things like this, but it’s an unusual enough hack that many companies aren’t defending against it. So beware, and if your ISP is doing this (for instance, if ww.bankofamerica.com returns a valid website), opt out of it! In addition to exposing users to this sort of attack, these ad injection systems often break DNS, which in turn breaks non-HTTP error handling (for instance, I could not VPN into work until I opted out of my ISP’s version of this crap).

I’ve found another interesting wrinkle in the ternary operator. So, here’s a bonus question for that quiz from last time. You start with the following code:

class Abstract;
class DerivedOne;  // Inherits from Abstract
class DerivedTwo;  // Inherits from Abstract
Abstract x;
DerivedOne one;
DerivedTwo two;
bool test;

Again, you can assume that all of these are defined/initialized (and you can assume the comments are correct—both Derived* classes inherit from Abstract). Now, consider these snippets:

if (test) x = one;
else x = two;

x = (test ? one : two);
 

Another unexpected answer →