Academic Webpage for Aaron Williams

Feet Up
Photo by Dave Matthews

Contact

haron ampersat uvic.ca

Research Interests and CV

My academic CV and research interests as of June 2011 are available.

Teaching

Research Positions

Publications

Refereed Journal

Submitted to Journal

Refereed Conference

PhD Thesis

My PhD thesis "Shift Gray Codes" in combinatorial generation was recently completed under the supervision of Frank Ruskey and Wendy Myrvold in the Department of Computer Science at the University of Victoria.

One result in my thesis is illustrated by the following Flash animation using the multiset {1,1,2,3,4,4}.


The permutations of any multiset are generated by this simple rule:
The first symbol a is shifted to the right until it passes over consecutive symbols b c with b < c.
If a > b, then a is inserted after b; otherwise, if a <= b, then a is inserted after c.
(If there is no such b c then a is shifted until it passes over the rightmost symbol.)
This result leads to the first O(1)-time / O(1)-additional variable algorithm for generating the permutations of a multiset (see publication in SODA 2009).

Masters Thesis

My Masters thesis "Packing Directed Joins" in combinatorial optimization was done under the supervision of Bertrand Guenin in the Department of Combinatorics and Optimization at the University of Waterloo.

Talks

To navigate through the presentations use the arrow keys (.pdf) or click on the leaves along the bottom of the window (.swf).

Art(icles)