I am a member of the
ACM. If you are a student interested
in research, perhaps you should be, too!
Job postings
I share job postings with my former and current students via email
to current students in some senior courses, and via LinkedIn. If you
are a previous student of mine, please invite me to link with you on LinkedIn.
Research
My research interests include discrete algorithms, particularly algorithms for generating combinatorial objects.
In 2013-14, I was on sabbatical. I spent a semester as Visiting Professor at the University of Toronto, conducting research with colleagues
Professor Derek G. Corneil
and Lalla Mouatadid. VIU folk may remember Lalla from the days when she
was an undergrad here in Computing Science. Now she has completed her Master's degree in Computer Science at the University of Toronto, and has begun her Ph.D. work.
My plan had been to get Derek and Lalla to work with me on
Generating Ideals of a Poset, but they had such an intriguing area of
research already developed,
with several results already to their names -- and with a poset connection
to their work that needed exploring. The result of that collaboration is
an algorithm for the bump number of a poset -- in near-layperson terms, the
task here is to schedule a bunch of jobs, among which there is a set of
precedent constraints (i.e., of the type: "job A must be scheduled before
job B"), and the goal is to minimize the number of "bumps", where we
can imagine a bump as being a cost associated with scheduling a job immediately
after one that is constrained to be scheduled before this. Such a
circumstance arises when, for example, precedence constraints are a
result of outputs (such as data) from one job being required as inputs to
another job, and there is a communication delay in tranferring the output.
The delay is immaterial unless the job that needs the data is scheduled
immediately after the job that produces it. The task now is to construct the
schedule with the fewest number of communication delays. Our new algorithm
is a simple yet efficient algorithm to find the optimal schedule, and furthermore has an
elegant proof of correctness.
Older Research
I will post some links to older papers here some day. In the meantime, I get reqests for a cool proof I found for the Reed-Dawson identity (also known
as Knuth's Old Sum):
