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:
“Indeed, the Englishman’s history of New England commences only when it ceases to be New France.”
—Henry David Thoreau (1817–1862)
“There is no example in history of a revolutionary movement involving such gigantic masses being so bloodless.”
—Leon Trotsky (1879–1940)
“Every literary critic believes he will outwit history and have the last word.”
—Mason Cooley (b. 1927)