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.

List of Publications

List of recent publications of members of the Algorithmic Problem Solving group

Meeting a Fanclub: A Lattice of Generic Shape Selectors

Roland Backhouse, Richard Bird and Paul Hoogendijk, Workshop on Generic Programming WGP09, 2009.

The “fan” of a datatype F is a relation that holds between a value x and an arbitrary F structure in which the only stored value is x. Fans are used to make precise the notion of the shape of a data structure. For arbitrary datatypes F, G and H, we consider six different ways of composing their fans in order to construct F structures of G structures of H structures; each of the six imposes a different requirement on the shape of the substructures. We catalogue the relation between different combinations of the constructions. We apply the result to the shape properties of a natural transformation (aka polymorphic relation) from G structures to FG structures.

Available from: http://www.cs.nott.ac.uk/~rcb/MPC/FanClub.pdf

Work in Progress: Structure Editing of Handwritten Mathematics

Alexandra Mendes, Frontiers in Education (FIE) Conference, 2008.

This project aims to develop a pen-based software tool that will assist in the process of doing mathematics by providing structured manipulation of handwritten mathematical expressions.

The tool will be used to support the teaching of the dynamics of problem solving in a way that combines the advantages of the traditional blackboard style of teaching with the flexibility and accuracy of computer software. It will provide not only a simpler way to input mathematics – by allowing the recognition of handwritten mathematics -but also enhance students’ understanding of the calculational techniques and facilitate the process of doing mathematics – by providing structure editing. Some of the most important features of this tool are the accurate selection and copy of expressions, the automatic application of algebraic rules and the use of gestures to apply them, and also the combined writing of mathematics and text. These features will have a major impact on writing, doing, and presenting mathematics.

This project includes the required technical developments and also the application and testing of the tool in concrete situations, namely in mathematics and computing science courses.

The Capacity C Torch Problem

Roland Backhouse, Mathematics of Program Construction, 2008.

The torch problem (also known as the bridge problem or the flashlight problem) is about getting a number of people across a bridge as quickly as possible under certain constraints. Although a very simply stated problem, the solution is surprisingly non-trivial. The case in which there are just four people and the capacity of the bridge is two is a well-known puzzle, widely publicised on the internet. We consider the general problem where the number of people, their individual crossing times and the capacity of the bridge are all input parameters. We present an algorithm that determines the shortest total crossing time; the number of primitive computations executed by the algorithm (i.e. the worst-case time complexity of the algorithm) is proportional to the square of the number of people.

Link to the article