March 2004 Archives
You will finally automate a task the last time you need to do it.
What do you call the little gray creature (that looks like an insect but is actually a crustacean) that rolls up into a ball when you touch it?
http://www.hcs.harvard.edu/~golder/dialect/staticmaps/q_74.html
Who the hell calls this a "basketball bug"?
These are the options I could strip from OpenSSL and still get it to build with RSA:
no-md2 no-md4 no-mdc2 no-ripemd no-rc2 no-rc5 no-idea no-cast no-des no-krb5 no-ec no-engine no-hw no-err
libeay32.dll is 572K.
ssleay32.dll is 128K.
Note that speed.c in the test suite wouldn't compile because DES was missing.
Bloom filters are cool. Start with a hash table, which is an efficient way to look up items in a set. A bloom filter is like a hash table, but it tells you only whether an item is in a set, and it sometimes incorrectly says yes (false positives), and the data structure is much smaller than a hash table.
This could be used to make a P2P filesharing client where searches could be performed offline. Peer A computes its Bloom filter signature, then broadcasts it to the world. Peer B collects Bloom filter signatures, then when it wants to search for an item, it iterates all the signatures, looking for a likely match, and broadcasts queries to one or more of the peers that come up positive.
Same idea but generalize it: a peer itself can be an item, so peers could exchange Bloom filters of connected peers to determine how to reach a particular peer without broadcasting queries to the whole world.
Adam next posed this problem:
The warden meets with the 23 prisoners when they arrive. He tells them:
You may meet together today and plan a strategy, but after today you will be in isolated cells and have no communication with one another.
There is in this prison a "switch room" which contains two light switches, labelled "A" and "B", each of which can be in the "on" or "off" position. I am not telling you their present positions. The switches are not connected to any appliance. After today, from time to time, whenever I feel so inclined, I will select one prisoner at random and escort him to the "switch room", and this prisoner will select one of the two switches and reverse its position (e.g. if it was "on", he will turn it "off"); the prisoner will then be led back to his cell. Nobody else will ever enter the "switch room".
Each prisoner will visit the switch room arbitrarily often. That is, for any N it is true that eventually each of you will visit the switch room at least N times.
At any time, any of you may declare to me: "We have all visited the switch room." If it is true (each of the 23 prisoners has visited the switch room at least once), then you will all be set free. If it is false (someone has not yet visited the switch room), you will all be executed.
Devise for the prisoners a strategy which will guarantee their release.
(My solution follows.)
I heard of the Monty Hall Problem years ago, and believed that Marilyn vos Savant was full of crap. Today my friend Adam Dingle explained to me why she wasn't. It took me a long time to understand, and even longer to believe. But here's my explanation.
You have a 1/3 chance of picking the right door. Therefore you have a 2/3 chance of picking the wrong one. If you've guessed wrong, the host eliminates all but the winning door. This is true because he's promised that after you choose, he'll narrow it down to two doors, one of which contains the winner.
Thus, you now have two choices: stay with your original choice, which you knew had a 1/3 chance of being right; or switch to the other door, which must be the winning door if you earlier picked wrong.
Marilyn's million-door example is excellent, but she chose a rhetorical rather than clear explanation for it.
You have a one-in-a-million chance of picking the right door on the first guess. Then the host eliminates all but your pick and another door, one of which is the winner. If you stay, then you believe that you picked the winner on the first guess. If you switch, then you believe that you picked wrong, and are now switching to the winning one. It's much more likely you guessed wrong, forcing the host to reveal the winning door (since he had to make sure that the remaining two doors contained the winner).
The devilish part of this problem is that there are three doors, not a million. This means that the host eliminates only one door of the remaining two, so you don't realize that he's actually eliminating every remaining door that's a loser.
Being too cheap to buy Purify, I finally had to figure out how to use the built-in leak detector in VS.Net. Turns out it's really easy.
Consider the following telephone dialogue:
(ring!)
(ring!)
Callee: "Hello?"
Caller: "Hello?"
What is wrong with this dialogue? Choose the right answer:
(a) Nothing.
(b) The caller is not supposed to say hello. That's the callee's job. The caller's job is to identify himself or herself, and state his or her reason for calling.
(c) None of the above.
(d) All of the above.
The right answer is (b).
Here is source code for Reed-Solomon encoding/decoding using the Berlekamp algorithm.
Yesterday Emily got her third tooth, the upper-left front tooth, and she's already discovered a new trick. She clicks and grinds them together in her crib at night, making a very eerie sound that for some reason is just like bones rubbing together.
It creeps out Mary and me. Emily, however, thinks it's very amusing.
