Research
My areas of interest lie within theoretical computer science, and
my main interest is in the design and development of algorithms.
Why algorithmics? I guess I like answering the question "But how can I
solve that problem?" in a computer science setting.
I also have other areas of interest in computer science, including
the use of mathematics for program construction, functional programming,
relational algebra, computer graphics, and human-computer interaction.
Much of my algorithmics work has been concerning combinatorial
optimization problems, which involve all sorts of fun examples, from
dartboards, to marbles, and even quilting!
My recent work involves developing a comprehensive theory for
greedy algorithms that solve optimization problems exactly.
Some older work I have done (details of publications are below) has
involved unifying two dynamic programming strategies (the "top-down" and the
"bottom-up" methods), and the development of my Graph Calculus (an
extremely helpful tool for trying to produce tricky proofs in the
relational calculus).
So, why the dartboard? Hey, the numbers are all wrong!
I currently have one research student, Mrs. Wejdan Iskander, who is
studying the effects of using computer-based visualization techniques to
teach mathematics to school children.
Up until 1998, I was at Oxford University Computing Laboratory, in the
Algebra of Programming research group.
Publications
- S. A. Curtis: The Classification of Greedy Algorithms (gzipped postscript)
-
Submitted to Theoretical Computer Science
[Abstract:
This paper presents principles for the classification of greedy
algorithms for optimization problems.
These principles are made precise by their expression in the
relational calculus, and illustrated by various examples.
A discussion compares this work to other greedy algorithms theory.]
-
S. A. Curtis:
On a selection problem and the largest multinomial frequency
-
Submitted to Information Processing Letters
[Summary:
This paper analyses a recently-discovered algorithm
concerning a selection problem: the algorithm itself is very simple,
but its time complexity turns out to be intriguingly complicated.]
-
S. A. Curtis:
Marble Mingling
-
to appear, Journal of Functional Programming
[Summary: Algorithms are presented for solving the problem of
obtaining as many differently-coloured(=mingled) selections
as possible from a bag of marbles. Expressing the algorithm in
a lazy functional language leads to greater efficiency.]
- S. A. Curtis:
A Generic Algorithm for Minimum Chain Partitioning
-
in "Generic Programming", edited by Jeremy Gibbons and
Johan Jeuring, Kluwer, 2003
(proceedings of the IFIP WG2.1 Working Conference on Generic Programming,
Dagstuhl, July 2002)
[Abstract: This presents a generic algorithm to obtain a minimum
sized partition of a partially ordered set into chains.
The algorithm is illustrated with three examples, including
a novel box stacking problem and solution.]
-
K. Hammond, S. Curtis (editors):
Trends in Functional Programming (volume 3)
-
published by Intellect, 2002
(proceedings of the 3rd Scottish Functional Programming Workshop, Stirling,
2001)
- S. A. Curtis: Laziness, Drugs and Jam Jars (gzipped postscript)
- in the draft proceedings of the 3rd Scottish Functional Programming
Workshop, Stirling, 2001
[Abstract: This concerns a combinatorial problem to allocate drugs
for a medical trial. Two algorithms are presented which solve a more
general problem, one of these making crucial use of laziness to
achieve a (not straightforward) linear complexity. These results
are then used to solve the original problem.]
- Sharon Curtis:
An Application of Functional Programming: Quilting
-
in "Trends in Functional Programming", edited by Stephen
Gilmore, vol. 2, Intellect, 2000
(proceedings of the 2nd Scottish Functional Programming Workshop, St.
Andrew's, 2000)
[Abstract:
Quilting (including the patchwork that the typical quilter
indulges in) is primarily a leisure activity, one which on the
surface seems to have little to do with functional programming.
However, both the patchwork and the social participation in
group projects often yield interesting combinatorial problems.
This paper looks at the suitability of functional programming for
solving these types of problems, considering two representative
problems and their functional solutions.]
(If you wish, you can see web pages of the star arrangement
problem described in colour, and also see a summary of the results of
the round robin arrangement problem, in this article about "Organising
a Stress-free Round Robin". You can also see the quilts that resulted
from the original round robin.)
- Sharon Curtis: Use of Relational Operators for Algorithm Development
(gzipped postscript)
- in the draft proceedings of the 1st Scottish Functional Programming
Workshop, Stirling, 1999
[Abstract: We examine the use of the relational limit operator for the
solution of combinatorial problems. In particular, the first developmental
steps from specifications and the construction of feasible solutions are
considered.]
- Sharon Curtis:
Dynamic Programming: a different perspective
- in Algorithmic Languages and Calculi, edited by R.S.Bird
and L.Meertens, Chapman and Hall; proceedings of the
IFIP TC2 Working Conference
on Algorithmic Languages and Calculi (Feb 1997), Le Bischenberg, France
[Abstract: Dynamic programming has long been used as an algorithm
design technique, with various mathematical theories proposed to model
it. Here we take a different perspective, using a relational calculus
to model both problems and their solutions obtained from dynamic
programming. This approach serves to shed new light on the different
styles of dynamic programming, represneting them by different search
strategies of the tree-like space of partial solutions.]
- Sharon Curtis and Gavin Lowe:
Proofs with Graphs
- Science of Computer Programming, 1996, volume 26, pages 197-216
[Summary: Defines a graphical calculus for aiding reasoning in the
relational and sequential calculi. In particular the power and expressivity
of the graph calculus is emphasized.]
- Sharon Curtis:
A Relational Approach to Optimization Problems
- (D.Phil thesis) Tech. report PRG-122 from Oxford University Computing
Laboratory, 1996
[Abstract: The main contribution of this thesis is a study of the dynamic
programming and greedy strategies for solving combinatorial optimization
problems. The study is carried out in the context of a calculus of
relations, and generalises previous work by using a loop operator
in the imperative programming style
for generating feasible solutions, rather than the fold and unfold
operators of the functional programming style.
The relationship between fold operators and loop operators
is explored, and it is shown how to convert from the former to the
latter.
This fresh approach provides additional insights into
the relationship between dynamic programming and greedy
algorithms, and helps to unify previously distinct
approaches to solving combinatorial optimization
problems. Some of the solutions discovered are new
and solve problems which had previously proved
difficult. The material is illustrated with a
selection of problems and solutions that is a mixture
of old and new.
Another contribution is the invention of a new calculus, called
the graph calculus, which is a useful tool for reasoning in the
relational calculus and other non-relational calculi.
The graph calculus represents formulae by formal pictures, and this
enables proofs to be expressed more simply. It is also more powerful
than standard point-free reasoning, and its simple intuitive basis
aids greater understanding of the structure of formulae and
certain proofs.]
- Sharon Curtis and Gavin Lowe:
A Graphical Calculus
- Presented at the Mathematics of Program Construction conference,
1995, and published in Lecture Notes in Computer Science, number 947.
[Abstract:
We present a graphical calculus, which allows mathematical formulae to be
represented and reasoned about using a visual representation. We define how a
formula may be represented by a graph, and present a number of laws for
transforming graphs, and describe the effects these transformations have on
the corresponding formulae. We then use these transformation laws to perform
proofs. We illustrate the graphical calculus by applying it to the relational
and sequential calculi. The graphical calculus makes formulae easier to
understand, and so often makes the next step in a proof more obvious.
Furthermore, it is more expressive, and so allows a number of proofs that
cannot otherwise be undertaken in a point-free way.]
|
