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: 31.01.2024, 15:00

We covered grading and the task A Journey to Greece from GCPC 2015. You can find it as 100753A at Codeforces.

Here you can access the meeting "slides".

Weekly meetings: Tuesdays, 10:00AM, 02.11.018

Meetings are hosted online (but not recorded) at BBB.

Change of place, 16.04: one time only we're moving to 02.09.014.

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