idm

What I attended:

What I expected:

What I got:

I posed the problem of finding the execution time of increment sort without first figuring it out myself. What folly! Here goes:

Obviously the best-case is O(n) to check all elements of a pre-sorted list, and the worst-case is O(∞), as is common among randomized algorithms. But for the average case, not only does the running time depend on the sizes and spread of the elements in mysterious ways, but it turns out that merely determining the expected number of iterations is hopelessly complicated for all but the simplest of inputs (at least, using only high-school mathematics).

So let’s look at the simplest non-trivial input, the list [1,0]. With just two elements, we’re essentially flipping a coin to decide which element to increment, repeating until the second element catches up to the first. Since we only require that the number of tails is one more than the number of heads, coin-toss sequences are isomorphic to downward paths in Pascal’s triangle from \( \binom{1}{1} \) to \( \binom{2k+1}{k+1} \) [Edit: where k is the number of heads].

The total number of paths to \( \binom{2k+1}{k+1} \) in Pascal’s triangle is, of course, exactly this binomial coefficient. However, note that valid paths must stay on the left side of the triangle until the last minute, so we’re actually interested in paths to \( \binom{2k}{k} \) in a “modified” triangle that only counts left-side paths. It’s not too hard to convince yourself that these numbers are

$$ \binom{n}{r}’ = \binom{n}{r} \frac{n – 2r + 1}{n – r + 1} $$

which can be proved via induction, after verifying the base-case identities \( \binom{n}{0}’ = 1 \) and \( \binom{2n+1}{n+1}’ = 0 \).

Now, the probability of choosing any particular path to row \(2k+1\) is \( 2^{-(2k+1)} \), and so the expected number of iterations to sort [1,0] is

$$ \sum_{k=0}^\infty \frac{ 2k+1 }{ 2^{2k+1} (k+1) } \binom{2k}{k} $$

Stirling’s super-handy approximation gives

$$ \binom{2k}{k} \sim \frac{4^k}{\sqrt{\pi k}} $$

and simplifies the expected value sum to approximately

$$ \sum_{k=0}^\infty \frac{2k+1 }{ 2(k+1)\sqrt{\pi k} } $$

Hm. This most certainly does not converge. Which means increment sort is O(∞) on average!

Well then. The astounding ineffectiveness of this algorithm is just beginning to dawn on me.

Okay, back into the fray.

Bogosort is a pretty well-known example of the type of sorting algorithm you might concoct if you had a little too much time lying around — literally: O(n·n!) on average. Connoisseurs of efficiency-challenged sorts are familiar with DangerMouse’s bogobogosort, which performs much worse. Here’s my contribution to this nascent field:

Increment sort

1. If the list is sorted, you’re done.
2. Increment a random list element.
3. Go to step 1.

Of note is the “lossyness” of this algorithm. Whereas people often talk about whether a sort is stable or unstable, this takes that one step further by being a “mutable” sort: the resulting list is not guaranteed to contain the same elements as the original.

Unlike other lossy sorting algorithms, however, the number of elements is preserved. The benefits to sorting may not be immediately obvious, but consider the multitude of image filters that alter pixels while preserving the original dimensions. I expect that increment sort will open the doors to a new age of academic research in mutable sorting algorithms.

Now, what’s the execution time?

I’m sorry to say that Lulu, a dear and beloved friend, passed away today.

She was a beautiful calico with large yellow-green eyes and a luxurious coat in patches of black, white, and auburn. Her fur was, as more than one vet put it, as soft as a rabbit’s, and the hair itself so outgoing that many articles of clothing still feel her presence, and bring it to people who have not otherwise met her.

Her age remains a mystery to the end. Medical records from her earlier life in Rochester apparently date back 14 years, and might not even include contemporary mention of her having two litters of kittens.

Living 14 years is not normally miraculous for a domestic cat, but it is indeed for one who has lived with chronic renal failure through at least 7 of those years. Despite battling this condition for half of her life, she has managed to live well, and along the way she has made lots of friends.

By all accounts Lulu was a timid cat for many years, easily startled by noises, hiding from strangers, often cautious even of her own caretaker coming home with a thick winter coat on. When relaxed, however, she was remarkably sweet and affectionate, and loved giving people head-butts and body-rubs in return for chin-scratches and tummy-strokes. She wasn’t very good at keeping secret her fondness for being the center of attention.

Relocating to an apartment near Coolidge Corner last summer seemed to peel away a few layers of shyness. It might have been the chaos and commotion of moving, or perhaps her newfound spot by the window that offered a view of the busy street below, full of people and dogs and trucks. She picked up a habit of waiting at the door for people to return, and would even greet guests, becoming one of the household’s main attractions for visitors.

Though generally not a very active cat, she would eagerly scratch at the sofa, and chase mice, or more often mice-like objects, despite her lack of front claws. In the early morning and at night, she would find curious resting places atop sleeping people, usually on their chests or in nestled in the smalls of their backs. She sometimes groomed, but didn’t produce any hairballs. She loved catnip: once, to a fault.

A couple weeks ago, she started to refuse food, and by this time had been losing weight at a concerning rate. A visit to the vet revealed that her blood toxicity levels were severely elevated due to renal failure.

After five nights in the critical care unit, she regained an appetite and more normal blood toxicity levels. But the following week they rocketed back up, even amongst a cocktail of medications, and it became clear that no algorithm of drugs or treatments would be able to return her to a fair quality of life.

This week she had been meowing once every morning, but today we found her purring instead, for the first time in a while. Her daily subcutaneous fluids were administered, followed by some spoon-fed food. No oral medicine, which she greatly disliked.

For most of the day she laid on the bed, occasionally watching birds perched on the budding tree outside the window. Though visibly ailing, she didn’t evidence the immense pain that her blood levels would imply, and seemed calm and comfortable. I played her some Bach, and her favorite Godowsky. She did meow, as usual just once, upon waking from an afternoon nap basking in the sun. Despite being too weak to make a round-trip to the litter, she finished nearly a can and a half of her recent preference of “Marbella Paella,” and even groomed her paws and face. To the end she enjoyed having her chin scratched.

She was peaceful at a quarter before sundown, when the vet arrived. At 7:20 she drew her last breaths, relaxed, accompanied by warm friends to see her off. It is a lovely spring evening.

We will miss you dearly, Lulu.

In Memoriam, March 25, 2010.

Dreaming about being an expert troll on the Internets this morning tragically ended up with my imminently-awake self getting rickrolled. Tragically ironic.

Plotting my revenge… but how?

I have been told to blog about this.

waste:

1. v. to fail or neglect to use [negative].
2. n. left-overs; excess materials [positive].
3. n. anything not being used [neutral].

Triply conflated:

We waste [1] our waste [2] by dumping it in the waste [3].

True dream:

Through some unfathomable leap of imagination and confusion, a composer friend of mine has discovered a new avant-garde method of notating polyphonic music, in which haricots verts [the thinner, Frencher kind, of course] are arranged [you see?] on a cutting board, each representing a musical voice propagating through the two-dimensional domain of time versus pitch.

He calls me over to demonstrate his newest invention [again!], and — after a good deal of hand-waving and skepticism-banishing — manages to convince me of its validity.

He invites me to perform it.

I consider at length the lengthy greens.

Then, after producing a very large cleaver out of hammerspace [i.e. apparently nowhere], I begin chopping rapidly: vivacissimo.

“Stop, stop, stop, stop! You are doing it completely wrong! You have butchered my music!”

My /usr/share/dict wants to convince me that it knows the five longest words whose spellings are in anti-alphabetical order:

• wronged
• Tsoneca
• troolie
• sponged
• spiffed

Given that “troolie” is hardly a word, I’m not quite convinced.