Honours Projects 2007

Projects supervised by Peter Eades

Computational Complexity for Combinatorial Design Problems
Folklore among mathematicians suggest that, in general, constructing combinatorial designs (such as Hadamard matrices, balanced incomplete block designs, finite projective planes) is computationally difficult. However, standard complexity theories (NP-completeness, Kolmogorov complexity) do not seem to apply to these problems. This project aims to define a new complexity theory in which it is possible to prove or disprove the computational difficulty of combinatorial design problems.

Assumed knowledge:
Some 3rd year Mathematics or equivalent in mathematical sophistication
Good results in Algorithms classes

Interactive integer linear programming
Difficult optimization problems are often solved by integer linear programming. However, for many real-world problems, constraints are not known a priori, and are difficult to encode. This project aims to create novel systems in which the user interacts with a running integer linear programming algorithm to input constraints on the fly. The systems should take advantage of human pattern recognition ability, and human domain knowledge. The user should detect patterns as the ILP algorithm runs, and infer new useful constraints from these patterns.

Assumed knowledge:
Some knowledge of optimization methods
Good UI design skills