Susan and Adam last night were telling me a story about CMU's own Jay Kadane and Michael Shamos. It is told in Bentley's "Programming Pearls" — a pdf of the article is available here but don't read it yet if you don't want algorithm design spoilers!

The story centers around a particularly cute computational problem. Given a list of (maybe negative) integers x1 through xN, find a and b so that the sum of xi from i = a to b is maximized. In other words, find the biggest-sum contiguous sublist of the original list of numbers.

Back in the 70s Ulf Grenander came up with the obvious O(n3) algorithm, noticed it was slow, and improved it to O(n2). He asked Shamos about it, who improved it to O(n lg n) by thinking about it overnight. Shamos told the story up to that point to Kadane, who in "a minute" improved it to O(n).

Exercise to the reader: what were the four algorithms?

I was very pleased that I was able to reconstruct them eventually, strangely repeating the fact that it took sleeping on it to think of the O(n ln n) (although in hindsight I really should have got that quicker) and then the O(n) solution seemed easy after that. It was strange how trying really hard last night to think of the O(n) algorithm directly failed, and really just served as a distracting force. Working in a more generous "budget" of n lg n made me stop worrying about being heroically clever and let me think about the problem more calmly.
Tags:
• #### (no subject)

K got back tonight, pretty late in subjective time (3-4am or so, coming from europe) but all in one piece. None of her houseplants, which were…

• #### (no subject)

K is off tonight to Old Country for a couple weeks, to fulfill family-seeing obligations. Sad! Thankfully we still have internet and skype and…

• #### (no subject)

Finally home. This time instead of mysteriously attracting screaming babies I mysteriously attracted full grown adults biting their nails or maybe…

• Post a new comment

#### Error

Anonymous comments are disabled in this journal

default userpic