Suggestions for individual projects

Roland Backhouse

This is a list of project suggestions for the academic year 2010/2011. If you are interested in one or more of the projects, or would like to do something similar, then please come to see me (room B30) or send me an email to arrange an appointment.

In general, I am interested in projects that have a strong algorithmic content; I would be pleased to supervise projects of this nature in areas other than those listed below.

Currently, I am particularly interested in projects concerned with Algorithmic Problem Solving. This includes the design and implementation of new algorithms (which is often very challenging) and the development of material to assist in teaching. The first four projects listed below are relevant. Similar projects are also possible.

The General Torch Problem

I have published an algorithm for solving a generalised version of a well-known "flashlight"/"bridge"/"torch" problem. It is an optimisation problem and the solution uses techniques from dynamic programming. The project would entail implementing my solution and making it available on the internet. There is scope for further work (related to shortest-path algorithms) aimed at improving the efficiency of the algorithm.

Combinatorial Games

I use combinatorial games in the first-year undergraduate module on Algorithmic Problem Solving in order to illustrate algorithm-design principles. A project is to develop software to test the students' understanding of game theory (the use of so-called "mex" functions).

Solitaire-Like Games

Wei Chen and I have recently invented a novel class of solitaire-ike games played on a one-dimensional tape. The solution of these games involves exploiting polynomial arithmetic. The project would be to develop efficient solutions for particular subclasses of the games and to implement the solutions in a way that can be used to support the teaching of the techniques.

DNA analysis

The project is to explore the use of non-standard shortest-path algorithms when comparing pairs of DNA sequences.

Last modified: Thursday 27th January 2010