About Me
My name's Sebastian Raaphorst, and I have recently completed my PhD in computer science at the University of Ottawa under the supervision of Lucia Moura and Brett Stevens. My focus is in combinatorial design theory and specifically covering arrays, although I'm very interested in machine learning as well. I am currently seeking a developer position in industry, preferably working in Java, C++, or Python, or further opportunities in academia.
I can be typically found studying Mandarin Chinese or Classical Chinese, watching television, reading, writing novels, cooking (preferably Thai food), jogging, playing video games, programming, or reading math and computer science books.
[back to top]Research Interests
The focus of my PhD research was on covering arrays, and in particular variable strength covering arrays. These are a type of combinatorial design that can be used to perform highly effective testing (combinatorial testing), which is one of the few types of testing where actual guarantees can be made as to the quality of testing. My interests are predominantly in combinatorial algorithms and machine learning, high performance computing, combinatorial design theory, coding theory, cryptography, and finite fields. I also have a strong background in integer programming and optimization, which was the focus of my Master's thesis. Both are available below in the Publications section.
[back to top]Code
Here is some code that I've written and am distributing for anyone who finds it useful. All code is released under the GNU GPL version 2.0. Note: While I program in C++, C, and Java, I prefer to program in Python when I have the option to do so. I firmly believe that Python teaches new programmers good programming techniques without overwhelming them in computer science concepts, and makes programming fun again (like back in the C64 days). *shakes his cane at you*
- Termite simulation (Java) - I have been interested recently in swarm optimization algorithms, and this is just the source code of a Termite simulation, where a number of termites begin on a plane covered in wood chips and move randomly. They pick up a woodchip when they hit one, and then continue to move randomly until they hit another woodchip, at which point, they put down their woodchip and respawn at a random position. Order emerges fairly quickly. The code, once unzipped, can be compiled via: javac TermiteFrame.java && java TermiteFrame
- VCADBGA / VarDens (Python) - Python library package of my VCADBGA / VarDens algorithm for finding variable strength covering arrays over arbitrary hypergraphs. The algorithm is of both practical and theoretical importance, in that it generates actual test suites, and analysis of the algorithm generates a guaranteed upper bound on the size of variable strength covering arrays. Based on Bryce and Colbourn's density algorithm for covering arrays. Can be built via: python setup.py install
- PynComb (Python) - Python library package of my PynComb PYthoN COMBinatorial algorithms. Contains algorithms to generate many different objects (permutations, subsets, k-subsets, etc) using different orderings (lexicographic, colex, minimal change, etc). This is the source code. The package can also be found on PyPi: http://pypi.python.org/pypi/pyncomb, at can be installed using pip install pyncomb or easy_install pyncomb.
- Boggleboard (Python) - Boggle board library package of my Boggle board solvers. Can generate Boggle boards from a standard set of Boggle dice, and can find complete solutions for given Boggle boards. You can also play with Boggle boards of arbitrary shape, such as toroidal boards (boards where you can traverse the boundaries); hexagonal boards, where instead of squares we have hexagons; hexagonal toroidal boards; and arbitrary anagrams / Scrabble hands. Uses a trie over an arbitrary word list (YAWL from http://www.gtoal.com/scrabble/yawl is provided). Package also found on PyPI: http://pypi.python.org/pypi/boggleboard. Can be installed from command line with pip install boggleboard or easy_install boggleboard.
- DLX (Python) - DLX (C) - Various implementations of Donald Knuth's DLX Dancing Links algorithm (http://arxiv.org/abs/cs/0011047), which is a clever depth-first search for solving combinatorial exact cover problems such as - most famously - Sudoku boards (my Sudoku solvers: Python - C) or Steiner designs (my design solver: Python). My Python dlx implementation in particular has been highly praised by many for being the fastest Python implementation available. The Python version is available on PyPI: http://pypi.python.org/pypi/dlx and can be installed via pip install dlx or easy_install dlx.
- Kakuro (Python) - Kakuro solver in Python. Available at PyPI (http://pypi.python.org/pypi/dlx) and can be installed via pip install kakuro or easy_install kakuro.
- Reed-Muller codes (Python) - Implementation of Reed-Muller encoding / decoding in Python (C implementation available in the Projects section). Convenience functions for command line execution available: tools. Can be found on PyPI: http://pypi.python.org/pypi/reedmuller and installed via pip install reedmuller or easy_install reedmuller.
- Agriscore (Java JAR) - Agriscore (Java source) - Score card calculator for the excellent board game Agricola. Can be run directly from the JAR using java -jar Agriscore-20090405.jar.
- Flasher (Python) - A light-based brainwave stimulator. Requires PyGame to run. Can cause seizures in those prone to such, since the whole point of the program is to flash a light at a set frequency. Use at your own risk.
- LJFuncs (Python) - A library of LiveJournal functions I was working on back when people still used LiveJournal. Can calculate discrepancies between friend and friend of lists, find friend-of-friend lists, and calculate user compatibility based on mutual interests (with weightings based on interest frequency) to suggest new friends.
- NIBAC (C++) - NIBAC (NonIsomorphic Branch-And-Cut), the result of my Master's Thesis. A 0-1 ILP branch-and-cut solver for highly symmetric ILPs such as those that arise in combinatorial design problems. Determines (or can be provided with) the symmetry group of the problem, and exploits this group to prune the search tree to avoid equivalent solutions.
- SmokingMeter (Java) - Code I wrote years ago to tell you how long you quit smoking, the number of cigarettes avoided, and the amount of money saved. (I quit smoking in 1999 and have saved about $20,000 from not smoking my previous 10 cigarettes a day.)
- Stack (C) - A quick implementation of a stack I did in C to help some students better understand C coding and data structures.
Projects
For the requirements of my Master's courses, I completed several projects. The resultant programs and papers are listed below:
- Reed-Muller Codes [PS] [PDF] [code]
- Using Isomorphism Pruning to Solve Symmetric ILPs [PS] [PDF] [code]
- Cookbook: A Usability Study [PS] [PDF] [code]
- A Usability Inspection of Several Graphical User Interface Toolkits [PS] [PDF]
- Parallel Algebraic Algorithms [PS] [PDF]
Publications
Academic:
- S. Raaphorst, L. Moura, and B. Stevens. Using the Lovasz Local Lemma to Derive Upper Bounds on Families of Variable Strength Covering Arrays. In preparation.
- Sebastian Raaphorst. Variable Strength Covering Arrays. PhD thesis, 2013. Available: [PDF]
- S. Raaphorst, L. Moura, and B. Stevens. A Construction for Strength-3 Covering Arrays from Linear Feedback Shift Register Sequences. In revision for Designs, Codes, and Cryptography.
- S. Raaphorst, L. Moura, and B. Stevens. A Density-Based Greedy Algorithm for Variable Strength Covering Arrays. Submitted to the Australasian Journal of Combinatorics.
- Sebastian Raaphorst. Branch-and-cut for symmetrical ILPs and combinatorial designs. Master's thesis, 2004. Available: [PDF]
- Lucia Moura and Sebastian Raaphorst. Distributed Isomorph-free Exhaustive Generation of Anti-Pasch Partial Triple Systems. Journal of Combinatorial Mathematics and Combinatorial Computing, 56:101-121, 2006.
Personal:
- Raaphorst, Sebastian. "Snow Angels", YAWP, University of Ottawa, 2003. Winner of the annual 2003 novella writing competition.
Contact Information
Here are some of the ways you can track me down:
- E-mail (TA): If I am your TA for a course, please e-mail me at: sebastian.teaching@gmail.com
- E-mail (Other): sraaphorst@gmail.com
- Office: SITE 3012