University of Otago logo. Computer and Information Science Seminars

Seminar Homepage


Mike Atkinson, Department of Computer Science


Stacks, deques, and permutations


Archway 2 - 1:00 pm, Friday 11 July


2008 is the forty-year anniversary of the publication of volume 1 in Knuth's Art of Computer Programming series. This seminar marks the occasion by considering Exercise which asked how many permutations of length n can be obtained with a double-ended queue. This problem is still unsolved but we report on recent progress, and progress on other problems also raised by Knuth. We shall begin by explaining the problems and continue by sketching out some techniques based on finite automata which give rise to approximate solutions.

Last modified: Tuesday, 01-Jul-2008 10:18:14 NZST

This page is maintained by the seminar list administrator.