bg

Thomas Library

Honors Thesis Archive

Author Alyssa Armstrong
Title The Pancake Problem: Prefix Reversals of Certain Permutations
Department Mathematics
Advisors Adam Parker, Steve Bogaerts, and Jeremiah Williams
Year 2009
Honors University Honors
Full Text View Thesis (271 KB)
Abstract The Pancake Problem concerns the minimum number of moves needed to order a random stack of di fferently-sized pancakes. Mathematically, this problem translates to flipping prefi xes 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 de fine a set of algorithms that require fewer reversals than Gates' algorithm in certain cases.

Return to Main Honors Thesis Archive Page