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:

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

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.

(more…)

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.

Cumulative Binomial Distribution

In my defense, I was trying to give an exact number.

iOS keycodes in Javascript

Here are the iOS keycodes for the keyDown and keyPress events in JavaScript as generated by an iPad running iOS 4.3.3:

(more…)

WordPress permissions on NearlyFreeSpeech.net

“To perform the requested action, connection information is required.”

My earlier post on WordPress with NearlyFreeSpeech.net was too hastily written. There are more issues than WP not wanting to use the direct upgrader, and editing WordPress code is not the right way to solve it either.

Problem 1: WordPress doesn’t want to use the direct upgrader. You can force it to use the direct upgrader by adding define('FS_METHOD', 'direct'); to /wp-config.php.

Problem 2: WordPress may not have write access to certain directories. The wp-content directory, for example, would need to be chgrp to web and chmod to 775 in order for WordPress to update the things within. Of course, there is the option of just doing that on all of your WordPress files.

Problem 3: WordPress will create files that you cannot edit. Files created by PHP will be owned by user ‘web’ and the permissions will be 644. That means you (“me”) cannot edit these files over SSH since you are not the owner. You can’t even delete, chown, or chmod the files. You’ll either have to get PHP to delete them or ask NFSN support to chown them for you. A workaround is to umask(002); to your wp-config.php, which makes files created by PHP group-writable. They will still be owned by web by default, but at least you can do something about it.

Problem 4: The default temp directory may not be accessible by PHP. NFSN’s FAQ for installing WordPress has instructions about this and a variant is given here. First, make a directory called ‘tmp’ in your WordPress root and give PHP permissions to write to it (chgrp to web and chmod to 775). Then, add define('WP_TEMP_DIR', dirname(__FILE__).'/tmp'); to your wp-config.php file.

Life-saving ability of major mobile devices

We’ve all known that Apple iDevices are superior to their competitors, but until now, we haven’t looked into a critical factor—their ability to save your life.

To compile the following charts, a Google search was conducted for “X saved my life” where X is a value from the left side of the chart. The number of results are reported by Google was then recorded as the data point.

“_____ saved my life”

(more…)

Configuring your phone for T-Mobile data

If your cellphone didn’t come preconfigured for T-Mobile (e.g. iPhone), you may need these APN settings to access the Internet:

APN: internet2.voicestream.com
Leave the username and password blank.

New web host

If you’re reading this, then the DNS changes have successfully propagated and you’re loading this page from my new hosting provider, NearlyFreeSpeech.net. I’m dropping Site5 like a bad habit, and will soon be free of uncool mainstream shared hosting relatively soon. Although Site5’s control panel software went through a major revision recently, it was still clunky and awkward, especially for MySQL and hosting multiple sites on one plan.