Special Seminar by Associate Professor Murray Elder (13/9/2019)

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

Abstract:

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.