Software Lab WS2025
Algorithmic Battle
Summary
In this lab, teams will be formed to then compete against each other on five different problems. For each of the five problems, the teams write a generator for hard problem instances, and a solver that should efficiently solve the instances of the other groups. The five problems will be choosen to represent a wide range of problem classes, e.g. will be problems in P, NP, parameterized problems, graph or string problems, approximation problems or not, maybe with with heavily restricted space,...Organization
This year, the lab will not only be offered as a Softwareprojektpraktikum for computer science students at RWTH, but additionally be open to students from our ENHANCE partners. Therefore, we will start with the lab two weeks before the lecture period in Aachen starts, so the lab will finish the week before christmas.Students from RWTH should register on the well-known Supra-sytem, students from other ENHANCE-universitys can register via the microcredential catalog. Please not that there are deadlines, and that we can only offer a limited number on spots in this lab.
We will start with a kickoff meeting to discuss organizatorial matters, form groups and present with a (not graded) warmup task to familarize with the system and the concept. Afterwards, a total of five tasks will be given, each with a duration of two weeks.
For each problem, every group should think about
(a) what instances of the problem are hard (and likely not easy to solve the problem on for other groups), and
(b) how to algorithmically solve the instances of the other groups, ideally as efficient as possible.
The instances generated by one team are then given to the solvers of another team, and vice versa. The goal of each problem, of course, is to win against the others by finding harder instances or better algorithms.
So as a main difference to other lab courses, we will not hand out a task to be solved until some large deadline: each problem will only be a task for two weeks, with the main goal to learn a lot about different problem settings, and to play and experiment with different approaches on how to beat the other groups.
For the implementation, we do not require anything specific: Your generator and solver will both run in a docker container, so everything that your group can make running will work out for the lab course.
In particular, you are not only allowed to use whatever coding language you prefer, but also to use external libaries, tools, programs,... (as long as there are no copyright concerns). One of the goals of the lab is to learn how to work efficiently, therefore this freedom should encourage you to think about when to invest time in own development and when to just adapt other findings.
Organizatorial Aspects
Students of RWTH can register at the supra-system as a Softwareprojektpraktikum (please note the deadlines), students of other ENHANCE-universities can use the registration over the microcredentials catalogue (also please note the deadlines).
In comparison to the last years version of the lab course, there are some organizatorial changes necessary to allow students from other universities to participate:
First, the main, biweekly meetings, where each group presents their ideas at the end of a problem, and the next task gets presented, will likely be held digitally via zoom (so that participants from everywhere can join). This allows you to participate in the lab even if you are not at one particular place like Aachen. There is also no other reason that requires attendance in person, thus participation in the lab is possible from everywhere.
As the semester dates are different everywhere (and basically an exception in Germany), we will start the lab course in early October (likely the warm-up task will be presented two weeks before the lecture period in Aachen starts), and we will be finished with everything before Christmas. This should be a subset of the fall term weeks for most coutries.
For students from Aachen this also allows to fully concentrate on the exam period afterwards (which usually starts end of January).
Requirements
You should have liked the content that was discussed in subjects like Datastructures and Algorithms, and be motivated to play around with algorithms yourself. It would be also beneficial if you have written a few lines of code before.
Documentation and Code standards
We encoruage every participant and every group to write clean code and helpful comments. This is not only necessary as this lab is a group work with different people having to understand the code, but also helpful as usually groups tend to recycle code written for one task at a later task. The quality of the code will also be part of the grading. We suggest that every group agrees on common standards they want to maintain, and also on a sensible software structure.
At the end of each task, two members of each group will give a short presentation about the used and unused ideas, and report what were successful approaches and what not. Additionally, those approaches should also be written down in a short documentation (usually a few pages) by each group collectively.