Wacken

I’ll be up early tomorrow, Saturday, to take the train with lots of friends to the little town of Wacken in Germany. (Actually, there is no train station in Wacken, so we need to hire a cab someway for the last dozen kilometers)

Sunday morning the camping of the Wacken Open Air festival will open. The festival itself will start on Thursday. I hope to be home again the first Sunday of August.

linux 2.6.22-bw-r1

There isn’t a tree that contains reiser4, suspend2 and the gentoo patches — so I created one. This revision adds the -stable patches and the new gentoo patches.

One big patch: bw-r1-for-2.6.22.diff.bz2
Patches broken out: bw-r1-for-2.6.22.tar.bz2

To apply the one big patch, use: bzcat bw-r1-for-2.6.22.diff.bz2 | patch -p1 inside a vanilla 2.6.22.

“Nothing to hide”

In this short essay, written for a symposium in the San Diego Law Review, Professor Daniel Solove examines the “nothing to hide” argument. When asked about government surveillance and data mining, many people respond by declaring: “I’ve got nothing to hide.” According to the “nothing to hide” argument, there is no threat to privacy unless the government uncovers unlawful activity, in which case a person has no legitimate justification to claim that it remain private. The “nothing to hide” argument and its variants are quite prevalent, and thus are worth addressing. In this essay, Solove critiques the “nothing to hide” argument and exposes its faulty underpinnings.

“I’ve Got Nothing to Hide” and Other Misunderstandings of Privacy

Not only is its subject very relevant, the Essay is very well written and a pleasure to read.

Online Cycle Detection in Directed Graphs

A short while ago I came across a quite interesting problem. Design a datastructure (and algorithms) to maintain a Directed Acyclic Graph.

There has to be only one operation: adding a link between two given nodes. This operation must be able to detect and deny any new link that would cause a cycle. For simplicity, nodes are identified by sequential ids starting with 0.

An example:

addLink 0, 1 -> True
addLink 1, 2 -> True
addLink 2, 0 -> False # Fails because it would create a cycle

addLink 0, 1 -> True
addLink 1, 2 -> True
addLink 0, 2 -> True # This isn't a real cycle, so it's perfectly fine

It’s rather trivial to create a [tex]\mathcal{O}\left(n+\ell\right)[/tex] (where [tex]n[/tex] is the number of nodes and [tex]\ell[/tex] the number of links). I conjecture there exists a [tex]\mathcal{O}\left(\log n\right)[/tex] algorithm.