Bibliography: Pancake Sorting

Pancake Sorting, Prefix Reversals, and DNA Rearrangements

The seemingly simple problem of sorting a stack of differently sized pancakes has become a staple of theoretical computer science and led to insights into the evolution of species. First proposed many years ago in The American Mathematical Monthly, the problem attracted the attention of noted mathematicians and computer scientists. It now plays an important role in the realm of molecular biology for making sense of DNA rearrangements.

Online Bibliography

Pancake Sorting, Ivars Peterson's MathTrek, MAA Online, Sept. 4, 2006.

Improved Pancake Sorting. Mathematical Tourist, MAA Online,  Oct. 9, 2008.

Dweighter, H. (pseudonym for Jacob E. Goodman). 1975. Problem E2569. American Mathematical Monthly 82:1010.

Hayes, Brian. 2007. Sorting out the genome. American Scientist 95(September-October):386-391.

Malkevitch, J.  2002. Pancakes, graphs, and the genome of plants. UMAP Journal of Undergraduate Mathematics and Its Applications  23(No. 4) (2002) 373-382. See Pancakes, graphs and the genomes of plants (preprint).

Sloane, N.J.A. 2000. My favorite integer sequences.

Pancake Sorting, Wolfram MathWorld.

Pancake Sorting, Wikipedia.

Sorting by prefix reversal, Sequence A058986, On-Line Encyclopedia of Integer Sequences.

Flipping Pancakes (Pancake sorting as a game, Flipper), Cut the Knot.

"Research Team Scores Big for Bio-Computer That Sorts "Burnt Pancakes," Davidson College, Nov. 23, 2006.

"Team Bests Young Bill Gates with Improved Answer to So-called Pancake Problem," University of Texas at Dallas, Sept. 17, 2008.

Computer Science

Chitturi, B., W. Fahle, Z. Meng, L. Morales, C.O. Shields, I.H. Sudborough, and W. Voit. In press. An (18/11)n upper bound for sorting prefix reversals. Theoretical Computer Science.

Cohen, D.S., and M. Blum. 1995. On the problem of sorting burnt pancakes. Discrete Applied Mathematics 61:105-120.

Gates, W.H., and C.H. Papadimitriou. 1979. Bounds for sorting by prefix reversal. Discrete Mathematics 27:47-57.

Haynes, K., et al.  2008. Engineering bacteria to solve the Burnt Pancake Problem. Journal of Biological Engineering, 2:8.

Heydari, M.H., and I.H. Sudborough. 1997. On the diameter of the pancake network. Journal of Algorithms 25(October):67-94.

The Pancake Problems (1975, 1979, 1973), Douglas B. West, University of Illinois, Urbana-Champaign.

"Before Microsoft, Gates Solved a Pancake Problem," David Kestenbaum, Morning Edition, National Public Radio, July 4, 2008.

Molecular Biology

Hannenhalli, S., and P. Pevzner. 1995. Transforming cabbage into turnip: Polynomial algorithm for sorting signed permutation reversals.

Genome Rearrangements in Man and Mouse (GRIMM), Glenn Tesler, University of California, San Diego.