Universiteit Leiden

Competitive Programming

This course is intended for highly motivated master students in computer science, especially those with a with a keen interest in algorithm development and programming. Knowledge of C++ (or Java), algorithms and datastructures is required. The course welcomes up to 15 computer science students.


Note: this course is not taught in Spring 2023 and 2024.


Course information

Lectures & lab sessions: Tuesdays from 14:15 to 16:00, lectures in Snellius room 313, lab sessions in 302-304
Lecturer: dr. Frank Takes, f.w.takes@liacs.leidenuniv.nl, room 157b
Assistant : Ludo Pulles MSc (l.n.pulles@math.leidenuniv.nl) and Hanjo Boekhout MSc (h.d.boekhout@liacs.leidenuniv.nl, room 126)
Examination: individual assignment (20%), presentation and report (35%) and three programming contest rounds (together 45%)
Format: on-site (lectures will be recorded as backup in case of corona-related absence)
Grading: two presentations and reports (each 30% of the final garde) and two live contests (each 20% of the final grade) Spoken language: English
Study points: 6 ECTS
Previously taught in: 2020
Brightspace: Competitive Programming


Timetable

  Date Lecture (14:15 - 15:00 in 313) Lab session (15:15 - 16:00 in 302-304)
1. Feb 15, 2022 Lecture 1: Course introduction Domjudge introduction (see slides)
2. Feb 22, 2022 No lecture
3. Mar 1, 2022 No lecture Kattis practice problems week 2
4. Mar 8, 2022 Lecture 2: Data structures and libraries Kattis practice problems week 3
5. Mar 15, 2022 Lecture 3: Problem types Kattis practice problems week 4
6. Mar 22, 2022 No lecture
7. Mar 29, 2022 Soft contest & Evaluation; 13:15 - 18:00 in 302/304 TCR
8. Apr 5, 2022 No lecture
9. Apr 12, 2022 Student presentation 1: Minimum cost flow
Student presentation 2: Bidirectional search
Student presentation 3: Sliding window problems
10. Apr 19, 2022 No lecture & Deadline report on first presentation topic
11. Apr 26, 2022 Live contest 1; 13:15 - 18:00 in 302/304
12. May 3, 2022 No lecture
13. May 10, 2022 Student presentation 4: Lowest Common Ancestor
Student presentation 5: Bitonic TSP
Student presentation 6: Union-find disjoint sets
14. May 17, 2022 Live contest 2; 13:15 - 18:00 in 302/304
May 24, 2022 Deadline report on second presentation topic

Due to the lower number of students and personal circumstances of the lecturer, several lectures were canceled.

Presentation and report - Topics

As part of the course, students give two presentations and write corresponding reports about topics related to competitive programming. The topic of a presentation is usually a particular more specialistic a) data structure, b) problem type or c) algorithm with relevance to competitive programming. For more information, among others about the report, see the document on the course project (presentation and report).

A list of topics can be found below. Numbers between parenthesis mostly refer to sections of the book by Halim, in which a short description of the topic and links to example problems can be found.

Students with a lot of experience in programming contests are strongly encouraged to not choose from the somewhat easier first four topics.
Please see Brightspace for slides detailing the topics that were not chosen.

  1. Max flow: Fulkerson and Karp (4.6)
  2. Big integer problems (5.3)
  3. [Chosen] Sliding window problems (9.31)
  4. Closest pair problem (9.6)
  5. [Chosen] Union-find disjoint sets (2.4.2)
  6. Binary indexed (Fenwick) tree (2.4.4)
  7. Suffix tree (6.6.2)
  8. Suffix array (6.6.4)
  9. Ternary Search (Laaksonen 8.3.1)
  10. Graph matching (9.10)
  11. [Chosen] Minimal cost flow (9.23)
  12. [Chosen] Bidirectional search (8.2.4)
  13. Chinese Postman Problem (9.5)
  14. Dinic's algorithm (9.7)
  15. Cycle-finding in functions (5.7)
  16. Backtracking with bitmasks (8.2.1)
  17. 2-SAT using connected components (9.1)
  18. [Chosen] Bitonic traveling salesman problem (9.3)
  19. [Chosen] Lowest common ancestor (9.18)
  20. Matrix exponentiation (9.21)