Loading Events

Computer Science Colloquium - "Gray Codes, Puzzles, Video Games, and Computational Complexity"

Tuesday 1/15 @ 2:35pm in TPL 203
Computer Science Faculty Candidate Aaron Williams

Gray Codes, Puzzles, Video Games, and Computational Complexity

Computer scientists learn the standard method for counting in binary during their introductory courses. However, in many situations it is simpler and more efficient to use an alternate method. In particular, a ​Gray code​ is any ordering in which single bit changes always create the next binary string.

This talk surveys the history of Gray codes dating back to the 1600s along with standard applications, including brute force solutions to classic problems like Hamilton path and the partition problem. Then Gray codes are used as a common thread through broader discussions on the history and computational complexity of puzzles and video games. In particular, we will learn why pencil-and-paper puzzles like Sudoku are NP-complete while sliding block puzzles like Rush Hour are PSPACE-complete. The talk will feature several hands-on exercises including video game playing and live programming in Python. To fully participate in the digital exercises please consider bringing a laptop or tablet. Resources for the course will be stored on a Google Classroom which can be accessed from ​http://classroom.google.com​ using the code 7816yn​ and your ​@williams.edu​ Google account. Email ​aw14@williams.edu​ with any accessibility concerns or issues joining the online classroom.

Aaron Williams was born and raised near Toronto and attended several Canadian institutes as a graduate student and postdoc including the University of Waterloo, University of Victoria, and McGill University. His research often involves unorthodox algorithms or hardness proofs. He has published 50 academic papers, and regularly attends a variety of conferences including the ACM/SIAM Symposium on Discrete Algorithms (SODA), Fun with Algorithms (FUN), and the Canadian Conference on Computational Geometry (CCCG).

In 2014 Aaron joined the faculty at Simon’s Rock, which is a small liberal arts college in Great Barrington, MA. The computer science program has since grown to be one of the largest concentrations on campus with total enrollment increasing nearly 500% in five years. Recent graduates of the BA program have gone on to high ranking graduate programs and have earned desirable positions in industry, including multiple positions at Google. Aaron is also committed to undergraduate research and has supervised a dozen students on their first publications or conference presentations.

When not working as a computer scientist, Aaron enjoys bicycling and has completed rides over the Rocky and Andes Mountains. He also collects retro video game systems and enjoys implementing new games on older systems (e.g. Intellivision) and on low-power modern handhelds (e.g. Arduboy). Some of Aaron’s work has received media attention including widely spread stories on the FIFA World Cup and Super Mario Bros. Aaron lives in the Berkshires with his partner Elizabeth Hartung who is a professor of mathematics at MCLA. They are expecting their first child in the summer of 2019.

Event/Announcement Navigation