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
