This web page lists a number of topics for which I am prepared to be the supervisor. In general the topics are best suited to students who like to write programs and to experiment with them.
My 2000/2001 BSc project students are:
Many of the proposals here are illustrated by references to
articles I wrote for
EXE: Software Developer's Magazine.
These articles are copyright of Centaur Communications PLC, which have kindly
allowed me to make them available on my web page, so that you do not have to
chase up back issues of the magazine to read the articles.
The Evolutionary approach to programming is based upon the law of natural selection. Popularly known as Darwin's law of survival of the fittest , though I don't think Darwin coined this phrase himself.
The idea is to encode the solution to a problem as a sequence of genes (just numbers). Now we try to breed a good solution by mating and mutating the population of individuals. We define a fitness function, which evaluates how close each individual is to solving the problem in hand and use this measure to bias the selection of individuals when mating and killing off. As the population evolves the average fitness increases and, hopefully, we get a solution to our problem (without really knowing quite how we got it).
My interest in Evolutionary Algorithms revolves around their use in finding good ways of simplifying programs. The genes, in this case are simple program transformation steps that change a program from one form to another. Fitness is how simple the program becomes under a sequence of transformations. The project would consist of breeding simplified versions of a program using a genetic approach. Naturally, we'd make up a very very simple programming language, with only a small set of elementary transformations to experiment with. The interesting part of the project would be seeing whether we could breed simpler versions of our programs using different kinds of evolution. That is, how two individuals mate, how individuals are selected for breeding and how we apply mutation to the population's gene pool.
The nature of this project will be very experimental. It will consist of experimenting with different mating and mutation strategies and different problems to see which evolutionary strategies appear to work best.
Bryan Jones has a
good page which describes
GAs and related technologies in some detail.
With the growth of the internet, there will be a need for computer programs which assist the human in managing the enormous amounts of data they will be required to process. One way of dealing with this is to built programs, called agents, which assist in the process of managing information.
An agent might screen your e-mail or search the web for information of interest to you. I am more interested in simpler agents that simply help us to keep our own web provision up to date. There is a growing recognition that the web pages we provide will need constant maintenance and up-dating if they are to be attractive to their target audience. This project will define and build the kinds of agent that will help an organisation to manage the provision of web information. Such agents are more likely to be robots (having no intelligence) than artificially intelligent programs. For example, we could write a very simple robot program which searches a web site, downloading all pages which can be found by following links to a pre-defined depth. This is a simple way of creating a local mirror site . The ideas behind this project are described in an article I wrote for the December issue of EXE magazine.
The project will use UNIX/ Linux shell scripts and or C code to define the agents.
In particular I'm interested to
look at how agents can be attached to web pages to ensure that they remain up-to-date.
This involves less of the AI aspect of personalization, and more of the
problems associated with web maintenance and interfacing to different systems.
Such an agent would require autonomous execution and independent
decision making, but need not tailor its behaviour to suit user taste.
therefore, perhaps `robot' would be a more appropriate term, rather than agent.
Angel .html is a system for estimating properties of a project. The project might be a programming project and the estimates might be the number of people who will be required or the amount of code the project will produce. It could also be a repair job on a car and the property might be the time to fix the fault or the cost of repair.
Angel works by case analysis. The Angel system maintains a database of projects for which values of the properties of interest are known. In order to provide a cost-estimate or some similar predication for a new project, Angel attempts to find the projects in its data base which are similar to the new project.
The idea has been developed at Bournemouth University as a system to provide software development cost estimates (like those produced using COCOMO and other project estimation systems). However, the idea applies to a far wider variety of problems and these may be subject of the investigation I propose.
The Angel approach and alternatives are briefly described in
my EXEarticle on
cost estimation.
Any change in the value of a variable which occurs when an expression is evaluated is called a side-effect. Side-effects are particularly frequent in C, and have thus been inherited into C++ and to some extent into Java. Side-effects are believed to make programs harder to understand, yet programmers use them because they are also believed to improve the efficiency of a program.
It would therefore be extremely helpful to design a system which allowed us to transform the side effects out of a piece of code.
This idea described briefly in my EXE article on
program transformation.
Program Slicing is a technique for simplifying programs by deleting statements which cannot affect a given set of variables at some point in the program.
I wrote an EXE article A piece of cake on slicing, which explains the idea in a little more detail.
I worked on an algorithm for constructing slices (described in a A Parallel Algorithm for Static Program Slicing (this link is a postscript file)), which could be implemented as an object oriented program. The idea would be to compile the program to be sliced into an object oriented program which computes slices for the program. This would lead to a very fast slice-computation process and would create a cross-platform slicing tool, which could deliver tailor-made slicing programs over the web.
This is a challenging project which could lead the student on to
study for a higher degree.
I am also interested in software testing. In particular I'm interested in how we can automatically generate from a program good quality test data.,
As so much time is spent software testing, the production of good quality data is essential to the safe and reliable use of computers. unfortunately, what constitutes good quality test data and how to create it remain challenging problems.
For a beginner's introduction to the field of software testing, you
might like to look at another couple of
EXE articles on
basic and slightly more
advanced approaches to testing.