Sorting pancakes with Bill Gates

I've seen this meme all over the internet. We know how comforting when life is simply not working out.  It tends to the notion that you can struggle as a student and still be useful to the world. Only problem the reality is the complete opposite. Bill Gates, was far from a sloppy student, he was the type of engaged student, who read and thought a lot. Infact as an undergrad student, he published an academic paper that for 30 years remained the state of the art solution to a very fundamental problem. Although the title 'Bounds for sorting by Prefix reversal'[1] sounds boring and academic, its about pancakes, so grab some pancakes, lets talk about pancakes.

What exactly is the problem with pancakes? None, such a sweet and comforting food source is far from a nuance. The problem is with the chef who like me, likes to throw things around, with little attention to aesthetics. Pancakes come in different sizes and most people agree they look better when sorted with the biggest at the bottom. Given an arbitrary order produced by our chief, produce pleasant looking stack with the minimum number of flips. As easy it sounds, it is still an open Computer Science problem, since the only move allowed is reversing a sequence of pancakes from the top.

When Prof Harry Lewis casually posed this question to his undergrad class, 40 years ago, he wasn't expecting any breakthrough. That was until one William Gates brought him a solution 2 days later. Previously, it was known that the solution is at most 2(n-1) because the lazy approach is start by flipping the biggest to the bottom ( at most 2 moves) and iteratively do so, for the next biggest until everything is sorted. Like all brute force algorithms, it  works but doesn't scale, imagine a very hungry customer orders 1000 pancakes. He'll definitely starve. Good guy Bill proposed  an algorithm with an upper bound that is substantially better.

Pancakes are represented as a permutation of numbers reflecting their sizes. If the two neighbors in the permutation differ by 1, the pair is called an adjacency. A block is a series of consecutive adjacencies and an element that is not a block is a free element. The perfectly sorted permutation 123...n has n-1 adjacencies and one block, others have fewer adjacencies and more blocks.  The algorithm Bill proposed increases adjacencies by designing minimum flips for all possible configurations of the first element of the permutation with respect to its neighbors.For each configuration different kinds of flips are performed increasing the number of adjacencies by at least one and changing the number of blocks differently. The result is a linear programming problem with the objective of maximizing the number of flips while constrained by the number of adjacencies and blocks. Using the duality theorem of Von Neuman, Kuhn, Tucker and Gale, the upper bound on the number of flips is established to be of the order five thirds (actually (5n-5)/3)of the number of elements in the permutation. As if a 1.2 times speedup is not enough, the paper goes on to establish the lower bound as well as the bounds for the restricted case where pancakes not only have to be sorted but also sorted the right side up.

Sorting pancakes may not sound like a ground breaking problem but it is the same problem encountered when establishing gene similarities between species. For 30 years, Gates' algorithm remained state of the art until folks at University of Texas, produced a marginal improvement [2], utilizing automation made possible by the same Bill Gates.

I have always known that it takes a lot more than quitting Harvard to revolutionize the tech industry, or at the very least launch a successful startup. Now I know that uncertainity fused with bountiful curiosity  is a major ingredient of the recipe. Bill Gates didn't foresee anything, he simply solved a problem that interested him, building his confidence to solve bigger problems. If you are confused on your purpose in life, hang in there, savor the feeling, its building up to something. In the meantime, get even more inspired with Gates Notes and have a great weekend ahead.

References:
[1] Bounds for sorting by Prefix reversal  by Gates,W and H, Papadimitriou
[2] An 18n/11 upper bound for sorting by prefix reversals by B. Chitturi, W. Fahle, Z. Meng, L. Morales, C.O. Shields, I.H. Sudborough , W. Voit