Computer Science at Oxford

From Computer Science at Oxford

Second year students carry out a group programming project in the third term, giving them the opportunity to experience working collaboratively in a team to produce a working software prototype. Participation is required as part of the degree, but we do not assess the results in a way that contributes to exam results. Our students enjoy presenting their results at the end of the project, with a chance to win one of several industry-sponsored prizes.

Students in the third year of the Computer Science degree spend 25% of their time on a project, usually involving the creation of a bigger computer program than they have worked with in laboratory exercises. In the fourth year, students do a more substantial project (50% of their time), often more oriented towards the research interests of a member of staff.

Mathematics and Computer Science students who elect to stay on for a fourth year are also offered the option of doing a project, occupying 25% of their time in the fourth year.

Each year, the Department publishes a list of projects that members of staff have agreed to supervise, but students are also encouraged to propose their own projects. Here is a small sample of projects from the current list:

Robot Path Planning

A robot cannot find its way by looking at a map designed for humans; rather, it must make a complex series of geometric calculations. Many algorithms have been developed for robot path planning, and the purpose of this project is to investigate (and improve upon) some of these. The `robot' might be an arbitrary convex polygon that can slide in a world composed of polygonal obstacles; an industrial robot arm; or a human trying to find their way across a strange city.

Which algorithms you investigate is largely up to you: they range from pragmatic, `suck-it-and-see' methods to mathematically-complicated methods that are guaranteed to succeed (after a lot of CPU time!). There is also considerable scope to think of novel robots. For example, previous students have considered: a planetary exploration vehicle; a smart torpedo; and a model railway track.

Stephen Cameron

Decompilation

Java and C# are compiled to high-level intermediate code, and programs are distributed in that form. In fact, the intermediate code is so high-level that it is usually possible to reconstruct the original program (or something similar); this process is known as decompilation. In the course of research at Oxford, we have developed a rudimentary decompiler that produces something approaching C# code from the .NET intermediate language. The Soot framework already provides a decompiler from Java byte code to Java source.

The purpose of this project is to explore various alternatives for future work along these lines. For example:

• Extend our rudimentary decompiler to produce valid C# and apply rewrites to make it easy to read
• Investigate decompiling .NET IL to other languages; for example, Java

Oege de Moor

Case studies with CSP and FDR

The aim of this project is to model some distributed algorithms or protocols using the process algebra CSP, and then to analyse them using the model checker FDR, both of which were developed as a result of research at Oxford. The choice of algorithms to analyse would be up to the student, but here are some possibilities:

• the Session Initiation Protocol (SIP), a signalling protocol for Internet telephony;
• common communication protocols such as those in the ISO OSI or TCP/IP models, or the i-Protocol;
• asynchronous hardware;
• feature interaction;

Gavin Lowe

Garbage collection for OBC

Traditionally, PASCAL-like languages have pointers and dynamically-allocated storage, but they do not have a garbage collector. This makes programming with pointers unnecessarily difficult, because each program must keep careful track of all the storage that has been allocated, in order that it can be released later. Oberon breaks this mould by requiring that heap-allocated storage be garbage collected.

At present, the Oberon compiler that we use to teach programming (and also study in the Compilers course) uses a 'conservative' garbage collector that knows nothing about the type structure of the Oberon program that is running. The aim of this project is to make a better garbage collector that knows how the heap is laid out, and to extend the Oberon compiler to output the information that this garbage collector needs. A first implementation could operate entirely at the level of the byte-code machine; if this goes smoothly, a later extension might add pointers and garbage collection for native code.

Michael Spivey

A Family of Modeless Structure Editors

The article 'Modeless Structure Editing' (in Millennial Perspectives in Computer Science: Eds. Davies, Roscoe, and Woodcock. Palgrave, 2000) outlines the design of a family of modeless structure editors – the outline takes the form of a Haskell program, and this was the basis for a prototype implementation in Haskell. The goal of this project is to build an efficient, customizable, implementation of the family in Java or OCAML.

Bernard Sufrin