Pancake sorting
Encyclopedia
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
problem in which the only allowed operation is to reverse the elements of some prefix of the sequence. Unlike a traditional sorting algorithm, which attempts to sort with the fewest comparisons possible, the goal is to sort the sequence in as few reversals as possible. This operation can be visualized by thinking of a stack of pancake
Pancake
A pancake is a thin, flat, round cake prepared from a batter, and cooked on a hot griddle or frying pan. Most pancakes are quick breads; some use a yeast-raised or fermented batter. Most pancakes are cooked one side on a griddle and flipped partway through to cook the other side...
s in which one is allowed to take the top k pancakes and flip them. A variant of the problem is concerned with burnt pancakes, where each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on top.
The original pancake problem
The maximum number of flips required to sort any stack of n pancakes has been shown to lie between (15/14)n and (18/11)n, but the exact value is not known.The simplest pancake sorting algorithm requires at most 2n−3 flips. In this algorithm, a variation of selection sort
Selection sort
Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort...
, we bring the largest pancake not yet sorted to the top with one flip, and then take it down to its final position with one more, then repeat this for the remaining pancakes. Note that we do not count the time needed to find the largest pancake, only the number of flips; if we wished to create a real machine to execute this algorithm in linear time, it would have to both perform prefix reversal (flips) and be able to find the maximum of a range of consecutive numbers in constant time.
On September 17, 2008, a team of researchers at the University of Texas at Dallas
University of Texas at Dallas
The University of Texas at Dallas, also referred to as UT Dallas or UTD, is a public research university in the University of Texas System. The main campus is in the heart of the Richardson, Texas, Telecom Corridor, north of downtown Dallas...
led by Founders Professor Hal Sudborough announced the acceptance by the journal Theoretical Computer Science
Theoretical Computer Science (journal)
Theoretical Computer Science is a computer science journal published by Elsevier, started in 1975 and covering theoretical computer science. The journal publishes 52 issues a year. It is abstracted and indexed by Scopus and the Science Citation Index...
of a more efficient algorithm for pancake sorting than the one proposed by Gates and Papadimitriou. This establishes a new upper bound of (18/11)n, improving upon the existing bound of (5/3)n from 1979.
On November 2, 2011, a paper was submitted to the arXiv announcing a proof that the problem is NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
, thereby answering a question open for over three decades.
The burnt pancake problem
In a more difficult variation called the burnt pancake problem, the bottom of each pancake in the pile is burnt, and the sort must be completed with the burnt side of every pancake down. In 2008, a group of undergraduates built a bacterial computerDNA computing
DNA computing is a form of computing which uses DNA, biochemistry and molecular biology, instead of the traditional silicon-based computer technologies. DNA computing, or, more generally, biomolecular computing, is a fast developing interdisciplinary area...
that can solve a simple example of the burnt pancake problem by programming E. coli
Escherichia coli
Escherichia coli is a Gram-negative, rod-shaped bacterium that is commonly found in the lower intestine of warm-blooded organisms . Most E. coli strains are harmless, but some serotypes can cause serious food poisoning in humans, and are occasionally responsible for product recalls...
to flip segments of DNA which are analogous to burnt pancakes.[DNA has an orientation (5' and 3') and an order (promoter before coding). Even though the processing power expressed by DNA flips is low, the high number of bacteria in a culture provides a large parallel computing platform. The bacteria report when they have solved the problem by becoming antibiotic resistant. An animation depicting this process has been produced.
The pancake problem on strings
The above discussion presumes that each pancake is unique, i.e. no two of them are identical. Hence the sequence on which the prefix reversals are performed is a "permutation", i.e. the sequence in which every symbol occurs exactly once. However, "strings" are sequences in which a symbol can repeat. The complexity of sorting a permutation with prefix reversals is unknown. However, Heydari showed that a related problem is NP-complete. Chitturi and Sudborough (2010) and Hurkens et al. (2007) independently showed that the complexity of transforming a compatible string into another with prefix reversals is NP-completeNP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
. Chitturi (2011) proved that the complexity of transforming a compatible signed string into another with prefix reversals, i.e. the burnt pancake problem on strings, is NP-complete.
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
Microsoft
Microsoft Corporation is an American public multinational corporation headquartered in Redmond, Washington, USA that develops, manufactures, licenses, and supports a wide range of products and services predominantly related to computing through its various product divisions...
founder Bill Gates
Bill Gates
William Henry "Bill" Gates III is an American business magnate, investor, philanthropist, and author. Gates is the former CEO and current chairman of Microsoft, the software company he founded with Paul Allen...
(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
Futurama
Futurama is an American animated science fiction sitcom created by Matt Groening and developed by Groening and David X. Cohen for the Fox Broadcasting Company. The series follows the adventures of a late 20th-century New York City pizza delivery boy, Philip J...
co-creator David X. Cohen
David X. Cohen
David Samuel Cohen , primarily known as David X. Cohen, is an American television writer. He has written for The Simpsons and he is the head writer and executive producer of Futurama.-Early life:...
(as David S. Cohen) concerned the burnt pancake problem. Their collaborators were Christos Papadimitriou
Christos Papadimitriou
Christos Harilaos Papadimitriou is a Professor in the Computer Science Division at the University of California, Berkeley, United States...
(then at Harvard
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
, now at Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
) and Manuel Blum
Manuel Blum
Manuel Blum is a computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography and program checking".-Biography:Blum attended MIT, where he received his bachelor's degree and...
(then at Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...
, now at Carnegie Mellon University
Carnegie Mellon University
Carnegie Mellon University is a private research university in Pittsburgh, Pennsylvania, United States....
), 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 [Kaplan, Shamir, Tarjan
Robert Tarjan
Robert Endre Tarjan is a renowned American computer scientist. He is the discoverer of several important graph algorithms, including Tarjan's off-line least common ancestors algorithm, and co-inventor of both splay trees and Fibonacci heaps. Tarjan is currently the James S...
, 1997], the problem of sorting by reversals has been proven to be hard even to approximate to within certain constant factor [Berman, Karpinski
Marek Karpinski
Marek Karpinski is a computer scientist and mathematician known for his research in the theory of algorithms and their applications, combinatorial optimization, computational complexity, and mathematical foundations...
, 1999], and also proven to be approximable in polynomial time to within the approximation factor 1.375 [Berman, Karpinski
Marek Karpinski
Marek Karpinski is a computer scientist and mathematician known for his research in the theory of algorithms and their applications, combinatorial optimization, computational complexity, and mathematical foundations...
, Hannenhalli, 2002].
Related integer sequences
| Height | | N | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |
| 1 | 1 | ||||||||||||||
| 2 | 1 | 1 | |||||||||||||
| 3 | 1 | 2 | 2 | 1 | |||||||||||
| 4 | 1 | 3 | 6 | 11 | 3 | ||||||||||
| 5 | 1 | 4 | 12 | 35 | 48 | 20 | |||||||||
| 6 | 1 | 5 | 20 | 79 | 199 | 281 | 133 | 2 | |||||||
| 7 | 1 | 6 | 30 | 149 | 543 | 1357 | 1903 | 1016 | 35 | ||||||
| 8 | 1 | 7 | 42 | 251 | 1191 | 4281 | 10561 | 15011 | 8520 | 455 | |||||
| 9 | 1 | 8 | 56 | 391 | 2278 | 10666 | 38015 | 93585 | 132697 | 79379 | 5804 | ||||
| 10 | 1 | 9 | 72 | 575 | 3963 | 22825 | 106461 | 377863 | 919365 | 1309756 | 814678 | 73232 | |||
| 11 | 1 | 10 | 90 | 809 | 6429 | 43891 | 252737 | 1174766 | 4126515 | 9981073 | 14250471 | 9123648 | 956354 | 6 | |
| 12 | 1 | 11 | 110 | 1099 | 9883 | 77937 | 533397 | 3064788 | 14141929 | 49337252 | 118420043 | 169332213 | 111050066 | 13032704 | 167 |
Sequences from The Online Encyclopedia of Integer Sequences
On-Line Encyclopedia of Integer Sequences
The On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs...
of Neil Sloane
Neil Sloane
Neil James Alexander Sloane is a British-U.S. mathematician. His major contributions are in the fields of combinatorics, error-correcting codes, and sphere packing...
: – maximum number of flips – number of stacks requiring the maximum number of flips (above) – maximum number of flips for a "burnt" stack – the number of flips for a sorted "burnt-side-on-top" stack – the above triangle, read by rows
Further reading
- Mohammad, H.H. and Hal Sudborough, I. "On the Diameter of the Pancake Network," Journal of Algorithms 25 (1), 67-94, 1997.
- Roney-Dougal, C. and Vatter, V. "Of pancakes, mice and men," Plus Magazine 54, March 2010.
External links
- Cut-the-Knot: Flipping pancakes puzzle, including a Java applet for the pancake problem and some discussion.
- Douglas B. West's "The Pancake Problems"
- Pancake sorting - from Mathworld
- Animation explaining the bacterial computer that can solve the burnt pancake problem.