Steve Vickers: Student projects

{Here are my project orientation lecture slides on "Writing good dissertations".)

Student projects with Steve Vickers

My serious research is very much pure mathematics, exploring the relationship between logic, algebra and topology (the study of continuity). Computer science has had a big impact on how we understand the mathematics itself, particularly in logic: the logical question "Is this true or false?" gets deeper when you add, "And how do we compute that?" As a result, we end up changing the logical rules in interesting ways to make them match computation better.

I'm also run a research project on how those logical issues relate to the foundations of quantum physics (and I also used to teach the module Quantum Computing and Cryptography).

If you are interested in my research in more detail, look on my home page.

If you have some mathematical ideas of your own that you'd like to develop in a project, the chances are I can help you.

A common element of projects with me is software for interactive demonstrations, typically as a potential teaching aid for some curriculum topic - along the lines of my turtle graphics for simple algorithm structure, or my FSA applet for finite state automata. Even for a project that could in principle be dissertation-only in mathematics, interactive software can make it much richer and can help your own understanding of the topic.

Here are a variety of possible projects that range from the very concrete, through more theoretical issues of computer science, to the mathematical. They all require programs to be written. Several require good GUI and Model-View-Controller architecture.

Interactive quantum computing

Quantum computing relies at the algorithmic level on weird features of quantum physics. There is already a considerable body of theory about how it would work, with striking applications such as an efficient algorithm to break RSA encryption. You can see more on the webpage for our old module Quantum Computing and Cryptography, which I used to teach.

Unfortunately, there are no quantum computers at present beyond the trivial, though there is great scientific activity in the area and there is already some success in implementing quantum communications protocols.

The aim of this project is to simulate quantum computers on classical ones. This is not in order to do quantum computations on classical computers -- it is impossible to do this efficiently, which is why people are so keen to build actual quantum computers. Rather, it is to illustrate the principles and so an important part of the project is to have a good interactive graphical interface so the user can experiment with quantum algorithmic ideas.

If you do this project well you will have gained --

  • some familiarity with the principles of quantum computation
  • good skills in interactive GUI and Model-View-Controller architecture
  • good insight into how such an interactive simulation might be useful

One possible application I would be very pleased with is if I could use it in my Quantum Computing lectures. You can see a slightly crude example in my applet to illustrate Quantum Fourier Transform (which is used in the algorithm to break RSA).

Interactive teaching aids

Some years ago I supervised a project "Animated Simple Kernel" that illustrated the way processes change state (running, ready, suspended or sleeping) in a simple operating system. It was interactive, and showed the various queues with buttons for interrupts, semaphore operations and sleep commands. It was one of my favourite projects and was really useful in lectures because it let me demonstrate things that otherwise were quite difficult.

I am always looking for similar good ideas for student projects. All suggestions gratefully received. One idea is the next one, "Interactive mathematics".

Interactive mathematics

This project is about creating an interactive application that allows you to explore some mathematical idea. It could be almost any area of mathematics, ranging from calculus to computer science, but some of the best examples are in geometry.

Look on Alexander Bogomolny's website and you will find a wonderful collection of Java applets designed to illustrate geometric theorems - one of my favourites is Pappus's theorem. They are interactive, so you have a chance to play with them by dragging with the mouse and seeing how the geometry is preserved as you modify the configuration. One useful feature is to display data from the diagram - e.g. lengths or angles, so for instance in Pythagorus's theorem the program can display the hypotenuse squared and the sum of the other two squares, so as you modify the triangle you might see those two values remaining equal.

This project is about making similar programs. There are various directions the project could go in; here are some possibilities.

  1. User-defined configurations: Design a system that allows you to specify a configuration (various points, lines, circles etc.) with contraints (lines perpendicular, line tangent to a circle, point on a line, etc.). To do this in complete generality is a tough challenge.
  2. Write a package for demonstrating conic sections (ellipses, parabolas, hyperbolas), perhaps even demonstrating Pascal's theorem on one.
  3. Write a package for demonstrating spherical geometry - calculating lengths and areas on a sphere.

Model-View-Controller architecture is needed here. Often you need different views on a quite simple model. For example, in Pythagorus's theorem the model could be just the coordinates of three vertices of a right-angled triangle. One view might be a simple display of that triangle, another might have some extra points and lines drawn in to show some stage of a proof, and another view might just be numeric data - side lengths, their squares etc.

p-adic Calculator

Try to imagine a computer in which the words are not restricted in size but have infinitely many bits: so for integer arithmetic, there is never any overflow because the carry can always be accommodated in a higher order bit in the infinite word. Then you have all the integers, both positive (almost all the bits are 0) and negative (almost all the bits are 1, using 2s complement).  But you also have new numbers in which there is a mixture of 0 and 1 bits going all the way to infinity. These are called the "2-adic integers".

You can do the same with any number base p instead of 2, and get the p-adic integers. They are used in some branches of mathematics, for instance in number theory (that is, the theory of ordinary numbers).

The project is to develop a p-adic calculator that manipulates streams of digits as representing p-adic integers.

As part of it, there are some interesting p-adic algorithms that rely on working with a digit even before you know what it is - this is for functions that are able to give more digits of output than the available number of input digits. To implement this, the calculator's operations must include not only ordinary arithmetic (+, -, * etc.) but also a non-deterministic "anticipation" operation.

Proof assistants

A "proof assistant" means some software to help write and check proofs in formal logic, such as the natural deduction proofs you may remember from your first year.

I am particularly interested in proof assistants for some logics that enter into my theoretical research:

  • coherent logic
  • quasi-equational logic

Both these work with sequents, assertions that say one formula implies another. The logical rules say how, if you have already managed to prove that certain sequents are valid, then others will follow.

In coherent logic, the formulae in the sequents are very restricted. The only logical connectives allowed are "and", "or", "=" and "there exists". This sounds too simple to be of much use, but in fact it turns out to be related to topology and computing.

It has a generalization, geometric logic, in which the "ors" are allowed to combine infinitely many formulae. That would obviously cause problems in a finite computer, but an extension to the project on coherent logic would be to look at ways of getting the infinities in.

In quasi-equational logic, the formulae are even simpler: they just use "and" and "=", and there are no predicate symbols - just functions. But there is a catch - the function symbols are allowed to be sometimes undefined.

This logic is extremely useful in algebra.

Notes on Model-View-Controller (MVC) architecture

In many of these proposals you will need to acquire a good understanding of how to write interactive graphics packages using model-view-controller architecture. This is because the projects explore different GUI ideas, different ways of manipulating objects by interactions with the screen. You therefore need a very clear idea of the underlying "thing you are manipulating". This is the model and needs to be kept as simple as possible. The view and controller are how it is displayed on the screeen and how you can interact with it.

I can supply notes to describe these ideas in more detail.