
1.
Armstrong, Alyssa.
The Pancake Problem: Prefix Reversals of Certain Permutations.
Degree: BS, Math, 2009, Wittenberg University Honors Theses
► The Pancake Problem concerns the minimum number of moves needed to order…
(more)
▼ The Pancake Problem concerns the minimum number of moves needed to order a random stack of differently-sized pancakes. Mathematically, this problem translates to flipping prefixes of permutations until the identity permutation is achieved. Bill Gates and Christos Papadimitriou created an algorithm in 1979 that improved the lower bound of the Pancake Problem. While Gates and Papadimitriou characterized a permutation based on blocks, I consider transposition decomposition and define a set of algorithms that require fewer reversals than Gates’ algorithm in certain cases.
Advisors/Committee Members: Adam, Parker.
Subjects: Computer science; Mathematics
Keywords: sorting algorithms
More Like This