Suggestions for individual projects

Roland Backhouse

This is a list of project suggestions for the academic year 2012/2013. The suggestions are suitable for students registered on the Advanced Computer Science, Scientific Computation and Information Technology degrees. (I am not competent to supervise and/or assess projects on any of the other MSc degrees offered by the School.) 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.

Automated Assistance in the Design of WoodblocX Structures

WoodblocX is a company that manufactures lego-like wooden structures for use in the garden or playground. (One of the more complicated examples is a dinosaur-like sandpit.) The company uses auto-cad to help with the design process but further automation is desirable. In the academic years 2011-12 and 2012-13, I have supervised undergraduate projects with the support and cooperation of the company. This project would take that work further. Because the project may involve direct contact with the company, the criteria for selection are very high: only students with demonstrably excellent programming skills will be considered. Experience with auto-cad is not a prerequisite but it will be necessary to learn how to use and extend the software. A possible project is a pilot study of how to automate the process of turning rough sketches of garden structures into a complete design of a WoodblocX structure.

The General Torch Problem

This paper, written jointly with Hai Truong (a former MSc student), presents dynamic-programming and integer-programming solutions to a generalisation of a well-known "flashlight"/"bridge"/"torch" problem. The dynamic-programming solution has quadratic complexity. My current interest in the problem is to develop algorithms that construct difficult or unexpected instances of the problem that could be of interest in an online competition.

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).

First-past-the-post Games

"First-past-the-post" games are combinatorial games where the winner is the person who predicts the event (in a collection of events) that occurs first. An example is the so-called Penney-Ante game: players each choose a sequence of heads/tails and the one whose chosen sequence is thrown first wins. When there are just two players, it is well-known how the second player can optimise their choice of sequence knowing the choice made by the first player. A possible project is to explore how to choose sequences when there is more than one player.

DNA analysis

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

Last modified: Monday, 18th Februauary 2013