General areas:
Contact: rjb@cs.bath.ac.uk
Visualisation of large networks is hard, the difficulty of plotting them on a screen in a way that is visually comprehensible. Spring-based approaches (where nodes in a network are imagined connected by springs, and we move the nodes to minimise the energy of the system) have been successful. This project is to choose and implement such an algorithm. It should allow the user to drag nodes around and re-compute layout from the new configuration.
Pre-requisite knowledge: Programming skills
Indicative reading: http://citeseer.nj.nec.com/behzadi99improved.html
Another way of laying out networks that has been suggested is to map them into a high-dimensional space and then project the high dimensional space into 2D by judicious choice of eigenvectors of a certain matrix. The project is to implement such an algorithm (possibly using MATLAB) and determine how good it is.
Pre-requisite knowledge: Programming skills
Indicative reading: "Graph Drawing by High-Dimensional Embedding" D Harel and Y Koren, Proc. 10th Int. Symp. on Graph Drawing (GD'02), pp. 207-219, 2002. Available here
MHEG is a language that is use to control the interchange and display of multimedia data. In particular, it is used in Digital Terrestrial Television to diplay subtitles, teletext and other "interactive" features. This project is to implement (some part of) the MHEG language and demonstrate examples of its use.
Pre-requisite knowledge: Programming skills
Rijndael is a new standard encryption algorithm (the Advanced Encryption Standard, AES). It is a straightforward (but not simple) algorithm that takes a block of data, performs various manipulations on it, and outputs the encrypted version. This project is to develop several versions of Rijndael for use in different circumstances. This would at least include: a fast C version for general use; a Java version for use in applets; a JavaScript version for use with web pages; a Perl version for scripting use. Each version would be proved by a simple application that uses the code, e.g., a file encryption program using the C code.
Pre-requisite knowledge: Programming skills, a little mathematics to understand Rijndael.
Indicative reading: http://csrc.nist.gov/CryptoToolkit/aes/rijndael/ http://csrc.nist.gov/encryption/aes/ http://csrc.nist.gov/CryptoToolkit/aes/aesfact.html" Java books, JavaScript books, etc.
Rijndael is a new standard encryption algorithm (the Advanced Encryption Standard, AES). It is a straightforward (but not simple) algorithm that takes a block of data, performs various manipulations on it, and outputs the encrypted version. There are several different ways to implement Rijndael depending on the processor and memory configuration of the machine you want to run it on. This project is to develop several implementations of Rijndael in C for use in different circumstances: this would include (at least) large, medium and small memory machines.
Pre-requisite knowledge: Programming skills, a little mathematics to understand Rijndael.
Indicative reading: http://csrc.nist.gov/CryptoToolkit/aes/rijndael/ http://csrc.nist.gov/encryption/aes/ http://csrc.nist.gov/CryptoToolkit/aes/aesfact.html"
With the advent of Internet publishing it is difficult to retain control over data like images or sound. Some people have developed watermarking techniques (hiding data in the image) to promote this control. A watermark is some data hidden in the medium in such a way that a) the watermark is not visible/audible; b) the watermark is robust is the sense that it is not easily removable by, say, changing a few pixels in the image; c) the watermark is easily readable by the copyright owner. The aim of this project is to implement a few watermarking techniques, and determine their effectiveness against a few simple attacks.
Pre-requisite knowledge: Programming skills, some mathematics will help.
Indicative reading: http://citeseer.ist.psu.edu/petitcolas98attacks.html
Discrete event simulation is useful in many areas. For example, simulation of aircraft moving in a flightspace, molecules in a chemical reaction, packets in a network. All are characterised by being modelled by objects that react to events, e.g., a plane moving to avoid another, a packet being dropped due to congestion. A relatively new way of implementing such simulations is to use Critical Channel Traversal (CCT). This project is to read, understand and implement "Scheduling Critical Channels in Conservative Parallel Discrete Event Simulation" by Xiao et al. This describes a simulation kernel, i.e., a program that performs the object and event management that can then be used in a variety of simulation programs. This will be backed up by a simple simulation that demonstrates the correctness of the implementation of CCT. You will need reasonable skills in programming to undertake this project
Indicative reading: http://citeseer.nj.nec.com/xiao99scheduling.html
Some functions are multiple valued. This is something like sqrt, which is really +sqrt and -sqrt. When plotting such a function on a graph you should see both branches of the function. When we expand our view to the Complex plane, things become much more exciting. The function sqrt(z^4-1) suddenly becomes a torus; ln(z) is an infinite spiral.
This project is to write a program that plots such functions in 3D. It should be able to take a function and display it in a comprehensible manner. Extra points for colour and rotation of viewpoints.
This project requires some familiarity with Complex numbers, and some programming skill.
Indicative reading: "Graphing Elementary Riemann Surfaces" Corless & Jeffrey
There are several radically different algorithms to factor large integers. The traditional method is the one everybody learns at school: trial division up to the square root. This is easy to perform, but get slow very quickly as the numbers get larger. When we have perhaps ten or hundreds of digits in our integers other methods are better. These include Pollard Rho and Quadratic Sieve amongst others.
This project will implement and compare at least three algorithms, and determine the ranges of numbers for which each is the best.
Pre-requisite knowledge: Programming skills. Some familiarity with maths would help.
Indicative reading: Knuth, "The Art of Computer Programming", volume 2.
Build a Lego emulator. Using a standard graphics package build a system to display Lego bricks, and allow the user to manipulate them and build models. This should be able to save and restore models; allow the user to rotate the viewing point; do collision detection of bricks; and so on.
Pre-requisite knowledge: Programming skills.
Indicative reading: A standard graphics system, such as OpenGL.
There are many techniques to achieve secrecy for a document: a) encryption, where the bits of the document are mixed and processed in a complex fashion; b) steganography, where the bits are hidden within another document, such as a picture or sound. This project is to investigate a third way: chaffing. This does not attempt to hide or mask the bits in any way, but simply mixes in random data in such a way it is hard to determine the original data. An implementation of the method should be produced, and experiments on it to determine its efficiency and convenience and so on in various environments.
Pre-requisite knowledge: Programming skills.
Indicative reading: http://theory.lcs.mit.edu/~rivest/chaffing-980701.txt http://theory.lcs.mit.edu/~rivest/chaffing-remarks.txt
Recently there has been growing interest in a method that unifies discrete and continuous systems in a single framework called "Time Scales". This project will involve writing a comprehensible introduction to Time Scales and implementing a selection of generic algorithms (probably using Maple).
Pre-requisite knowledge: Mathematics, programming skills.
Indicative reading: Stefan Hilger. "Differential and difference calculus - unified". In Nonlinear Analysis, Theory, Methods and Applications, 30, 2683-2694, 1997. Available from