Comment Re:You're watching Futurama... (Score 2, Informative) 386
"David X. Cohen: Graduated magna cum laude with a bachelor's degree in physics from Harvard University in 1988. He received his master's degree in computer science from UC Berkeley in 1992. He published the following article with Manuel Blum: On the Problem of Sorting Burnt Pancakes. Discrete Appl. Math. 61 (1995), no. 2, 105--120."
Here is the abstract:
The "pancake problem" is a well-known open combinatorial problem that recently has been shown to have applications to parallel processing. Given a stack of n pancakes in arbitrary order, all of different sizes, the goal is to sort them into the size-ordered configuration having the largest pancake on the bottom and the smallest on top. The allowed sorting operation is a "spatula flip", in which a spatula is inserted beneath any pancake, and all pancakes above the spatula are lifted and replaced in reverse order. The problem is to bound f(n), the minimum number of flips required in the worst case to sort a stack of n pancakes. Equivalently, we seek bounds on the number of prefix reversals necessary to sort a list of n elements. Bounds of 17n/16 and (5n + 5)/3 were shown by Gates and Papadimitriou in 1979. In this paper, we consider a traditional variation of the problem in which the pancakes are two sided (one side is "burnt"), and must be sorted to the size-ordered configuration in which every pancake has its burnt side down. Let g(n) be the number of flips required to sort n "burnt pancakes". We find that 3n/2 less-than-or-equals, slant g(n) less-than-or-equals, slant 2n 2, where the upper bound holds for n gt-or-equal, slanted 10. We consider the conjecture that the most difficult case for sorting n burnt pancakes is In, the configuration having the pancakes in proper size order, but in which each individual pancake is upside down. We present an algorithm for sorting In in 23n/14 + c flips, where c is a small constant, thereby establishing a bound of g(n) less-than-or-equals, slant 23n/14 + c under the conjecture. Furthermore, the longstanding upper bound of f(n) is also improved to 23n/14 + c under the conjecture.
Here is the abstract:
The "pancake problem" is a well-known open combinatorial problem that recently has been shown to have applications to parallel processing. Given a stack of n pancakes in arbitrary order, all of different sizes, the goal is to sort them into the size-ordered configuration having the largest pancake on the bottom and the smallest on top. The allowed sorting operation is a "spatula flip", in which a spatula is inserted beneath any pancake, and all pancakes above the spatula are lifted and replaced in reverse order. The problem is to bound f(n), the minimum number of flips required in the worst case to sort a stack of n pancakes. Equivalently, we seek bounds on the number of prefix reversals necessary to sort a list of n elements. Bounds of 17n/16 and (5n + 5)/3 were shown by Gates and Papadimitriou in 1979. In this paper, we consider a traditional variation of the problem in which the pancakes are two sided (one side is "burnt"), and must be sorted to the size-ordered configuration in which every pancake has its burnt side down. Let g(n) be the number of flips required to sort n "burnt pancakes". We find that 3n/2 less-than-or-equals, slant g(n) less-than-or-equals, slant 2n 2, where the upper bound holds for n gt-or-equal, slanted 10. We consider the conjecture that the most difficult case for sorting n burnt pancakes is In, the configuration having the pancakes in proper size order, but in which each individual pancake is upside down. We present an algorithm for sorting In in 23n/14 + c flips, where c is a small constant, thereby establishing a bound of g(n) less-than-or-equals, slant 23n/14 + c under the conjecture. Furthermore, the longstanding upper bound of f(n) is also improved to 23n/14 + c under the conjecture.
