• Main
• Lectures
• Seminars
• Homework
• Projects
• Tools

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:

• all standard arithmetic operators (at least + - * /);
• current precision level setting;
• an arbitrary numeral system as both input and output;
• extensive unit tests;
• well-written documentation;
• a showcase program that works as a simple calculator with variables.

Graph Library with Concepts

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 and concepts.

Minimum requirements:

• concepts defining the notion of graphs, vertices, edges, etc.;
• template-based code that allows the users to supply their notion of a graph as represented by the defined concepts;
  • this means that the functions should have a templated parameter typename Graph;
• basic graph traversal algorithms: BFS, DFS (incl. an iterative version to be able to traverse large graphs);
• at least one of the following:
  • several shortest-path algorithms,
  • several minimum spanning tree algorithms, or
  • several algorithms for max-flow or variants thereof;
• extensive unit tests;
• well-written documentation;
• a benchmark suite.

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:

• template-based code that allows the users to supply their graph generator;
• at least two different approaches;
• some final report about the reachable part of the graph (its size in the number of vertices and edges, whether any interesting vertices such as deadlocks were encountered);
  • Note: A deadlock vertex is a vertex without outgoing transitions.
• well-written documentation;
• a benchmark suite and a document describing the evaluation results, including the scalability of the implemented approaches.

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:

• Turing-complete language with a reasonable set of instructions;
• support for functions and simple data structures;
• the ability to allocate memory on the heap;
• garbage collection (reference counting, mark and sweep, …);
• well-written documentation;
• unit tests;
• a set of example programs for your language.

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:

• user registration and contact lists on the server;
• the ability to add/remove contacts (adding a connection can optionally need to be confirmed by the other user);
• the ability to send and receive messages including offline messages;
• Unicode support;
• terminal-based or graphical UI client;
• thread-based/asynchronous code for the processing of messages;
• well-written documentation including the communication protocol used.

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:

• basic data-flow, arithmetic and unit delay blocks;
• multiple inputs and outputs;
• verbose/debugging output to see what is happening;
• well-written documentation;
• unit tests;
• a set of example circuits.

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:

• support for a reasonably large set of constraint kinds;
• adding of symbolic variables and constraints on the fly;
• nice C++ syntax via operator overloading and user-defined literals;
• well-written documentation;
• unit tests;
• a set of examples, e.g. a sudoku solver.

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:

• various kinds of 2D objects (circles, rectangles, polygons);
• some implementation of gravity and collisions;
• well-written documentation;
• unit tests;
• a show-case tool (or a simple sandbox game).

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:

• A multiplayer network-based computer game.
• A simple X11- or Wayland-based window manager (see tinywm for inspiration).
• An interesting data structure.
• A comparison of various memory allocators.
• Some kind of ranges extension.
• Discord or IRC bot.