Dr. Joseph Sawada received his PhD from the University of Victoria in 2000. He spent two years working as an NSERC postdoctoral fellow visiting Charles University in the Czech Republic, the University of Sydney in Australia, and the University of Toronto. He joined the School of Computer Science at the University of Guelph in 2003. He co-founded FreshBooks, a Toronto-based tech company that employs many U of G co-ops and graduates.
Sawada’s research investigates a variety of combinatorial objects—from necklaces to free plane trees to stamp foldings to vertex orderings of chordal graphs. No interesting object is left behind. A primary goal of his work is to better understand the object in question by considering how to efficiently list all non-isomorphic instances of that. When there is a constant amount of change between successive objects, the listing is called a Gray codes. Recent areas of focus include:
de Bruin sequences and Universal cycles. A de Bruijn sequence is a string of length 2n where every length n binary string appears as a substring exactly once. There are many efficient constructions of such sequences and a current project is to survey these algorithms on the website http://debruijnsequence.org. It provides free, downloadable source code for those algorithms.
Combinatorial Object Server. First launched by Frank Ruskey, the Combinatorial Object Server has been re-launched at http://combos.org in collaboration with Torsten Mütze and Aaron Williams, launched the second generation of this tool. This community project is called COS++ and it enables the generation of combinatorial objects with parameters of your choice. It provides free, downloadable source code for those algorithms under the GNU General Public License).
Graphs. A variety of structured graphs are investigated in search of complexity results, recognition algorithms, and characterizations.
NSERC Discovery grant holder
Member of NSERC Discovery Evaluation Group (4 years)