Gates於1973年進入Harvard大學學習，當時他18歲。在大學的第二年，
他選修了Papadimitriou博士的一門組合數學課程。

Papadimitriou當時還是一個剛剛得到博士學位的年輕教師，和學生一
樣厭惡考試。他在學期剛剛開始的時候，列出了一些與課程相關的問題，
讓同學們準備一個報告，以作為課程的考核。

在給出的問題中，有一個是關於利用前綴翻轉操作進行排序的問題。聰
明的Gates給出了這個問題的一個很好的結果。自然，Gates這門課得到了
最好的成績。而且，這個結果後來發表在離散數學最頂級的學術期刊上。

Gates, William H. and Christos H. Papadimitriou.
Bounds for sorting by prefix reversal.
Discrete Mathematics 27, 47--57, 1979

不完全統計，這篇文章至今被引用過19次，最近一次引用在1999年。而其
中對於這一結果的真正改進是由Heydari和Sudborough在1995年給出的，此時
Microsoft公司已經成立20年了。

1999年，Papadimitriou教授來到香港城市大學訪問。當時，姜濤教授也在
那裡訪問。期間，姜濤與Papadimitriou就Gates有以下的對話。

Jiang：“象Gates這樣有理論研究天才的學生去開公司，是不是很遺憾？”
Papa：“這個問題應該去問Gates，這是他個人的事情...”
沉默了一會兒，Papa接着說，“如果現在我有這樣的學生要去開公司，我一
定和他一起去。”

註：這個故事是今年夏天在浙江大學的時候，聽姜濤教授說的。回來以後，
我找到了Gates的那篇文章。如果有同學想研究一下，可以與我聯繫。:)

Papadimitriou教授曾在Harvard, MIT, Athens Polytechnic, Stanford，UC
San Diego等校任教，現在UC Berkeley計算機系。他在算法理論，計算複雜性理論
及其應用方面成果豐碩，是該領域的權威，享有很高的地位與聲譽。
(homepage: http://www.cs.berkeley.edu/~christos/)

姜濤教授1984年在中國科學技術大學獲得計算機科學技術學士學位，1988年於
Minnesota大學獲得計算機科學博士學位，現為UC Riverside計算機系教授。他在
自動機理論，計算生物學等方面做出了傑出的貢獻。
（homepage: http://www.cs.ucr.edu/~jiang/)

Gates同學這裡就不介紹了，呵呵。
(homepage: http://www.microsoft.com/billgates/)