CM30076 / CM30082
Dr Carsten Fuhrmann
Learning tools for computability lectures
As a final-year student, you probably remember how hard it was in the
beginning to understand Turing machines, or abacus machines, or
I am interested in learning software that makes it easier for students
understand these topics. For example, one could produce a simulator that
allows the user to enter a program for an abacus machine and then
visualizes the program execution. Or similarly for Turing machines or
Optimally, such a teaching tool should encourage students to
experiment, and thereby learn in a playful way.
Pre-requisite knowledge: good programming skills, basic knowledge of
parsing, interest in designing graphical user interfaces.
- A CASE tool for student projects
- CASE stands for ``Computer Aided Software Engineering''. Software
engineering involves various activities: specification, design,
implementation, validation, evolution; depending on the nature of the
software project, these activities are arranged in some SOFTWARE
PROCESS MODEL, for example, the ``waterfall model'' or ``evolutionary
development''. Along the way, documents are produced: requirement
analysis and specification, description of the design, user and system
documentation etc. A CASE tool helps the software engineer to organize
and carry out the activities and produce the documents and the code.
- Typical student projects, e.g. final-year and MSc projects, are a
special kind of software project whose development follows well-known
patterns: the final document produced is a dissertation with certain
standard chapters, the deadline is known, the planning process always
involves a supervisor, and so on.
- The goal of this project is to create a CASE tool that helps students
to carry out their final-year or MSc projects, for example by
providing a facility for choosing a software process model (as
mentioned above), scheduling the activities, controlling the progress,
producing the documentation, and putting all documentation and code
together into a thesis in WORD or LaTeX.
- An editor for proof-nets
- Proof-nets are a user-friendly way to present logical proofs in
graphical form. In 2004, our MSc student Yifan Xie wrote a convincing
editor that allows the user to create and validate such proof-nets.
- However, there are still desirable features left to implement:
most importantly, the possibility to simplify proof-nets
automatically; but also an undo function, and the possibility to print
the proof-nets in publishable form.
- The goal of this project is to add some of these features, building on
the code of Yifan Xie. (The code is in good shape.)
- Pre-requisite knowledge: a student undertaking this project should
have enjoyed the more mathematical courses offered in computer science
and - in particular, `COMP0019: Computation III: Introduction to
Formal Logic and Semantics' - and should be planning to take 'CM30071:
Application of Logic'. The project also requires good programming
skills, basic knowledge of parsing, and an interest in the design of
- An email client with hierarchical views
- This project is about improving email clients by `views'. A `view' in
an email client is a criterion for selecting the visible messages (see
e.g. 'views' in Outlook, Mozilla, 'searches' in Kmail, or 'virtual
folders' in Ximian Evolution). Ideally, view is the same as a search
which has been stored for re-use. Views are a very useful, because
they eliminate the users' need to sort messages into folders. In
particular, this eliminates the danger of mis-filing messages. (This
is also the philosophy behind Google's GMail - "search, don't sort".)
- Many email clients do not support views, but even those that do suffer
from the problem that new views cannot be built from existing ones.
- The goal of this project is to build a graphical email client that
allows the user to not only create views like "sender is John", but
also build views from other views by using logical connectives like
"and", "or", "not". For example, consider the following definitions of
- Person X = (sender is X) or (recipient is X)
- John = Person "John"
- Claire = Person "Claire"
- Fred = Person "Fred"
- People = John or Claire or Fred
- Friends = People and not Fred.
- "Person X" is a view that shows the bidirectional email exchange with
Person X. John, Claire, and Fred are views built in this way. For
example, when the user wants to see all their communications with
John, they invoke the view "John". Similarly, when the user wants to
see all their communications with their friends, they invoke the view
- There should be a convenient way for users to create, edit, and invoke views.
- Good work on this project has already been done by the former MSc
student Yuen Chan. The idea now is to refine that work and design an
graphical user interface that appeals to typical users.
- Pre-requisite knowledge: good programming skills (the use of Java is
- A Java board game API
- The idea is to provide a Java Application Programming Interface (API)
that enables a Java programmer to implement new board games quickly by
using your API's classes and interfaces.
- For example, there may be classes called:
- "Board", which allows the implementation of a game board,
- "Move", which describes a Player's move,
- "Strategy", which describes a computer strategy, and which
essentially maps Boards to Moves.
- There should be features like "load game", "save game", "undo move",
and the possibility to let the computer play against itself (using two
different strategies). An optional feature would be the implementation
of an optimal strategy for ANY game that assigns scores to board
situation. This could be implemented by a technique called "alpha-beta
search" (also "minimax search").
- The usefulness of the API should be demonstrated by using it to
implement at least three SIMPLE games, like Tic-Tac-Toe or
Connect-Four. The point is to demonstrate that your API nicely
captures the common elements of board games, and any Java programmer
who is interested in implementing a board game would have an easier
time if they used your API.
- Pre-requisite knowledge: This project requires an excellent understanding of object-oriented
programming, and Java in particular, because the code you produce is
not aimed at end-users, but at PROGRAMMERS who build on it.
- Indicative reading:
To get an idea of alpha-beta search, look at