Christos Papadimitriou was asked about this paper in a recent interview[0] - his response is below:
------------------------------------
When I was an assistant professor at Harvard, Bill was a junior. My girlfriend back then said that I had told her: "There's this undergrad at school who is the smartest person I've ever met."
That semester, Gates was fascinated with a math problem called pancake sorting: How can you sort a list of numbers, say 3-4-2-1-5, by flipping prefixes of the list? You can flip the first two numbers to get 4-3-2-1-5, and the first four to finish it off: 1-2-3-4-5. Just two flips. But for a list of n numbers, nobody knew how to do it with fewer than 2n flips. Bill came to me with an idea for doing it with only 1.67n flips. We proved his algorithm correct, and we proved a lower bound—it cannot be done faster than 1.06n flips. We held the record in pancake sorting for decades. It was a silly problem back then, but it became important, because human chromosomes mutate this way.
Two years later, I called to tell him our paper had been accepted to a fine math journal. He sounded eminently disinterested. He had moved to Albuquerque, New Mexico to run a small company writing code for microprocessors, of all things. I remember thinking: "Such a brilliant kid. What a waste."
Something to think about when giving interviews, writing articles, and creating marketing material:
> My girlfriend back then said that I had told her: "There's this undergrad at school who is the smartest person I've ever met."
That sounds more impressive and more sincere than simply saying, "He's the smartest person I've ever met."
In both cases, it's the same person saying it, and in neither case can you verify that he really believes it, yet one statement is much more credible and quotable.
The previous formatting got me so confused, I thought `>` was a prefix swap operator ...
Anyways, I'd never have thought Gates was so mathematically inclined before starting Microsoft. Many times, articles about him in college were more about how he peeked on others code found in the trash. It's a tiny bit of a waste, but if he had kept doing proofs he would never have been the "historical" figure that he is now.
Trivia: this was the most efficient known algorithm until 2008 [1].
> On September 17, 2008, a team of researchers at the University of Texas at Dallas led by Founders Professor Hal Sudborough announced the acceptance by the journal Theoretical Computer Science of a more efficient algorithm for pancake sorting than the one proposed by Bill Gates and Christos Papadimitriou. This establishes a new upper bound ... improving upon the existing bound ... from 1979.
So, what would I do if I was as smart, rich, and old as billg? I'd invest in things that exponentially accelerate the rate of collective Human scientific and technological progress. Then, I'd sit back, relax, and wait for a cure for old-age to appear...
I appreciated how easy it was to read, at least until it got to the formal proof. This might be a good interview question to pose - to ask the interviewee to come up with the trivial lower and upper bounds of "pancake flips".
------------------------------------
When I was an assistant professor at Harvard, Bill was a junior. My girlfriend back then said that I had told her: "There's this undergrad at school who is the smartest person I've ever met."
That semester, Gates was fascinated with a math problem called pancake sorting: How can you sort a list of numbers, say 3-4-2-1-5, by flipping prefixes of the list? You can flip the first two numbers to get 4-3-2-1-5, and the first four to finish it off: 1-2-3-4-5. Just two flips. But for a list of n numbers, nobody knew how to do it with fewer than 2n flips. Bill came to me with an idea for doing it with only 1.67n flips. We proved his algorithm correct, and we proved a lower bound—it cannot be done faster than 1.06n flips. We held the record in pancake sorting for decades. It was a silly problem back then, but it became important, because human chromosomes mutate this way.
Two years later, I called to tell him our paper had been accepted to a fine math journal. He sounded eminently disinterested. He had moved to Albuquerque, New Mexico to run a small company writing code for microprocessors, of all things. I remember thinking: "Such a brilliant kid. What a waste."
[0] - http://awards.acm.org/info/papadimitriou_4558987.cfm