Project Topics

In general, all projects should include a description of how to build the project including prerequisites, such as libraries that need to be installed. The projects should use cmake if possible (qmake if you intend to use Qt).

Numerical Library

Create a numerical library that can deal with arbitrary-precision fixed-point numbers. The library should ideally work similarly to the standard Linux arbitrary-precision calculator bc. This includes working with any given precision in any given numeral system.

Minimum requirements:

Graph Library

Implement a library for basic graph algorithms such as graph traversal or shortest paths. The library should allow for different kinds of graphs by using templates.

Minimum requirements:

Parallel Reachability

Implement a parallel algorithm for computing reachability in implicit graphs. An implicit graph is described using a graph generator that has a function returning the initial vertex and a function that for any given vertex returns the list of its successors. The project should also analyse the efficiency of the algorithm and compare several different approaches. Optionally, instead of simple reachability, you can think of a different graph problem, such as strongly connected components or shortest paths.

Minimum requirements:

Bytecode

Design a simple bytecode language (simplified Java bytecode or something similar) and implement a bytecode interpreter. The interpreter should include garbage collection.

Minimum requirements:

Chat Client/Server

Create a simple chat client/server with at least the basic functionality of sending/receiving messages and adding/removing contacts. The client should use threads (for incoming messages processing). Additionally, the client could have a friendly UI, either terminal-based (using, e.g., curses) or graphical. Optionally, you can also implement end-to-end encryption.

Minimum requirements:

Discrete Dataflow Programming Library

Create a library for dataflow programming. The principle of dataflow programming is that the program consists of a set of blocks (elements). Each of the blocks computes a simple function, such as adder blocks, multiplier blocks, or conditional blocks, and has a set of input and output ports. The ports are connected using dataflow arcs. Some of the blocks may even use memory, such as the unit delay block that outputs the previous value it has received on its input port. The computation of a dataflow program (in this discrete version) happens in “ticks”. As an example of a dataflow programming environment, you might want to look at Simulink.

Minimum requirements:

Constraint Solving Library

Create a library that can solve constraint satisfaction problems. The goal of the library is to support (a fragment of) the constraint programming paradigm. One of the options is to build the library on top of an SMT solver, such as Z3.

Minimum requirements:

2D Physics Simulator

Create a 2D physics engine and a showcase tool (or possibly a sandbox game). The engine should be able to deal with various 2D objects and their interactions, such as gravity and collisions.

Minimum requirements:

Choose Your Own Topic

You are also allowed to choose your own project topic. The topic should be interesting and should not be too simple. You should send us an extended abstract together with the minimum requirements that you plan to implement (for inspiration, see above).

Ideas: