Interesting Stuff

In today’s installment of “why not to program in C++,” I give you the following quiz, which Dustin, Steve, Tom, and I had to figure out today (Dustin’s code was doing the weirdest things, and we eventually traced it down to this):

Suppose you start out with the following code:

class Argument;
Argument x;
void Foo(const Argument& arg);
bool test;

You can assume that all of these are defined/initialized elsewhere in the code. For each pair of code snippets below, decide whether the two snippets are equivalent to each other.

if (test) Foo(x);
else Foo(Argument());

Foo(test ? x : Argument());
 

{ // limit the scope of y
  Argument y;
  Foo(test ? x : y);
}

Foo(test ? x : Argument());
 
 
 

Foo(x);

Foo(test ? x : x);

Foo(x);

Foo(true ? x : Argument());

The answers are worse than you'd think. →

Merry Easter, all! Zombie Jesus may not be real, but we can honour him anyway by watching videos of Zombie Dog Head, which is real. Though I should first post a WARNING: THESE VIDEOS ARE VERY GRAPHIC. The first one shows organs and body parts that have been dismembered. The second shows a dog getting killed (and then brought back to life; there is a happy ending!). Seeing early prototypes of the life support systems that hospitals use is fascinating!

Admittedly, I can’t think of an uncontrived use case when I would prefer this to a hash table, union find, or traditional bit field, but I still think this is a pretty cool concept. It’s a data structure to hold n items, with constant time initialization (i.e. you can’t initialize all n items at the beginning), and constant time random access. Moreover, it can be used as a set: on top of the constant time random access, you can store and remove items as well as get the number of items in it in constant time, and you can iterate through all the inserted items in O(n) time (where n is the number of items currently stored in the set; not the maximum number of items it can have). and on top of that, if you don’t need to call the items’ destructor (for instance, you’re storing doubles or ints), you can empty the set in constant time! The only drawback to using it as a set is that it takes memory proportional to the size of the keyspace (for instance, if you’re trying to store items indexed by b-bit numbers, it will take O(2^b) space). However, it can be used as a bit vector: to store u bits, it takes a mere O(u) space, and you don’t need to zero all the bits out at the beginning! This implies that if you only end up using a sparse subset of the bits, you don’t have to waste time initializing all the bits you didn’t use. To be fair, the constant hidden behind that O(u) space is bigger than the one in a normal bit vector, but I think it’s still a pretty neat idea. Besides, space is cheap these days; people already often use a byte or four for every bit needed.

Anywho, here’s a great write-up of it, along with the original 1993 paper that introduces it (see the top of page 4 to compare the running times of this to a traditional bit field). On top of what is written in those links, the space required can be cut in half by only having a single array instead of two: just have it point to other parts of itself. Insertion/deletion gets a little more complicated, but it totally works. Neat!

Man, would I like to know how that works. Its balancing algorithm is incredible!

Today the California Supreme Court began considering the constitutionality of gay marriage. The overwhelmingly Republican court is expected to deny the pleas of dozens of plaintiffs hoping the state will sanction their marriages. A decision is expected in about 3 months, so this shouldn’t drag on forever and with any luck I’ll remember to follow up on it when the results are in. In the meantime, I can hope against hope that the court will extend the same rights and liberties to everyone.

I need to stop editing this and post it before it becomes out of date again.

Finally, after seven years, it appears that some of the democrats may have grown a spine. Congress has been fighting over surveillance bills concerning wiretapping and the Foreign Intelligence Surveillance court. Although everyone in Congress unfortunately seems to think that warrantless wiretaps are a good idea, the main battle is currently over whether the telephone companies should be granted retroactive immunity for allowing such warrantless wiretaps back when it was illegal according to Federal law. You may recall that the Protect America Act of 2007 allowed the government to wiretap phones without court oversight, but it was set to expire in February 2008. Congress recently spent a lot of effort trying to renew it, but the retroactive immunity has become a sticking point. Bush and his cronies say that without it, the telecoms will be afraid to help the government with this stuff in the future (never mind the fact that if they just got the FISA court to review it, it’s very easy to get a warrant and then the telecoms are happy to comply). Consequently, the Senate passed a version of the bill that granted retroactive immunity to the telecoms (note that Obama voted against the immunity, while McCain voted for it and Clinton didn’t bother to show up; all three have claimed they were against such things when asked about it in the past). The House of Representatives, however, passed a copy of the bill that did not grant immunity. The two bills went to reconciliation (where they’re merged into one law that goes back to both groups again), and the version decided upon included the immunity. However, again the House did not pass the bill. In response, Republicans staged a walk-out in protest. Consequently, no bill was sent to Bush to be signed, and the PAA expired! We’re back to the (mostly sane) wiretapping rules described under the Foreign Intelligence Surveillance Act of 1978. I earnestly, desperately hope that the Democrats continue to hold strong, and I have written to my Representative to say this (he wrote back with a canned response about how he intends to fight this, but that doesn’t actually mean he’ll carry through). We’ll see.

In the meantime, bastions of freedom and privacy such as the Electronic Frontier Foundation continue to fight against the telephone companies that violated Federal law and our privacy. Sadly, the Supreme Court threw out the ACLU’s case with absolutely no comment about why they did that (a lower court had ruled that they can’t prove they were the victem of the warrantless wiretaps, because the evidence that shows they were was deemed to be a state secret and consequently thrown out of the case). However, I believe the EFF cases are still going through the legal process. This is a tough thing for the Supreme Court to tackle: if they rule in favor of the wiretaps, they significantly weaken the fourth amendment (see Berger v. New York, 1967). However, if the court makes warrantless wiretapping illegal, all hell breaks loose because the Bush administration has been conducting an unconstitutional program for years (and all hell breaking loose is not conducive to orderly government).

We’ll see what happens. If the past few years are any prediction, the Democrats are just going to roll over and grant the retroactive immunity, but I really, really hope this won’t transpire.

I recently received the following email, sent to a non-work-related account I have. Except for removing this person’s name and city, I have not changed the text or formatting (size, boldness, line breaks) at all.
A cover letter looking for an internship →

Hells yeah! The Internet Corporation for Assigned Names and Numbers, the group in charge of domain registrars (who are in charge of keeping track of who owns what domain names) changed some boring policies, and my personal work indirectly affected the entire Internet. →

I got this one from Alasdair months ago, and it’s a doozy. However, it’s really only intended for the mathematically minded, so feel free to skip if you’re not comfortable with introductory probability. It’s a multi-part question, but the first parts are intended to be easy, so don’t second-guess yourself too much on those.

1. A guy is repeatedly rolling an unbiased six-sided die in a room when you enter the room and start watching him. How many rolls do you expect to watch before he rolls a 1?
2. On further inspection, you notice that he has written down his previous rolls in a list. How far back in the list do you expect to have to look before seeing the previous 1? You can assume that the guy has been doing this for long enough that he rolled a 1 at some point in the past.
3. Define a “drought of 1’s” as the die rolls between successive 1’s (including the bounding 1’s). For instance, the rolls 1-4-2-1-5-1 would constitute a drought of length 4 followed by a drought of length 3. What is the expected length of a drought of 1’s?

The typical answers to the above questions are six, six, and seven (since we’re including both the starting 1 and the ending 1). However, this implies that on average droughts will have length seven, but when you walk into the room the average drought will have length twelve: you’d expect to be six rolls into the drought already, and you’d expect six more once you start watching. What’s going on here? How should this discrepancy be resolved?