History
Although seen more often as an educational device, pancake sorting also appears in applications in parallel processor networks, in which it can provide an effective routing algorithm between processors.
The problem is notable as the only well-known mathematics paper ever written by Microsoft founder Bill Gates (as William Gates), entitled "Bounds for Sorting by Prefix Reversal". Published in 1979, it describes an efficient algorithm for pancake sorting. In addition, the most notable paper published by Futurama co-creator David X. Cohen (as David S. Cohen) concerned the burnt pancake problem. Their collaborators were Christos Papadimitriou (then at Harvard, now at Berkeley) and Manuel Blum (then at Berkeley, now at Carnegie Mellon University), respectively.
The connected problems of signed sorting by reversals and sorting by reversals were also studied more recently. Whereas efficient exact algorithms have been found for the signed sorting by reversals see, the problem of sorting by reversals has been proven to be hard even to approximate to within certain constant factor, and also proven to be approximable in polynomial time to within the approximation factor 1.375 .
Read more about this topic: Pancake Sorting
Famous quotes containing the word history:
“The history of all hitherto existing society is the history of class struggles.”
—Karl Marx (1818–1883)
“The history of the Victorian Age will never be written: we know too much about it.”
—Lytton Strachey (1880–1932)
“It may be well to remember that the highest level of moral aspiration recorded in history was reached by a few ancient Jews—Micah, Isaiah, and the rest—who took no count whatever of what might not happen to them after death. It is not obvious to me why the same point should not by and by be reached by the Gentiles.”
—Thomas Henry Huxley (1825–95)