Honors Thesis Archive
| Author | Alyssa Armstrong |
|---|---|
| Title | The Pancake Problem: Prefix Reversals of Certain Permutations |
| Department | Mathematics |
| Advisors | Dr. Adam Parker, Dr. Steve Bogaerts, and Dr. 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
Back