Volker Sorge's UG and MSc project suggestions

I am mainly interested in artificial intelligence techniques and mathematics- and logic-related topics. I am particularly interested in the application of distribution and multi-agent technology to automatic and interactive theorem proving. I am also interested in topics in the area of image analysis and recognition. In particular, if you want to do an MSc project in Computer Security with me, I prefer topics that involve some sort of graphics component. Furthermore, I am interested in the application of CS/AI in Law.

The following project proposals are just some projects that fit into my current line of work. Please feel free to come up with ideas of your own and to contact me.

- Graphical Input Device for Theorem Provers
- Venn Diagram Editor
- Compression Techniques for Mathematical Data
- Mathematical Middleware Components
- Emacs Mode of Specifying Mathematical Service
- Analysing Mathematical Expressions
- Analysing Latex Texts for Mathematical Formula Extraction
- Biometrics
- Watermarking
- Steganography
- Cryptography
- Distributed Search via the Grid
- Environment for Internet Distribution of Various Software Agents
- Negotiations among Software Agents
- Learning in Software Agents
- Gameplaying Testsuite
- Settlers of Catan
- (Un)Fair Card Shuffling
- Multiplayer Version of Conway's Game of Life
- Example Ontology for a Law Subject

Theorem Proving

Mathematical OCR

Computer Security

Distribution/Agent Technology

Gameplaying

Law

1. Graphical Input Device for Theorem Provers

Brief Description: The idea of the project is to develop a user interface that helps a user to specify knowledge for a theorem proving system. I.e., the task is not to implement a GUI for the whole theorem prover but only a front end for specifying problems, theorems, and definitions, as well as more advanced structures such as tactics or proof planning methods.

Languages and/or other Software: Java

2. Venn Diagram Editor

Brief Description: Venn diagrams are used in mathematical set theory to graphically display the relation between sets in order to give an intuition of the validity of set equations, etc. The idea of the project is to develop a user interface that aids the graphic input of Venn diagrams, their translation into an appropriate logic format, and the translation and display of set theoretic formulas into Venn diagrams.

Languages and/or other Software: Java

3. Compression Techniques for Mathematical Data

Brief Description: There exist several different techniques for compressing general data. Algorithms can often be improved if they are specialised for specific kind of data. The idea of the project is to develop specialised compression techniques for mathematical data such as large matrices or large systems of equations.

Languages and/or other Software: Java, Haskell or Lisp

4. Mathematical Middleware Components

Brief Description: Mathematical middleware components form the link between mathematical knowledge bases and theorem proving systems by combining functionality of both. The aim of the project is to give a specification for the requirements of mathematical middleware components and to implement a prototype.

Languages and/or other Software: Java, Lisp, or Oz

5. Emacs Mode of Specifying Mathematical Service

Languages and/or other Software: Emacs-Lisp

6. Analysing Mathematical Expressions

Brief Description: Mathematical expressions are often 2-dimensional. When scanning texts and subjecting it to OCR methods, it is difficult to recognise single mathematical expressions from a set of unconnected characters. The idea of the project is to construct the mathematical expression including subscripts, superscripts, fractions, summations, matrix expressions and as many other mathematical expression components as possible.

Languages and/or other Software: Java, OCaml

7. Analysing Latex Texts for Mathematical Formula Extraction

Brief Description: Latex provides elaborate commands to construct complex mathematical formulas and expressions. However, the very same expressions can often be constructed using placement of the single component characters involved. The aim of the project is to analyse and combine Latex commands to more complex structures.

Languages and/or other Software: Java, Ocaml, LaTeX

8. Biometrics

Brief Description: Analysing biometrical data for cryptographic purposes. E.g. reliably extracting crypto keys from signatures or images.

Languages and/or other Software: C, Java, OCaml

Prerequisite: Some graphics and cryptography

9. Watermarking

Brief Description: Inserting, dedecting, or removing watermarks in images, sound files, videos, etc.

Languages and/or other Software: C, Java

Prerequisite: Some graphics and cryptography.

10. Steganography

Brief Description: Hiding or dedecting messages in inconspicuous files. For example putting encrypted messages into images.

Languages and/or other Software: C, Java

Prerequisite: Some cryptography.

Literature: See the following paper foran introduction.

11. Cryptography

Course Suitability: MSc in Computer Security

Brief Description: Mathematical anaysis of cryptographic algorithms. Overview projects on elliptic curve cryptography, on cryptanalysis techniques for particular ciphers, etc.

Prerequisite: A good background knowledge in Mathematics for Cryptography

12. Distributed Search via the Grid

Brief Description: Implementation of a generic search engine that realises And/Or-tree search on the Grid. The project should result in a software that enables to control the distribution and search with arbitrary processes.

For example: We want to distribute the processes A1,...,An. (We do not need to know, what the processes actually are or compute, as long as we have a means to judge when the result of a process is positive or negative.) As soon as one of the processes returns a positive result the search should terminate. If none of the processes returns a positive result, the negative results should be combined. The software should then schedule time and run the single processes on the grid, monitor their output and either record a positive result from one process and terminate all other processes, or wait for all processes to terminate in order to construct the negative result.

Languages and/or other Software: C or Java, with Grid-Engine and the MPI library

Literature: See the following webpages for information on Grid Engine and an intro to MPI.

13. Environment for Internet Distribution of Various Software Agents

Brief Description: The idea of the project is to implement a generic framework that would allow the easy encapsulation and distribution of arbitrary programs as agents in a multi-agent environment. The program should provide clearly defined interfaces for client systems enable the communication between agents in some standard protocol like KQML.

The project would involve getting familiar with the state-of-the-art agent technology, designing and implementing communication and interface as well as ways to control the distributed system. Furthermore, a small case study should demonstrate the usefulness of the system by actually connecting agents such as a search engine and a database.

Languages and/or other Software: Java or Oz

14. Negotiations among Software Agents

Brief Description: Specification and implementation of different negotiation models for multi-agent systems.

Languages and/or other Software: Java or Lisp

15. Learning in Software Agents

Brief Description: Specification and implementation of learning algorithms for multi-agent systems.

Languages and/or other Software: Java or Lisp

16. Gameplaying Testsuite

Brief Description: Specification and implementation of a generic testsuite for two player games such as Tic-Tac-Toe, Checkers, Backgammon, etc. The idea is to have a generic tool with which two implementations or two different strategies of the same implementation can be tested against each other.

Languages and/or other Software: Lisp, ML or Haskell

17. Settlers of Catan

Brief Description: Implementation of the board game 'Settlers of Catan' with several possible playing strategies for computer players.

Languages and/or other Software: Java

18. (Un)Fair Card Shuffling

Brief Description: There exist probability theoretical approaches to model card shuffling to predict how often a deck of cards has to be shuffled to be randomly distributed or how it has to be shuffled achieve sequences of cards (of the same suit etc.) for various dealing situation. The project will involve getting into the mathematics and implementing a prediction algorithm for rising sequences for various card decks.

Languages and/or other Software: Java

Prerequisite: Some knowledge of probability theory.

Literature: A brief intro to the theory behind card shuffling and some references from Mathworld.

19. Multiplayer Version of Conway's Game of Life

Brief Description: This is not really a game. It is an implementation of a cellular automata that John H. Conway chose to call "The Game of Life". It simulates the birth, death, etc., of organisms based on certain rules. The game is designed for the population of one species. The project involves the extension to two or more species, including specification of the extended rules and implementation of the simulation.

Languages and/or other Software: Java

Literature: Some downloadable single player games

20. Example Ontology for a Law Subject

TopBrief Description: The aim of the project is to develop and encode a suitable ontology for a small subset of a particular law subject. The project will involve some research into ontology languages such as ITL or OWL, in which the ontology should be encoded.

Prerequisite: Some knowledge of a law subject.

Back