Honors Thesis Archive
Author | Alyssa Armstrong |
---|---|
Title | The Pancake Problem: Prefix Reversals of Certain Permutations |
Department | Mathematics |
Advisors | Dr. Â鶹´«Ã½ Parker, Dr. Steve Bogaerts, and Dr. Jeremiah Williams |
Year | 2009 |
Honors | University Honors |
Full Text | (271 KB) |
Abstract | 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. |
Return to Main Honors Thesis Archive Page
Back