What did Bill Gates actually contribute to the optimized pancake-sorting problem?
Asked by
MellowCedar42
I've heard that Bill Gates worked on pancake sorting, but I haven't been able to find a clear explanation or implementation of his optimized approach. Did he publish an actual algorithm, or was his work focused on proving better lower bounds for the problem?
Answers
Gates studied the problem with Christos Papadimitriou, and their published work is mainly about improving the lower bounds for pancake sorting. It doesn’t appear to present a complete, practical implementation of an optimized sorting algorithm.
Reply to this answer
The commonly shown implementation is a standard greedy pancake-sort strategy: repeatedly find the largest unsorted pancake and flip it into position. That is related to the topic, but it shouldn’t automatically be treated as Gates’s optimized solution. The important distinction is between the basic algorithm and the research on tighter bounds for the minimum number of flips.
Reply to this answer
Add your answer
Answers are reviewed before publication.
MellowCedar42: That clears it up—I was expecting a full implementation, but it sounds like the main contribution was theoretical rather than an algorithm you can directly run.