Text only

CM30076 / CM30082
Individual Project

Project Ideas

Dr Russell Bradford

rjb@cs.bath.ac.uk

Tcpdump visualisation
The output from tcpdump of network traffic between two hosts is somewhat difficult to read. This project is to take such an output and produce an arrows diagram such as we see in Stevens' book. This would be annotated with (configurable amount of) information, e.g,. new connection, dup ACK, etc. There is scope to spot Nagle and other strategies.
Pre-requisite knowledge: programming skills, Networking course
Indicative reading: Stevens "TCP/IP Illustrated", a standard Unix graphics system, such as Qt or FLTK.
Crocodile Clips for Unix
Those of you who took CM10017 Architecture and Operating Systems will have used Crocodile Clips as part of the assessed coursework. This project is to produce a work-alike tool that will run under Sun Unix and/or Linux and that is aligned more closely with the requirements of the course.
Pre-requisite knowledge: Programming skills. CM10017
Indicative reading: A standard Unix graphics system, such as Qt or FLTK.
Plotter of Riemann surfaces.
When we want to graph some functions, such as sqrt(z), we have a problem: square root is multiple valued (+ and -). This is made worse when we want to visualise the function over the complex plane. This means plotting surfaces, in particular Riemann surfaces. This project is to produce a stand-alone surface plotter of such multiple valued functions. It must allow the usual rotation and zooming of images and should be able to cope with moderately complicated functions, such as sqrt(z4-1) and ln(z).
Pre-requisite knowledge: Mathematics, programming skills.
Indicative reading: http://citeseer.ist.psu.edu/corless98graphing.html
A comparison of integer factoring algorithms
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.
Implementation of Wu's Algorithm
Wu's (or Wu-Ritt, or Ritt-Wu) algorithm is a technique that takes a collection of polynomials and triangularises them. For example, {x2 + y2 - 1, x + y} becomes {x + y, 2y2 - 1}. This is then easily solvable by back substitution. In some sense, Wu is between Gaussian elimination and Groebner bases. This project is to implement Wu's algorithm in the CoCoA system.
Pre-requisite knowledge: Computer Algebra course
Indicative reading: http://cocoa.dima.unige.it/; http://www.bath.ac.uk/~masrjb/CourseNotes/Notes.bpo/c78.ps.gz, section 7.5; Google scholar -> ritt wu triangularization
Chaffing and Winnowing: Confidentiality without Encryption
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
Unifying Difference and Differential Calculi
Recently there has been growing interest in a method that unifies discrete and continuous sytems in a single framework called "Time Scales". This project will inviolve 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 WebCat E-Journals.
Spring-based Graph Layout
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 successsful. 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
Digital Watermarking (sound or picture)
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.
A Simulation Kernel
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.
Pre-requisite knowledge: You will need reasonable skills in programming to undertake this project
Indicative reading: http://citeseer.nj.nec.com/xiao99scheduling.html