Special Seminar by Associate Professor Murray Elder from UTS Sydney, Australia
Title: Avoiding permutations and sorting with stack
Date: 13 September 2019 13:30 – 14:30
Venue: M 307 Faculty of Science, Mahidol University
I will describe some problems in combinatorics, motivated by computer science. Given some out-of-order data set, when is it possible to sort the data by passing it one-way through some system of stacks? For a single infinite stack, Knuth showed it is possible if and only if the data list avoids any sublist of “middle Big small” (not necessary contiguously). I will describe some of the many variations of this, including new work of my student Andrew Goh.