Help
Add this page to your book
Show book (0 pages)
Suggest pagesPancake sorting
Pancake sorting is a variation of the sorting 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 pancakes 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.
Contents |
[edit] The pancake problems
[edit] 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.[1]
The simplest pancake sorting algorithm requires at most 2n−3 flips. In this algorithm, a variation of selection 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 led by Founders Professor Hal Sudborough announced the acceptance by the journal Theoretical Computer Science 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.[2][3]
On November 2, 2011, a paper was submitted to the arXiv announcing a proof that the problem is NP-hard, thereby answering a question open for over three decades[4].
[edit] 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 computer that can solve a simple example of the burnt pancake problem by programming E. coli to flip segments of DNA which are analogous to burnt pancakes.[5][6][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.[7] An animation depicting this process has been produced.[8]
[edit] 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. 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-complete. They also gave bounds for the same. Hurkens et al. gave an exact algorithm to sort binary and ternary strings. 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.
[edit] 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.[9] In addition, the most notable paper published by Futurama co-creator David X. Cohen (as David S. Cohen) concerned the burnt pancake problem.[10] 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 [Kaplan, Shamir, Tarjan, 1997],[11] the problem of sorting by reversals has been proven to be hard even to approximate to within certain constant factor [Berman, Karpinski, 1999],[12] and also proven to be approximable in polynomial time to within the approximation factor 1.375 [Berman, Karpinski, Hannenhalli, 2002].[13]
[edit] 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 of Neil Sloane:
A058986 – maximum number of flips- A067607 – number of stacks requiring the maximum number of flips (above)
- A078941 – maximum number of flips for a "burnt" stack
- A078942 – the number of flips for a sorted "burnt-side-on-top" stack
- A092113 – the above triangle, read by rows
[edit] References
- ^ Fertin, G. and Labarre, A. and Rusu, I. and Tannier, E. and Vialette, S. Combinatorics of Genome Rearrangements. The MIT Press, 2009.
- ^ "Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics". University of Texas at Dallas News Center. September 17, 2008. http://www.utdallas.edu/news/2008/09/17-002.php?WT.mc_id=NewsEmails&WT.mc_ev=EmailOpen. Retrieved 2008-11-10. "A team of UT Dallas computer science students and their faculty adviser have improved upon a longstanding solution to a mathematical conundrum known as the pancake problem. The previous best solution, which stood for almost 30 years, was devised by Bill Gates and one of his Harvard instructors, Christos Papadimitriou, several years before Microsoft was established."
- ^ Chitturi, B., Fahle, W., Meng, Z., Morales, L., Shields, C.O., Sudborough, I. H., and Voit, W. "An (18/11)n upper bound for sorting by prefix reversals." Theoretical Computer Science, 410(36), 3372-3390, 2009.
- ^ Bulteau, L. and Fertin, G. and Rusu, I. Pancake Flipping Is Hard. Submitted, 2011.
- ^ Solving the Pancake Problem with an E. coli Computer
- ^ iHOP meets iGEM
- ^ Haynes, K.A., et al. "Engineering bacteria to solve the Burnt Pancake Problem." Journal of Biological Engineering, 2(1), 8, 2008.
- ^ E.HOP - E. coli House of Pancakes - computing in vivo (flash applet)
- ^ Gates, W. and Papadimitriou, C. "Bounds for Sorting by Prefix Reversal." Discrete Mathematics, 27, 47-57, 1979.
- ^ Cohen D.S. and Blum, M. "On the problem of sorting burnt pancakes." Discrete Applied Mathematics, 61, 105-120, 1995.
- ^ Kaplan, H., Shamir, R. and Tarjan, R.E. "Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals." Proc. 8th ACM-SIAM SODA (1997), 178-187, 1997.
- ^ Berman, P. and Karpinski, M. "On Some Tighter Inapproximability Results." Proc. 26th ICALP (1999), LNCS 1644, Springer, 200-209, 1999.
- ^ Berman, P., Karpinski M. and Hannenhalli, S., "1.375-Approximation Algorithms for Sorting by Reversals." Proc. 10th ESA (2002), LNCS 2461, Springer, 200-210, 2002.
B. Chitturi and H. Sudborough, Prefix reversals on strings, Proc. Int. Conf. Bioinformatics and Computational Biology, Vol. 2 (2010)591–598.
C. Hurkens, L. V. Iersel, J. Keijsper, S. Kelk, L. Stougie and J. Tromp, Prefix reversals on binary and ternary strings, SIAM J. Discrete Math. 21(3)(2007) 592–611.
B. Chitturi, A note on complexity of genetic mutations, DMAA 3(3) (2011)269-286 DOI: 10.1142/S1793830911001206.
[edit] 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.
[edit] 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.
|
|||||||||||||||||||||||||||||
