Project topics for the MSc in Advanced Computer Science

This page provides some suggestions for mini-project and project topics for the MSc in Advanced Computer Science that I would be interested in supervising. If you are interested in one of them, please email me for discussing it further. It helps if you have already found out a little more about the topic. Searching for some of the keywords mentioned on Google Scholar may be a good starting point. One of the best features of the MSc in Advanced Computer Science is the freedom it gives you in pursuing interesting questions. There are different possibilities for what can be done about a given topic, for example, a literature survey, a case study implementation, experiments, or a dissertation-only project without coding.

See also the projects for the MSc in Computer Security, as they are also suitable for (mini)-projects in the MSc in Advanced Computer Science. (But not conversely). For the MSc in Advanced Computer Science, a mini-project based on one of the security topics could consist of a literature review and an initial feasibility study (with a full implementation as a possible summer project).

Some of the MSc projects could also be a first step towards a PhD; see also my list of possible PhD topics in Computer Science.

Static analysis for regular expression denial-of-servive attacks

RXXR is a static analysis tool that detects whether regular expressions are vulnerable to redos attacks, which can cause Java to hang. This project extends the analysis to cover a broader class of regular expressions than currently supported by the tool and to make it more user-friendly. Porting RXXR to Scala will produce a stand-alone application in Java bytecode, making the analysis easier to use for Java developers.
For more details, see the RXXR page.
This project is suitable for: MSc Computer Security, undergraduate CS, MSc Advanced Computer Science

Latex to ibook translator

NB: while this would be a very useful tool to build, I have not looked into its feasibility, involving a propriety format. Academics often write lecture notes in latex, which produces great PDFs for printing or viewing on a desktop. But at the moment there is no good tool to translate whole Latex documents to an electronic book format suitable for handheld devices.

ANTLR and left recursion

This project builds a program transformation of ANTLR programs to make them suitable for parsing. The theoretical basis is my paper in PPDP'12 (see my publications page).
This project is suitable for: undergraduate CS, MSc Advanced Computer Science

Regular expression matching and parsing

Regular expressions (and their extensions) are everywhere, yet their implementation in Java is not anywhere as efficient as it could be. Projects in this area will leverage the large number of cores on a GPU (Graphics Processor) to match regular expressions in parallel. These techniques may also be extensible to parsing, such as XML parsing.

Programming in ML or Scala

ML is an advanced programming languages, and there are several dialects of ML with efficient implementations, such as OCAML and F Sharp. I am interested in projects that use ML. Note that many of the features of ML-style languages are covered in the final-year optional module on Principles of Programming Languages.

Push versus pull parsing

In the context of XML parsing in Java, there are two contrasting approaches to the interaction between the parser and the rest of the Java program: push technology uses method callbacks, whereas pull uses streams. The aim of this project is to analyse this distinction in a wider computer science context (there may be connections to continuations and streams in functional programming, or the Visitor Pattern in Object-oriented design).

Software engineering and web design

Web pages have links between them. That is analogous to data structures with pointers. They tend to be updated by different people, often with disregard for incoming links or consistency. That is analogous to concurrent processes updating data structures with pointers, and the problem of maintaining data structure invariants. So the question here is: can concurrent programming shed some light on how to design a web site and how it evolves?

Recursive-ascent parsing

Top-down, or recursive descent, parsers can be written in a pleasantly direct style as a collection of mutually recursive methods in Java. By contrast, bottom-up parsers (like those generated by yacc/bison) are typically table-driven. Recursive ascent generates methods for a bottom-up parser. The project would explore writing such parsers in Java.

Visitor-oriented programming

The visitor pattern is an object-oriented design pattern for traversing data structures, such as the parse trees described in the parsing part of the SSC1 module.

Aspect-oriented programming

Aspect weaving can potentially change the behaviour of the original code beyond what may have been intended. How can reasoning about methods in terms of pre- and postconditions be adapted to aspect-oriented programming?