Jonathan Turner is a Senior Professor in the Department of Computer
Science and Engineering, at Washington University.
While no longer a full-time faculty member, he continues to
work on selected research projects.
His research interests include the design of instruments for
automated long-term monitoring of marine environments,
hyper-spectral analysis of seawater,
design and analysis of algorithms and data structures.
He is a Fellow of the IEEE, a Fellow of the ACM and a
member of the National Academy of Engineering.
- The Optical Phytoplankton Detector (OPD) is a marine spectrophotometer first
developed by the Mote Marine Research Laboratory starting around 2005.
It performs automated sampling and analysis of seawater and has been used
to detect the presence of the algae responsible for causing red tide.
provides a high-level overview of the OPD and describes the software
that controls it, primarily as an aid to software developers who
may be called upon to maintain the software and expand its capabilities.
edge coloring is a generalization of the classical
edge coloring problem in which each edge has a specified minimum
color. We show that the problem is NP-complete and
study several approximation algorithms for it.
Bounded edge coloring is an abstraction of an offline crossbar
scheduling problem and has implications for the minimum speedup
required to achieve ideal performance.
Let G=(V,E) be an undirected graph with n vertices and m edges,
in which each vertex u is assigned an integer priority in [1,n],
with 1 being the ``highest'' priority. Let M be a matching of G.
We define the priority score of M to be an n-ary integer in
which the i-th most-significant digit is the number of vertices
with priority i that are incident to an edge in M.
This problem can be solved in O(mn) time using a variation
of the augmenting path method (Edmonds' algorithm).
separate paper gives an algorithm for the case of
bipartite graphs which is faster when the number of distinct
priorities is limited.
- Multicast switch scheduling. Packet scheduling in
is an interesting and challenging problem. While the unicast case
is fairly well-understood, relatively little is known about
the multicast case. One version of this problem can
be formulated as an
edge group coloring
problem in bipartite graphs.
In this problem, each vertex in the input subset divides
its incident edges into groups. Edges belonging to
different groups at a given vertex are required to have different
colors. Edges in the same group may share a color.
The objective of the problem is to color all the edges using as
few colors as possible. Such a coloring corresponds to a crossbar
switch schedule that transfers multicast packets from inputs to
outputs in the fewest steps.
The problem is NP-complete and the best approximation
algorithm known has a performance bound of
O(log n/log log n).
is a library of graph algorithms
and supporting data structures. It was developed primarily for
pedagogical purposes, and the code is designed to be reasonably
easy to read and understand.
This makes it relatively straightforward to modify and extend
the library for other purposes.
Attention Prospective Graduate Students: I am no longer accepting new students
In theory, there's no difference between theory and practice.
In practice, there is. Jan L. A. van de Snepscheut
Don't worry about other people stealing your ideas.
If your ideas are any good, you'll have to ram them down peoples' throats.
A design is complete not when there is nothing more to add,
but when there is nothing more that can be taken away.
Antoine de Saint-Exupery
A scientific theory should be as simple as possible.
But no simpler.
I apologize for writing such a long letter. I did not have time
to write a shorter one. Blaise Pascal
Omit needless words. Theodore Strunk
Asking if computers can think is like asking if submarines can swim.
The real question is not whether computers think, but whether people do.
B. F. Skinner
I think, therefore I am. Rene Descartes