Some interesting sorting algorithms

Walking back from Falafels today with CS majors, we somehow began discussing strange sorting algorithms.

A good sort to know (not really) is bead sort. Imagine you have a bunch of beads on rods, like an abacus, and cross-wise they represent numbers. If you simply tilt the whole thing over, then gravity will let them all fall and they’ll sort themselves. For example, we have the numbers 3, 2, 4, and 2 read horizontally. When they fall, we get 2, 2, 3, 4. Easy!

Another sort, “random sort,” “shuffle sort,” or the more common name “bogosort” was suggested as a good example of an O(∞) algorithm. But, as people have pointed out, if the quantum many-worlds theory holds, then you could sort in O(n) time: Use true quantum randomness to randomize the list and if the list is not sorted, then destroy the universe. The only universe that remains will have a sorted list.

Finally, Graham showed me the wonders of sleep sort. I’ll just leave the bash source code here:

seq="1 9 2 3 5 6 4 7"
for i in $seq; do
    (sleep $i;echo $i)&false;

git-dude, meet hg-dude

Git-dude is a cool little thing. Given a directory of git repos, it continually fetches updates and displays a popup if you get any new commits. When I first saw it on Google Plus, somebody inexplicably commented, “This is a neat thing and I dont [sic] think there is a mercurial equivalent.”

Given that Git and Mercurial are isometric for most intents and purposes, this baffled me. Clearly, this could not be some special Git-exclusive functionality. I dug into the git-dude source code and found out it was little more than a single bash script that pipes some git commands through sed and awk.

A few minutes later, I made hg-dude, which offers similar functionality for Mercurial. There’s a couple things that aren’t supported. Git-dude offered special notifications for tags and branches, and I didn’t translate them to Mercurial because the concepts, even though they have similar names, don’t quite match up. Regardless, it is still as useful as git-dude for commit notifications, which I expect is the primary usage.

Some may notice the irony of hosting a Mercurial tool on Github, but that was the easiest way to preserve its history from its git-dude days. Bitbucket fans can check out hg-dude’s Bitbucket repo.

Get hg-dude at Github or Bitbucket.

Why deterministic encryption algorithms do not satisfy multiple-message

Let’s say you have some private-key (symmetric-key) encryption scheme. It takes a key and a message, and outputs a ciphertext. Nobody without the key can decrypt the message using the decrypter. Is that secure? Not if it’s deterministic.

Continue reading Why deterministic encryption algorithms do not satisfy multiple-message

Steve Jobs: 1955–2011

It’s hard to put Steve Jobs into words, but I will forever remember him as a leader who didn’t let critics stop him from accomplishing so many things. We as a society tend to complain about Apple products being overhyped and to mock Apple’s “magical” and “revolutionary” labels, but the critics are uncomfortable because there’s truth under that glossy marketing.

Simply compare tablets before and after iPad, smartphones before and after iPhone, mp3 players before and after iPod, and even personal operating systems before and after OS X. Apple has been constantly setting the goalposts of the technology industry year after year, leaving its competitors struggling to keep up, and they have been and still are profiting enormously.

In the capitalist ideals of our society, isn’t that commendable? Millions of people were willing to pay the sometimes-high price for Apple products not because Steve Jobs really had a reality distortion field or that they were actually just gullible. Fool me once, shame on you, fool me twice, there’s something in the water? Millions of people returned to Apple time after time because Apple had a responsibility and consistently fulfilled it: make products that are ground-breaking yet polished in a way that leaves one wondering how life existed before.

Apple wasn’t interested in esoteric technologies to publish in research journals. When they found something good, they did what seemingly nobody else could: bring it to everybody. It was the ultimate intersection of technology and people. And Steve’s legacy isn’t limited to Apple: NeXT brought revolutionary computing ideals to fruition and without Steve, Pixar would have never went on to produce films like Toy Story and Finding Nemo.

Some companies settle into complacency and some pioneers settle into a dull CEO life. Bill Gates, Marc Andreesen, Larry Ellison… they are still around and active, but when was the last time they stunned us with innovation? Nobody else has come close to Steve Jobs in transforming technology over and over. Steve Jobs saved the best for last, and because we knew he would have continued wowing us year after year, it’s a shame that his time has come. Rest in peace.