Academic Webpage for Aaron Williams

Photo by Dave Matthews

Contact

Research Interests and CV

My academic CV and research interests as of January 2012 are available.

Teaching

Honours Algorithms and Data Structures (COMP 252) at McGill University in Winter 2012. Web page
Theory of Automata (MATH 4805/5605 COMP 4805) at Carleton University in Fall 2010. Web page.
Logic and Programming (CSC 322) at the University of Victoria in Fall 2007. Web page / evaluation.
Algebra for Honours Mathematics (MATH 135) at the University of Waterloo in Fall 2003.

Research Positions

Postdoc in the Department of Mathematics and Statistics at McGill University with Bruce Shepherd and Bruce Reed 09/2011 - 08/2012.
Postdoc in the School of Mathematics and Statistics at Carleton University with Brett Stevens, 05/2010 - 08/2011.
Roncesvalles postdoc in the School of Computer Science at the University of Guelph with Joe Sawada, 01/2010 - 04/2010.
NSERC PGS D researcher during my PhD in the Department of Computer Science at the University of Victoria with Frank Ruskey and Wendy Myrvold.
OGS researcher during my Masters in the Department of Combinatorics and Optimization at the University of Waterloo with Bertrand Guenin.

Publications

Refereed Journal

Durocher, S., Li, B.P., Mondal, D., Ruskey, F.and Williams, A. Cool-lex Order and k-ary Catalan Structures. Accepted to Journal of Discrete Algorithms. 33 pages.
Ruskey, F., Sawada, J., and Williams, A. De Bruijn Sequences for Fixed-Weight Binary Strings. Accepted to SIAM Journal of Discrete Mathematics. 12 pages
Sawada, J., and Williams, A. Efficient Oracles for Generating Binary Bubble Languages. Electronic Journal of Combinatorics, 19, 2012, P42.
Sawada, J., and Williams, A. A Gray Code for Fixed-Density Necklaces and Lyndon Words in Constant Amortized Time. Theoretical Computer Science (special issue for GASCOM 2010) DOI 10.1016/j.tcs.2012.01.013 .
Holroyd A., Ruskey, F., and Williams, A. Shorthand Universal Cycles for Permutations. Accepted to Algorithmica. Online version. DOI: 10.1007/s00453-011-9544-z.
Ruskey, F., Sawada, J., and Williams, A. Binary Bubble Languages and Cool-lex Order. Journal of Combinatorial Theory, Series A, 119, 1, 2012, 155-169.
Ruskey, F., and Williams, A. The Feline Josephus Problem. Theory of Computing Systems 50, 1, 2012, 20-34.
Ruskey, F., and Williams, A. An Explicit Universal Cycle for the (n-1)-Permutations of an n-Set. ACM Transactions on Algorithms Volume 6, Issue 3, Article 45, 2010.
Ruskey, F., and Williams, A. The Coolest way to Generate Combinations. Discrete Mathematics. Special Issue on Generalizing de Bruijn Cycles and Gray Codes (Edited by G. Hurlbert, B. Jackson, and B. Stevens) 309, 17, 2009, 5305-5320.

Submitted to Journal

Myrvold, M., and Williams, A. The Binary Graceful Forests. 23 pages. (Link available soon.)
Stevens, B., and Williams, A. Hamilton Cycles in Restricted and Incomplete Rotator Graphs. Submitted to Journal of Graph Algorithms and Applications. 26 pages.

Refereed Conference

(2012) Stevens, B., and Williams, A. The Coolest Order of Binary Strings. FUN 2012, The 6th International Conference on Fun with Algorithms, San Servolo Island, Venice, Italy, LNCS 7288 (2012) 322-333.
(2011) Durocher, S., Li, B.P., Mondal, D., and Williams, A. Ranking and Loopless Generation of k-ary Dyck Words in Cool-lex Order. IWOCA 2011, The 22nd International Workshop on Combinatorial Algorithms, Victoria, Canada, LNCS 7056 (2011) 182-194.
(2011) Stevens, B., and Williams, A. Hamilton Cycles in Restricted Rotator Graphs. IWOCA 2011, The 22nd International Workshop on Combinatorial Algorithms, Victoria, Canada, LNCS 7056 (2011) 324-336.
(2011) Sawada, J., Stevens, B., and Williams, A. De Bruijn Sequences for Binary Strings with Maximum Density. WALCOM 2011, The 5th International Workshop on Algorithms and Computation, New Dehli, India. LNCS 6552 (2011) 182-190.
(2010) Holroyd A., Ruskey, F., and Williams, A. Faster Generation of Shorthand Universal Cycles for Permutations. COCOON 2010, The 16th Annual International Computing and Combinatorics Conference, Nha Trang, Vietnam. LNCS 6196 (2010) 298-307.
(2010) Williams, A. O(1)-Time Unsorting by Prefix-Reversals in a Boustrophedon Linked List. FUN 2010, Fifth International Conference on Fun with Algorithms, Ischia Island, Italy. LNCS 6099 (2010) 368-379.
(2010) Ruskey, F., and Williams, A. The Feline Josephus Problem . FUN 2010, Fifth International Conference on Fun with Algorithms, Ischia Island, Italy. LNCS 6099 (2010) 343-354.
(2009) Williams, A. Loopless Generation of Multiset Permutations by Prefix Shifts. SODA 2009, Symposium on Discrete Algorithms, New York, United States. 20 pages.
(2008) Ruskey, F., and Williams, A. Generating Balanced Parentheses and Binary Trees by Prefix Shifts. CATS 2008, Computing: The Australasian Theory Symposium, New South Wales, Australia. Theory of Computing. 77: 9 107-115. (This paper won Best PhD Student Paper.)
(2007) Lee, G., Ruskey, F., and Williams, A. Hamming Distance from Irreducible Polynomials over F₂. AofA 2007, International Conference on Analysis of Algorithms, Juan-les-pins, France. Discrete Mathematics and Theoretical Computer Science: AH, 2007, 169-180.
(2006) Lee, O., and Williams, A. Packing Dicycle Covers in Planar Graphs with no K₅-e Minor. LATIN 2006, Latin American Symposium on Theoretical Informatics, Valdivia, Chile. Lecture Notes in Computer Science. 3887: 677-688.
(2005) Ruskey, F., and Williams, A. Generating Combinations by Prefix Shifts. COCOON 2005, International Computing and Combinatorics Conference, Kunming, China. Lecture Notes in Computer Science. 3595: 570-576.
(2005) Guenin, B., and Williams, A. Advances in Packing Directed Joins. GRACO 2005, Brazilian Symposium on Graphs, Algorithms, and Combinatorics. Electronic Notes in Discrete Mathematics. 19: 212-218.

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.

Ron Graham was the external examiner.
Don Knuth featured the shorthand universal cycle results in his Permutations Problems talk at the 2010 Joint Mathematics Meeting of the AMS / MAA.
The University of Victoria nominated it for the CAGS/UMI Distinguished Dissertation Award in 2009.
Chapter 1 was written with a general audience in mind, and follows "The Nine Billion Names of God" by Arthur C. Clarke.

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).

Solving Wilf's Sigma Tau Problem for Combinatorial Algorithms Group (University of Victoria) on February 24, 2012. (Abstract)
C Programs: Memoryless Sigma-Tau Path and Loopless Sigma-Tau Cycle.
Civilized Brute Force Algorithms for Fields Undergraduate Network: Discrete Mathematics Workshop on June 22, 2011. (Abstract)
Ranking and Loopless Generation of k-ary Dyck Words in Cool-lex Order for IWOCA 2011 in June 2011. (Abstract)
Hamilton Cycles in Restricted Rotator Graphs for IWOCA 2011 in June 2011. (Abstract)
New Constructions for Universal Cycles and de Bruijn Cycles for CanaDAM 2011 on May 31, 2011. (Abstract)
Efficient Generation of Hamilton Cycles in Restricted and Generalized Rotator Graphs for The 2nd Annual Workshop on Algorithmic Graph Theory on May 18, 2011.
Binary Graceful Forests for Banaras Hindu University in March, 2011.
Cooler Gray Codes and de Bruijn Cycles for Banaras Hindu University in March, 2011.
De Bruijn Sequences with Maximum Density at WALCOM 2011 in February, 2011.
Universal Cycles for Permutations Theory and Applications for Ottawa-Carleton Seminar of Combinatorics and Optimization on October 1st, 2010. This talk also presented the presentation below.
Ringing Campanologically New methods for Old Church Bells for Fields Institute Discrete Math Days 2010 on May 14th, 2010. This presentation was for a general audience. Click the black bar near each clef to hear audio clips.
O(1)-Time Unsorting by Prefix-Reversals in a Boustrophedon Linked List for FUN 2010 Conference on Ischia Island, Italy circa June 2010.
Gray Codes for Bubble Languages for 18th Ontario Combinatorics Workshop on May 7th, 2010. Part of this presentation was given on a chalk board.
Shift Gray Codes for my PhD Defense on October 23rd, 2009.
Fixed-Density de Bruijn Cycles for the CanaDAM 2009 Conference at Universite de Montreal circa May 2009.
Gray codes and universal cycles using shifts for the Discrete Mathematics and Optimization Seminar at McGill University circa January 2009.
Loopless Generation of Multiset Permutations using a Constant Number of Additional Variables using Prefix Shifts for the SODA 2009 conference circa September 2008. (This talk was also presented at the Seminar on New Developments in Discrete Algorithms and in Experimental Algorithms at The City University of New York circa April 2009.)
Right-Shift Gray codes, Shorthand Universal Cycles, and the Cool-lex Variation on Lexicographic Order for the Tutte Seminar at the University of Waterloo circa September 2008.
The Cool-Cat Algorithm and Gray Code for Balanced Parentheses for the Theory Seminar at the University of Auckland circa February 2008. (The first slide should be ignored.)
Shorthand Universal Cycles for Permutations for the CanaDAM 2007 Conference at the Banff Conference Center circa February 2007.

Art(icles)

Several articles were written about the ambiguous logic in the 2010 FIFA World Cup tiebreaker rules. (Interview posted.)
PostScript drawings of co-lex and cool-lex order. (You can modify the /S and /T parameters in a text editor to change the drawing.)
The above comparison published in The Feast (ISBN 0-978066-30-8) in 2006.
"Mile Zero Hero" on the uncelebrated 20th anniversary of Steve Fonyo's Journey for Lives published in The Martlet in 2005.
Presidential Debates as reality TV and sporting events (includes real box score) published in The Martlet in 2004.