If you want to do a project in one of the following areas, I would be glad to supervise it. If you have some of your own ideas, particularly in a mathematical area, then talk to me and we'll see if its OK.

Mostly these ideas are suitable for mathematical investigation. These are particularly suitable for MEng Mathematical Computation students. Key point: YOU choose your own project (provided someone agrees to supervise it).

## Relation Algebra

A relation algebra is a bit like a boolean algebra but it has extra operators designed to handle binary relations. A relation algebra comes with a constant called the *identity* (standing for the equality relation), a unary operator called *converse* (that reverses a binary relation) and a binary operator called *composition.* A relation algebra is defined by a set of about 8 axioms. Although every boolean algebra can be represented as a field of sets, not every relation algebra can be represented as a field of binary relations. Possible projects in this area include the following.

- Design a program that generates all possible relation algebras of a given size.
- Design a program that tries to test whether a relation algebra is representable (in fact this is undecidable, in general).
- Design a program that tests whether a relation algebra has a finite representation (it is not known whether this problem is decidable or not).
- Consider algebras over the signature with identity, <= and * only. A finite algebra A (with an identity element, an associative * operator and a partial order) is representable if it is isomorphic to a set of binary relations where the identity is the equality relation, <= is inclusion of sets and * is composition of binary relations. Note that the base set for the binary relations might be infinite. Write a program to generate structures of this type and test whether they can be represented over finite base sets.
- Design an efficient program that tests whether a given set of constraints over a given relation algebra can be satisfied by points in a representation (see www.cs.ucl.ac.uk/fileadmin/UCL-CS/staff/Robin_Hirsch/Papers/matteo.pdf).
- There is a mistake in Lemma 15 of www.cs.ucl.ac.uk/fileadmin/UCL-CS/staff/Robin_Hirsch/Papers/matteo.pdf Write a program to construct a set of constraints over this algebra, where every triangle is consistent but there is no global solution, or prove that this cannot happen.
- Write a program to find the smallest possible relation algebra that is weakly representable but not actually representable (the smallest known has 7 atoms, but smaller ones might exist).

Consider the following signature for algebras of binary relations: an ordering <= to denote that one binary relation is included in another, a converse operator that returns the converse of a binary relation, a composition operator that returns the composition of two binary relations and an identity constant. A representation of an algebra in this signature is an isomorphism to a set of genuine binary relations over some base, where all the operators have their natural meaning. We do not know whether a finite representable algebra necessarily has a representation over a finite base set. This needs investigating. You might want to implement a program that searches for finite representations for given algebras.

## Graph Theory

Various projects are possible here.

0. The *spectrum *of a graph is the multiset of eigenvalues of the adjacency matrix (see https://en.wikipedia.org/wiki/Spectral_graph_theory). In many (but not all) cases the spectrum of a graph determines the graph uniquely, up to isomorphism. It is not known whether the spectrum determines the graph for ALMOST ALL graphs. In this project you implement an isomorphism checker (preferably a fairly efficient one) and investigate whether the spectrum determines the graph.

1. Consider the following two-player, "forth game" \Gamma(G, H) played over two directed graphs G, H. Each player has two colours: red and blue. In the initial round the first player (A) picks a set of nodes of G and colours them red, the second player (E) picks a set of nodes from H and colours them red. The next round is similar: A picks another set of nodes of G and colours them blue, E does the same in H. In subsequent rounds, A picks a set of nodes of G and a colour (red or blue) and resets the nodes of that colour to the chosen set, E does the same in H. The game goes on, possibly forever.

At each stage, the two colours partition the nodes of G into four parts: not coloured, red but not blue, blue but not red, and both red and blue; the nodes of H are similarly partitioned into four. If at any stage one of these four parts is empty in G but non-empty in H, or the other way round, then A wins and the game is over. Also, if there are two of the four parts with an edge connecting some node in the first part to a node in the second part, but no edge between the corresponding parts of H, or the other way round, then again A wins and the game is over.

If A does not win at any finite stage then E is the winner.

The problem is to find two finite non-isomorphic graphs G, H that cannot be distinguished by this game, i.e. E has a winning strategy in \Gamma(G, H) and also a winning strategy in \Gamma(H, G).

The project might involve writing a computer program to construct suitable graphs and test them to see if they solve the problem.

2. A third problem is to give bounds to the so-called Ramsey numbers (see http://en.wikipedia.org/wiki/Ramsey_theory ). There are lots of problems to do with the 0-1 laws and random graphs (ask me for more details).

3. Solve the 17x17 grid colouring problem (and win a prize of £289) http://blog.computationalcomplexity.org/2009/11/17x17-challenge-worth-28900-this-is-not.html

**Definition:** The n x m grid is *c-colorable* if there is a way to c-color the vertices of the n x m grid so that there is no rectangle with all four corners the same color.

4. The following problem would help us understand the relation between the complexity classes P and NP.

Write a program that constructs a graph G with the following properties. (i) G is partitioned into n sets V_0, V_1, ..., V_{n-1} each with three nodes. (ii) For each i<n there are no edges within V_i. (iii) There is no clique of G with n nodes (a clique is a set of nodes where all edges between these nodes are edges of G). (iv) The following algorithm produces a non-empty list of triangles (a triangle is a clique of 3 nodes)

Make a list H of all triangles of G;

While (H changes)

For each triangle T in H, for each i<n if there is no vertex v\in V_i such that every triangle from T \cup {v} belongs to H then delete T from H;

End While

Return (H);

## Clustering Problem

Let G be an undirected graph. A k-clustering S_0, S_1, ..., S_{k-1} is a partition of the set of nodes of G into k disjoint sets. A positive error in a k-clustering is a pair of nodes in different clusters connected by an edge, a negative errors is a pair of nodes in the same cluster not connected by an edge. The total error of a k-clustering is the number of positive and negative errors. We aim to minimise the total error. There are two optimisation problems to consider. First, let k be fixed and find the optimal k-clustering for G. Second consider the general optimization problem where k is not fixed and you have to choose k and a k-clustering so as to minimise the total error.

Based on the MinCut theorem, I would conjecture that the 2 clustering problem can be solved in polynomial time. I conjecture that for fixed ki>2 the optimization problem is NP-complete, also that the general optimization problem is NP-complete. You might attempt to prove some of these conjectures. Also, you might construct algorithms that find near optimal clusterings.

## Cannibals

Have a look at this paper about a game called Cannibals. Implement this game and consider playing the game over other graphs (not necessarily just a grid as in the paper). Try to work out good intelligent strategies for such games.

## Music Harmoniser

Design and implement a program to create harmonies for a tune. Various projects could be possible. Design "fugue completers" to automatically compute a four part fugue.

## Temporal Reasoning and Games

Consider a set of temporal constraints between intervals of time. So, for example, if I, J, K represent intervals of time, we might be told that I is properly contained in J (it starts after J starts and it ends before J ends), J is either strictly before K or strictly after K and I either meets K (the end of I is the start of J) or it equals K. We want to know whether these constraints have a solution: is there a way of giving I, J, K definite intervals of time so that the constraints are satisfied?

Conventional algorithms for this are not complete: they sometimes miss inconsistencies in a set of constraints and return "yes" when the answer should be "no". For this project you need to study how a two player game is capable of detecting inconsistencies and implementing this as a computer algorithm.

## Temporal Databases

Consider a database that changes over time. How do we handle temporal changes? Logical aspects: what language is best to describe this? First-order logic, with one time variable (c.f. Kowalski's event calculus); a temporal language with temporal operators (e.g. F - future and P - past); in a non-monotonic framework?

## Planning

Design your own artificial planner. Example: the blocks world. Given blocks stacked on a table the problem is to move them (probably one at a time) till they are in the correct position. Only your program has to work it out for itself. Possibility of exploring mathematical aspects e.g. you can use a temporal reasoning system based on intervals of time to do this.

## Genetic Algorithms/Programming

Genetic algorithms evolve solutions to problems, but the solutions need not a plain data. If the solution is in fact a code that represents a strategy for some game, then a genetic algorithm could be used to evolve knowledge of how to play the game. This is a very interesting idea and one that has, to date, not been investigated very much. The main problem is how to find simple and correct ways to encode the idea of a strategy as data that can be combined by the genetic algorithm. You may have some ideas about this yourself. At each "iteration" all the current solutions would play each other to determine how good they were. The best would breed to produce, you hope, at least some that are even better. Of course what solutions evolve as good depends on what the existing competition is like and it may be necessary to "salt" the population with known good strategies to get started. I feel sure that the game would have to be a very simple one like noughts and crosses (also called tick-tac-toe) and you would need a lot of imagination to take this project on (and some luck) but I think it could be fascinating. Also, try to use GP for simple two-player games which are not zero sum. The most famous of these is the prisoners dilemma, but there are various others. Try three-player games and n-player games which involve co-operation as well as competition between players.

## Genetic Algorithms and Intractability.

Most interesting computer science problems are intractable and may even be undecidable. For the latter there can be no correct algorithmic solution and for the former we know that any solution cannot run in p-time. Nevertheless we may be able to find probabilistic solutions, i.e. algorithms that are not always correct but have a high probability of being correct. One approach of this type is by using genetic algorithms to find probabilistic solutions to intractable problems. A good example of an intractable problem is PSAT. Examples of undecidable problems are tiling problems and the satisfiability problem for first-order logic. The following links include databases of formulas to test your programs on

http://www.intellektik.informatik.tu-darmstadt.de/SATLIB/benchm.html

ftp://dimacs.rutgers.edu/pub/challenge/satisfiability/benchmarks/cnf/

http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/benchmarks.htm

http://www.satlive.org/bytype.jsp?reftypefrom=-3 [thanks to Marcin Sadowski for these links].

## Higher dimensional geometry kit

Graphic displays for simple 4 dimensional shapes.

## Logic theorem prover

Implement a theorem prover for first-order logic, or for various modal and temporal logics. Could use the tableau method. Investigate formulas such that the tableau method will terminate, i.e. find a set of first-order formulas which are *decidable*.

## Non-linear dynamics and fractal geometry

Investigate chaotic behaviour of iterative systems. Construct some fractal pictures. Consider the outcome of iterating different, non-linear functions. Study Julia sets, strange attractors etc.

## Combinatorics

Lots of problems here. See http://www.math.uiuc.edu/~west/openp/ for example.