Jason (jcreed) wrote,

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: algorithms
  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded