Academic Webpage for Aaron Williams
Photo by Dave Matthews
Contact
Research Interests and CV
My academic CV and research interests as of June 2011 are available.
Teaching
Research Positions
Refereed Journal
(2011) 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 )).
(2011) Ruskey, F. , Sawada, J. , and Williams, A. Fixed-Density de Bruijn Sequences SIAM Journal of Discrete Mathematics .
The title may be Fixed-Weight Binary de Bruijn Cycles in the final version.
(2011) Ruskey, F. , Sawada, J. , and Williams, A. Binary Bubble Languages and Cool-lex Order Journal of Combinatorial Theory, Series A .
(2011) Holroyd A. , Ruskey, F. , and Williams, A. Shorthand Universal Cycles for Permutations Algorithmica .
(2011) Ruskey, F. , and Williams, A. The Feline Josephus Problem Theory of Computing Systems .
(2010) 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 (June 2010).
(2009) 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
Refereed Conference
(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.
(2011) Stevens, B. , and Williams, A. Hamilton Cycles in Restricted Rotator Graphs IWOCA 2011 , The 22nd International Workshop on Combinatorial Algorithms, Victoria, Canada.
(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 F2 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 K5 -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 .
One result in my thesis is illustrated by the following Flash animation using the multiset {1,1,2,3,4,4}.
The first symbol a is shifted to the right until it passes over consecutive symbols b c with b < c .
a > b , then a is inserted after b ; otherwise, if a <= b , then a is inserted after c .
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).
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)
