Programming Project Topics

Below are some suggestions of mine; you are welcome to come up with your own as well, but in any case, these are a starting point, and the development of a topic is an interactive process between the supervisor/s and the student. The main issue is to come up with a project which can be done in one semester, and so the scoping of the project is quite important. A programming project for an M.App.Sci(IT) project does not have to aim for publishable research, but involves the development of some novel or interesting application (such as a tool for a research project). Some of these topics are also suitable for summer projects, or just for investigaion as and when you feel like it.

At IJCAI in August 2005, I heard about the amazing progress that has occurred recently in solvers for the 3SAT problem, which can now solve problems with around 1,000,000 variables in them. This is large enough to cope with many realistic large problems. It then suggests that one way to solve your favourite NP-complete problem is to use such a SAT solver (many of which are available as open source) as the base engine and to use polynomial reductions from say the travelling salesman or vertex cover problem to 3SAT as the basis of an implementation. The aim of this project is to determine how feasible this approach is by means of a series of experiments.