Project Ideas

Hi, welcome to my project page! Here, you will find various ideas for graduate projects which I think are interesting and would be happy to supervise this year. Broadly, they fall into two (quite different) areas: Programming Languages and Graph Algorithms. So, have a look and see if anything catches your eye. If you have any questions or want to discuss the projects in more detail, feel free to come by my office (CO231) or email me. I am also open to other suggestions for projects relating to my areas of interest. Finally, you can find more information on my homepage about my work.

Finding Bugs in Java

Have you ever wondered whether bugs in your programs could be found more systematically and automatically? The Java Modeling Language (JML) provides a way to annotate Java code with expected behaviours like pre- and postconditions, invariants, and assertions. These annotations can then be used to check whether the code behaves as expected. The aim of this project is to extend the JKit compiler, developed here at VUW, to automatically convert JML annotations into runtime checks. In this way, bugs in Java programs can be identified more easily through testing and execution.

Java Query Language (JQL)

JQL is an extension for Java developed at VUW that provides support for querying collections of objects. Queries provide a powerful abstraction for dealing with sets of objects, allowing the query engine to take care of the implementation details. This allows for shorter, clearer code, and permits the query engine to dynamically optimize query evaluation strategies as the runtime context changes. The aim of this project is to further improve the kinds of queries that can be expressed in JQL. For more information on JQL, see my papers [1][2] and also the JQL homepage.

Understanding Loops in Java

A typical loop, such as a for- or while-loop, found in a Java program has a very simple structure. Usually, it will iterate over some collection, performing some action on each element. In many cases, it will use a condition to filter down the objects of the collection being operated on. Our previous empirical studies have demonstrated that the vast majority of program loops fall into these two categories. However, these studies were conducted on fairly small benchmarks and we would like to repeat the study on larger, real-world benchmarks. In order to this, we require a tool for automatically analysing the loops found in Java programs. This tool will be built on top of the JKit compiler developed here at VUW, which provides all the facilities for parsing and analysing Java programs.

Optimising Java Programs with Functions

Java compilers cannot aggressively optimise the use of methods in Java programs, because such methods may have unknown side-effects. In practice, however, many methods do not actually have side-effects. Therefore, it would nice to optimise the use of these methods in order to improve the performance of Java programs. Thus, this project is about annotating methods as being "functional" (i.e. having no side-effects) and developing a compiler mechanism for optimising their usage in Java programs. In principle, this should lead to a significant performance improvement in Java programs. This will be implemented within the JKit compiler developed here at VUW, which is a full Java compiler designed for extensibility.

Profiling Collections in Java

DJProf is a profiler for Java programs written in AspectJ. DJProf can report various kinds of information, such as which functions are executed the most and/or consume the most heap storage. The aim of this project is to extend DJProf to monitor the usage of Java Collections classes. Different collection implementations (e.g. ArrayList versus LinkedList) have different performance characteristics (e.g. ArrayList gives quick random access, but slow insert). My hypothesis is that programmers often make poor choices regarding which collection implementation to use. The aim of this project is to test this hypothesis by, firstly, extending DJProf to monitor the necessary information and, secondly, by profiling a large selection of real-world Java programs. For more information on DJProf see my paper [1] and visit the DJProf homepage.

Dynamic Topological Sort

The problem of topologically sorting a directed graph is about arranging its nodes so that all edges go in the same direction. For example, consider the following directed graph:

A topological sort of this graph is:

There are often many possible solutions for a given graph and we are simply interested in obtaining one of them. This is a well-known problem and optimal algorithms are known which need O(v+e) time, where v is the number of nodes and e the number of edges.

A variation on this, called the Dynamic Topological Sort (DTS) problem, is that of updating the topological sort after a new edge is added to the graph. For example, consider adding an edge from A to C in our sorted graph above. In this case, we need only swap the positions of A and C to update the sort. Here, the difficulty lies in performing the least amount of work to obtain a new topological sort. It turns out this problem has not been studied very much in the past and details of existing algorithms can be found in my recent paper (postscript / PDF).

I have developed several new DTS algorithms and there are numerous ways in which these could be improved upon. Therefore, in this project, you will explore some or all of the possible improvements I know of in an effort to obtain a better algorithm. While not strictly necessary, the project should culminate in an experimental evaluation of the new algorithm compared with the existing ones.

Note: the only real requirement for this project is a keen interest in algorithm design. Knowledge of C++ would also be useful (but not strictly necessary) for any experimental component and because my current implementations are in C++.
Background reading: see my recent paper (postscript / PDF) as well as Chapter 3 of my thesis (postscript / PDF).