Sorting Permutations with Finite-Depth Stacks

Authors

Timothy Goodrich, Valparaiso University
Drew Groth, Valparaiso University
Lauren Knop, Valparaiso University

Presentation Type

Poster Presentation

Symposium Date

Spring 2012

Abstract

Sorting organizes information for optimal usage and is desirable in many different fields. Noted computer scientist Donald Knuth first considered using stacks of infinite depth as a powerful means to sort data. We extend this work to consider stack-sortable permutations using stacks of specified finite depths. We characterize patterns that sortable permutations must avoid and derive a handy enumeration formula. Further generalizations include the introduction of multiple stacks and the analysis of the resulting counting sequences.

Biographical Information about Author(s)

Link to abstract only

Recommended Citation

Goodrich, Timothy; Groth, Drew; and Knop, Lauren, "Sorting Permutations with Finite-Depth Stacks" (2012). Celebration of Undergraduate Scholarship. Paper 148.