The algorithmic problem solving group conducts research into mathematical method, in particular the problem-solving skills involved in the formulation and solution of algorithmic problems. Our goal is to articulate these skills primarily by way of concrete examples, but also by the development of appropriate mathematical theory.
Here is a list of the research themes that support the research strategy of our group.
Mathematics of Program Construction
Research into the mathematics of program construction has been a major theme for twenty years. This is a very broad area because of the nature of program construction. Our work encompasses relation algebra, the theory of ordered sets and category theory, fixed-point calculus, and the theory of datatypes. Contributions we have made in this area can be found here.
Currently we are exploring connections between generating functions and datatypes. We want to understand the extent to which equational reasoning about generating functions (in the domain of complex numbers) is applicable to the construction of isomorphisms between datatypes. Background material for this work is: Blass, Fiore and Leinster, Fiore 2004, Flajolet and Sedgewick, Graham, Knuth and Patashnik, Bergeron, Labelle and Leroux, and Stanley.
Work is also continuing on a (relational) generic theory of datatypes. See the work on fanclubs.
Algorithmic Skills for Mathematics
Over the last forty years, the unprecedented scale of programming problems, and the consequent demands on precision and concision have forced computing scientists to hone their algorithmic problem solving skills to a very fine degree. Even so, and although much of mathematics is algorithmic by nature, the skills needed to formulate and solve algorithmic problems do not form an integral part of mathematics education.
The Algorithmic Problem Solving group develops educational material to support the use of a calculational approach to algorithmic problem solving. Part of this material is currently being taught to computing science undergraduates, and it will also be tested at a pre-university level.
Structure Editing of Mathematics
Doing mathematics involves the use of algebraic rules to manipulate formulae and also the repeated copy of large expressions with only small changes. This is time consuming when done using pen and paper or when using a computer, since the keyboard and mouse are not oriented to write mathematics.
Tools to assist the writing of mathematical documents are needed. These tools should provide selection and copy-and-paste of expressions. It is also desirable that they support the systematic use of algebraic rules by applying them automatically. These actions should be as accurate and simple to use as possible to avoid the introduction of error while doing calculations.
The MathSpad system, developed by Richard Verhoeven, is a structure editor for mathematical documents that has proved very convenient for writing research articles across a wide spectrum of computing science. But given the time that it was developed, it assumes keyboard/mouse input and manipulation of documents. With the advent of the Tablet PCs, the creation of mathematical text has the potential to be much more straightforward using online recognition techniques. This, combined with a structure editor can make the writing of mathematics a more pleasant and easier task.
The Algorithmic Problem Solving group is currently creating a tool for Tablet PCs that will allow writing mathematical documents in a computer using a pen and also manipulate the structure of the handwritten expressions. It will provide accurate selection, copy-and-paste, and use of algebraic rules. The goal is to provide a tool that will assist the writing of mathematical documents and the teaching of the dynamics of algorithmic problem solving.
George Polya has made invaluable contributions to articulating problem-solving skills and was a major early influence on our work. We strongly recommend students to read his publications; his “How to Solve It” is deservedly a classic.
We share with Polya the approach of seeking out concrete problems; to him is also due the articulation of the basic techniques of understanding the problem and formulating a plan. We differ from Polya’s view of the importance of being a good guesser; whilst problem solving will always involve an element of creativity, we believe the key to success is to limit the amount of guesswork by goal-directed calculation. Indeed, we believe that a major defect of the way mathematics is currently practised (at least in our experience) is the predominant use of post hoc verification (the guess-and-verify approach). Of lesser significance is that our focus is on algorithmic problems; some of the problems that Polya discusses are less relevant to our theme. (Had Poly lived a few decades later, it is very likely that his focus would have been different too.)
The most major influence on our work has been Edsger Dijkstra. Although best known for his work in computing science, Dijkstra devoted much of his later career to mathematical method. He was a problem-solver par excellence and his “EWD” reports contain many instructive examples of his skills. However, possibly because he did not belong to the mathematical community and possibly because he did not hesitate to highlight bad as well as good technique, his work on mathematical method is, as yet, largely unrecognised.
The following citation, taken from EWD 709 (“My hopes of Computing Science”), is particularly appropriate to our own goals:
For me, the first challenge for Computer Science is to discover how to maintain order in a finite, but very large, discrete universe that is intricately intertwined. And a second, but not less important challenge is how to mould what you have achieved in solving the first problem, into a teachable discipline: it does not suffice to hone your own intellect (that will join you in your grave), you must teach others how to hone theirs. The more you concentrate on those two challenges, the more you will see that they are only two sides of the same coin: teaching yourself is discovering what is teachable.
The EWD reports mentioned above are available from Dijkstra’s archive. Netty van Gasteren’s PhD thesis (supervised by Dijkstra) is also well worth reading for its discussion of good and bad technique in problem-solving.
The focus on the importance of calculational technique is echoed in the book Concrete Mathematics by Graham, Knuth and Patashnik. Here are a couple of quotations from the book which are particularly relevant to our own goals:
Once you, the reader, have learned the material in this book, all you will need is a cool head, a large sheet of paper, and fairly decent handwriting in order to evaluate horrendous-looking sums, to solve complex recurrence relations and to discover subtle patterns in data.
Induction has its place, (…) but it’s still not really what we’re seeking. (…) Flashes of inspiration should not be necessary. We should be able to do sums even on our less creative days.