Prof. Dr. Tobias Friedrich

(Advanced) Competitive Programming

BSc/MSc Lecture - Summer 2024


In Competitive Programming, the goal is to devise fastest possible algorithms for problems and implement them. The time for coding is limited. Correctness and efficiency is verified by an automatic Online Judge system that runs your code against secret test cases. This kind of programming challenges has a long-standing tradition. Since 1970, the Association for Computing Machinery (ACM) holds the annual International Collegiate Programming Contest (ICPC). At ACM-ICPC, teams of three students from the same university try to solve as many problems as possible while using a single PC. There are several kinds of tasks that usually appear: graph problems (e.g., single-source shortest paths via Dijkstra), search problems (e.g., backtracking), geometric problems (e.g., convex hull), number theory problems (e.g., factorization into prime factors), and others (e.g., board games or parsing problems).

In this course, you will learn how to recognize different kinds of problems, design algorithms solving them, and implement these algorithms in Python or C++. By completing the course, you are not only well-prepared for coding interviews, but have also improved your Software Engineering skills all-around: you know C++ better, you have a full algorithmic toolbox at your disposal, you easily recognize various algorithmic problems and their solutions, and you always keep in mind the running time and the memory consumption. Moreover, debugging complex algorithms becomes much easier for you, and you have also learned to work efficiently as part of a team.

Every week, you will get a new topic explained in class, and then immediately apply the knowledge by solving programming exercises in the homework. Besides the homework problems, there will be several Live Contests, where we will simulate a real-world programming competition. We only aim to introduce a more dynamic and engaging problem-solving experience through these contests: as opposed to real-world events, here only the number of solved problems matters for evaluation, so there is no direct comparison to the performance of other participants.

With the experience obtained throughout the course, you are also well-set to participate in German and European Competitive Programming competitions as part of HPI teams, and get even more problem solving experience. Our experienced coaches also provide support in preparation and participation in these events!


We expect good command of C/C++ and basic knowledge of algorithms, obtained for example after passing the courses Theoretische Informatik 1 or Algorithmic Problem Solving.

Specifically, we require basic knowledge in the following areas:

  • Methods in algorithms design: greedy, divide and conquer, dynamic programming, backtracking, and recursion;
  • Fundamental data structures: arrays, lists, stacks, queues, binary search trees, binary heaps, adjacency lists, and adjacency matrices;
  • Standard topics in algorithms: big-O notation, sorting algorithms, enumeration, simple algorithms on graphs (e.g., tree transversal, DFS and BFS).

The class will be held in English.

Learning and teaching methods

Interactive discussions of different solution approaches will be an essential part of the course. During the lectures, we will not only introduce the relevant theoretical concepts, but will also cover implementation details and various tips and tricks to programming and contest participation.


During the course, there will be weekly programming exercises, the solutions will be evaluated by the Online Judge and explained later in class. At certain weeks instead of the class we will have Live Contests similar to real-world competitions. Course participants will split into teams of two for Live Contests, and the homework problems are to be solved alone.

The weekly exercises constitute 40% of the final grade, and Contests amount to 60%. One Final Contest will take place during the exam period; it will be longer, and contribute more towards the grade compared to the other Contests.


We meet weekly on Fridays, 13:30 - 16:45, the first meeting will be held on April 12 in the room HS 2.

Lecture Team

The following persons are involved in this lecture:

Dr. Kirill Simonov


Office: K-2.06
E-Mail: Kirill.Simonov(at)hpi.de

Farehe Soheil


Office: K-2.19/20
E-Mail: Farehe.Soheil(at)hpi.de