Algorithmic Battle

This learning opportunity is a lab course designed for computer science students, aiming to improve their algorithmic knowledge and coding ability and focusing on aspects often ignored in other courses.

Groups of ~6 students will be formed, which then will compete against each other in five different problems.

Each problem will focus on another aspect of the design of algorithms: thus likely some problems will be solvable in polynomial time,

one will be a parameterized problem, one will focus on heuristics, in another the efficient usage of memory space will be crucial, some might be on graphs while others are string-problems,...

For each problem, the groups have to write an instance generator and a problem solver. The instances created by a generator of one team will then be given to the solvers of the other groups, that then have to solve the problem on the given instance (the so-called "battles"). We then will measure how large an instance can such that the solver is still able to solve it within a time frame. Points will be awarded to each group for their performance in the battles.

Each team will report about their strategies at the end of each task in a digital meeting.

Of course a good understanding of the stated problems and coding experience in general, but furthermore

• To understand what makes a problem hard, how an instance should be designed such that the solver of other teams will struggle with them (for example, you might have heard that most SAT instances are easy to solve, but how do the hard ones look alike?)
• The ability to do research about each problem; and to decide what is worth it to code yourself and what can be used or adapted (each generator and solver will run in a docker-container, thus we neither restrict the coding language nor the used libraries, tools or solver*)
• The importance of rigor testing, as other groups might try to catch your missed edge cases (like empty instances...)
• The ability to coordinate the group work within an international team

(*as long as the groups are legally allowed to use it and are able to make it run)

In the first week, a simple problem will be stated as a warm-up task to get to know the system of the lab course.

Afterwards, five problems for two weeks each will be stated, each focusing on different aspects of algorithmics.

The two-level mutual trust-based quality assurance scheme has been adopted:

• at the university level: RWTH Aachen has applied its internal quality assurance procedures and structures to the proposal of Algorithmic Battle it submitted to ENHANCE and to its implementation - the related learning activities,
• at the Alliance level: the body composed of Education Officers has made decisions regarding the inclusion of Algorithmic Battle proposed by RWTH Aachen to the Innovative Learning Campus part of the joint ENHANCE educational offer, based on the compliance with the formal requirements and ENHANCE goals.

In the first week, a simple problem will be stated as a warm-up task to get to know the system of the lab course.

Afterwards, five problems for two weeks each will be stated, each focusing on different aspects of algorithmics.

No test or exam;

Grading will be based on the individual contribution to the team, as visible mainly by the documentation and the git-history.

Registration deadlines:

Winter Semester (October 1 to March 31): Registration open from August 1 to September 13

How to register + enroll:

Send an e-mail to: tcs-teaching@informatik.rwth-aachen.de, stating

• your full name,
• your birthdate,
• your home university,
• your university e-mail address,
• 1-2 sentences about your motivation for taking this course.

Grading: An individual grading on a scale with the grades 1.0, 1.3, 1.7, 2.0, 2.3, 2.7, 3.0, 3.3, 3.7, 4.0, and 5.0; with 1.0 as the best grade and 4.0 as the lowest passing grade.

Grading will be based on individual contributions:

In the last years usually top grades were given to participants of all teams. A top performance in the battles is usually only an indicator,

that the team consists of more highly motivated participants than other teams, so the average grade is just higher.

The individual grading does not benefit from a participant being in a stronger or weaker team in the battles.

Please note: We recommend checking with your local examination board at your home university, whether recognition is possible.

The main website, on which the battles will take place: algobattle.org

The course website for this winters edition and possible organizatorial updates: https://tcs.rwth-aachen.de/lehre/algobattle/WS2026/

For course-content related questions: tcs-teaching@informatik.rwth-aachen.de