Research Interest: Algorithms, gray codes, de Bruijn sequences, computational complexity of video games,
graph theory, combinatorics
Teaching Interest: Algorithms and data structures, discrete mathematics, artificial intelligences, programming
languages, history of video games
Other Interests: Bicycling, travel, retro video games, jenga, Chromebooks
Biography
PhD in Computer Science, University of Victoria MMath in Combinatorics, University of Waterloo BMath in Computer Science & BMath in Combinatorics, University of Waterloo
Dr. Williams has completed a series of postdocs including one in Computer Science
at the University of Guelph with Joe Sawada in 2009, another in Mathematics at Carleton
University with Brett Stevens in 2010-2011, and another in Mathematics at McGill University
with Bruce Shepherd in 2012-2013. He has been teaching at Simon's Rock since 2014.
Highlights
Research with Students
Buttons & Scissors is a popular puzzle app for both Android and iOS devices. The study
of its difficulty (or "computational complexity") was initiated at Simon's Rock by
students Harrison Gregg, Jody Leonard, and Aaron Santiago. This work eventually led
to a joint publication with a dozen researchers from around the world.
De Bruijn Sequences are classic objects in combinatorial mathematics with applications to computer science.
Summer research with the student Oscar Hernandez led to a simple new algorithm for
constructing de Bruijn sequences. This work was published and became the basis for Oscar’s senior thesis.
Media
In 2009 Dr. Williams discovered a shortcoming in the FIFA World Cup tiebreaker rules.
The flaw can lead to situations in which three different countries can argue that
they logically deserve a top-2 position after the initial group stage. The story was
picked up by the American Mathematical Society and was featured in various television and newspaper reports. The issue has not been resolved by FIFA (see FIFA 2018 rules Article 20.6 ) even though two soccer officials gave contradictory interpretations of the scenarios
he had constructed.
Dr. Williams helped prove that a simple generalized version of Super Mario Bros. is
NP-complete. This result was published along with a new result establishing its PSPACE-completeness. Media attention included
cursory coverage by Wired and Popular Science, and more in-depth coverage by MIT and other sources.