Computer Science Project Suggestions 2017/18

This page is written by Matthew Huntbach, Lecturer in Computer Science at Queen Mary, University of London.

Here are some ideas for projects I could supervise, either final year BSc or MSc. I am also willing to discuss ideas students may have, but the suggestions below show the sort of thing I am interested in.

Abstract Programming Language

This is a general term for programming language based on an abstract model, that is, some sort of data structure which is manipulated by a fixed set of rules. A programming language may be completely defined by a translation to such a model. This is in contrast to conventional programming languages which are converted to machine code and so are only properly defined in terms of how the machine code works. Abstract programming languages cover functional programming languages based on the lambda calculus (examples include Lisp and Haskell), and logic programming languages based on predicate logic (the most well known example is Prolog). There are also some experimental languages based on other models. Your task is to study such a language and make an implementation of the abstract model, possibly also the converter from the language to the abstract model. Your implementation could be in a standard programming language like Java. Good programming skills and confidence with discrete structures are required for a project in this topic, though allowances will be made for the fact that most students in Computer Science at Queen Mary won't have had any formal tuition in programming language theory.

Algorithmic Program Debugging and Synthesis

A method consists of some code structure in which method calls may occur. For any arguments to a method, there will be an expected return value. Suppose you have a method which for some arguments gives the wrong return value. If you execute the method with these arguments and make a record of the arguments to each method call it makes and its return value, you will find either at least one of these method calls has the wrong return value for its argument, or they all give the correct return value for their argument. If they all give the correct return value, the error must occur in the code for the initial method. If one of the method calls gives a wrong return value, then there must be an error in its code or in the code of a method it calls, so you could apply the same technique to locate it until you find the actual faulty method. This is the basis of algorithmic program debugging, a systematic way of debugging code by asking the developer queries about expected return values given arguments to method. Automatic program synthesis takes this further by making modifications to the code of the method identified as faulty and seeing if this produces code which works correctly for all examples given so far. This technique was developed within the context of Prolog programming, so if you have done some Prolog there is existing work you can build on. A more difficult task would be to apply it to another programming language. This is a challenging project!

Two-player Board Games

There is a well-known technique, the alpha-beta algorithm, for getting computers to work out a good next move in a game like chess, that is one with a fixed board and pieces, fixed set of rules, no random elements, two players take it in turn to use a rule to move a piece on the board, and each player can see all of the board and pieces. An essential part of this project would be to understand this algorithm and implement it for some game. There are then various ways of extending this to make a worthwhile project. You could concentrate on building a good interface to make a system where humans play against the computer. You could consider making it a distributed implementation, so a player could interact with the computer player over a network connection. You could investigate variations of the alpha-beta algorithm to see which gives the best computer play. This is a common Computer Science project, but good marks could be obtained by finding some element of originality you can add to it.

Please note, "computer games" of a sort which involve graphics and human players interacting in real time are a completely different sort of thing to this, and I have no particular interest or specialist skills in that area.

Artificial Life

This is another side to artificial intelligence, taking a different approach to the logic and search based techniques of traditional artificial intelligence, of which games-playing programs like that described in the previous section are a good example. With artificial life, there is no central controller. Instead independent agents each work according to their own rules, and interact with each other. One way in which this is used is to simulate the behaviour of a community of simple animals, such as ants. The idea is to try and find rules which result in behaviour similar to that observed in nature. Another way of using this idea is as a problem-solving technique. There has been a lot of work done in this area, so there are a wide range of topics you could pick from it and try to develop. I don't have any direct suggestion for projects in this area, so it would be up to you to look at the literature and find something you think you can work on and which would make a worthwhile project.

Computers and Politics

In both these cases, a good project would involve not only a fair amount of software development, but also the ability to look beyond the technology and consider human needs and the impact the technology could have on them.

Election Campaign Manager

This is a practical database with interface project: there are existing systems which do this job, and a good potential niche market for anyone who could build a better one. Such a system would keep the records gained from knocking on doors and asking for votes, and produce reports enabling campaign activists to distribute literature and do election-day door-knocking with maximum effect.

Thomas Hare's Electoral System

Divide the number of seats in Parliament by the number of electors in the country to get a figure, the "quota" Q. Anyone who wants to stand for Parliament and can get Q people to agree to support him or her gets elected. Thomas Hare proposed this idea in the 19th century, but practical considerations meant it was never used in this pure form. The "Single Transferrable Vote" system is an attempt to adapt it to paper based voting with voter secrecy maintained. Could we use computer technology to build something closer to Hare's ideal in the 21st century? Remember, maintaining confidentiality and security is vital in using computers to record and count votes in public elections. This project is more experimental than the previous one, to do it well would require a lot of research and original thinking.

Matthew Huntbach
Last modified: 26 April 2017