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 TheAmerican 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.

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).

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.