"In 1979, Bill Gates and Christos Papadimitriou gave a lower bound of 1.06n flips and an upper bound of
(5n+5)/3. The upper bound was improved, thirty years later, to 18n/11 by a team of researchers at the University of Texas at Dallas, led by Founders Professor Hal Sudborough." --https://en.wikipedia.org/wiki/Pancake_sorting
Cheers. I've found the full paper is accessible through Sci-Hub [1]. I've had a very quick glance over it. The paper was submitted in January 1978 (when he'd already been at Microsoft for 2 years). But this NPR transcript [2] of a chat with Gates' Harvard professor Harry Lewis describes him as coming up with the solution a few days after the professor referenced the problem in class (in either 1974 or '75). Gates' co-author Christos Papadimitriou was an assistant professor at Harvard at the time. Papadimitriou went on to a glittering academic career and he recounts his recollection of the collaboration with Gates in a 2013 ACM profile [3].
So it appears that I do have to concede Gates this one contribution towards computer science. Although the paper contains a somewhat intriguing note right at the bottom :
> Ervin Györi of the Hungarian Academy of Sciences and György Turán of J. Atilla University have independently discovered a proof of Theorem 1 [the five-thirds solution]. Their algorithm and proof are essentially the same as ours.
And their paper [4] was published in 1978, preceding publication of the Gates & Papadimitriou paper in 1979.
The original paper seems to be https://www.sciencedirect.com/science/article/pii/0012365X79...
Rather interesting, I didn't know that about his history either.