Home

Welcome to the algobattle wiki!

Use the side bar to navigate through topics such as how to create your own problem files and on the functionality of the implemented battle wrappers.

A lot of this project is still undocumented. If you are interested in a topic, whether specific or broad, that is not yet documented, please let us know.

What is the core concept of this project?

You are looking at code that was developed for use in an academic context, primarily in higher education. This framework is supposed to let you hold a lab course without having to do the heavy lifting of implementing the core logic of it. This means that you can focus on the kinds of problems that you want your students to solve.

The basic idea is quite simple. Complexity theory tells us that (we assume that) some problems have a bad worst-case runtime complexity, be it of a high polynomial order in the size of the input or even of non-polynomial complexity. In practice, these theoretically hard problems are often solved anyway, and much quicker than one might assume. The students are thus tasked with finding out what the hard core of a problem is. This task is to be solved from two points of view. The first one is to design an instance of a fixed size that is deemed hard to solve. The other point of view is to design a solver that is capable of solving hard instances quickly. Every groups solver is then pitched against each other groups generator.

Points are awarded in a battle between two teams in regards to how much better they are able to solve a problem than another team. This encourages optimizing both the generator and the solver.

As the organizer of the lab course, your part in preparing such a battle is in designing such a problem. This means specifying the problem itself, how it is supposed to be encoded and how a solution for an instance can be verified (we recommend also writing tests).

You can then give these problems to your students. The students can use whatever programming language, libraries or other tools they want, as long as they can build a docker container around them. This means that you do not have to worry about installing anything on your host machine other than docker and python in order to run this lab course.

Follow the side bar to dive deeper into specific topics, such as designing a concrete problem. If you need any help, feel free to contact us.