Practical Course: Advanced Algorithms in Competitive Programming Problems

Content

We will examine a selection of interesting problems from competitive programming contests (e.g. ICPC, Advent of Code, Topcoder) focusing on solution techniques and effective implementations of algorithms and data structures commonly appearing in them. Students will attempt to solve the tasks individually, while the model solution will be presented a week later.

It is expected students are familiar with advanced algorithms and data structures, such as:

  • BST trees;
  • graph algorithms (shortest path, DFS trees, matchings and flows);
  • dynamic programming;
  • union/find.

Basic experience in a systems programming language (C++, Rust) is required.

Organization

Preliminary meeting: 05.02.2025, 17:30 (02.09.014)

Also hosted online.

Weekly meetings: Tuesdays, 10:00AM, 02.11.018

Judging platform: https://aacpp.db.in.tum.de/

Previous Knowledge Expected

  • Introduction to Informatics 1 (IN0001)
  • Fundamentals of Programming (IN0002)
  • Fundamentals of Algorithms and Data Structures (IN0007)
  • Efficient Algorithms and Data Structures (IN2003)
  • Advanced Algorithms (IN2360)

Objective

After the completion of this course students should:

  • know the structure of a competitive programming contest, tasks, and judging platforms;
  • be familiar with designing effective algorithmic solutions to competitive programming problems;
  • know how to identify the time and memory complexity of an algorithm;
  • be able to implement the advanced algorithms and data structures on their own in an efficient systems programming language;
  • know how to present a solution and justify its correctness.

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022) [1990]. Introduction to Algorithms (4th ed.). MIT Press and McGraw-Hill. ISBN 0-262-04630-X

 

Navigation