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.

News:
The final contest reports have been graded. Grades have been submitted to the student administration.

Course information

Lectures: Thursdays from 9:15 to 11:00 in Snellius room 408, with sometimes a lab session in 302-304
Lectures: Thursdays from 9:30 to 14:00 (contest days) or from 10:00 to 11:00 (student presentation days) in a Kaltura Live Room.
Lecturer: dr. Frank Takes, f.w.takes@liacs.leidenuniv.nl, room 157b
Assistant : Ludo Pulles BSc, l.n.pulles@umail.leidenuniv.nl
Examination: individual assignment (20%), presentation and report (35%) and three programming contest rounds (together 45%)
Spoken language: English
Study points: 6 ECTS


Timetable

  Date Lecture Lab session
1. Feb 6, 2020 Lecture 1: Course introduction Domjudge introduction (see slides)
2. Feb 13, 2020 Lecture 2: Data structures and libraries Practice problems week 2
3. Feb 20, 2020 No lecture (as announced via e-mail) Practice problems week 3
4. Feb 27, 2020 Lecture 3 4: Problem types Practice problems week 4 (wrong endtime)
Practice problems week 4
5. Mar 5, 2020 Programming contest (soft)
Mar 16, 2020 Deadline for invididual assignment (soft contest report) Click here to upload your report
6. Mar 12, 2020 Presentation 1: Fenwick trees
Presentation 2: 2-SAT using connected components
Presentation 3: Max flow
7. Mar 19, 2020 No lecture (university COVID-19 policy) 10:00 Testing and Q&A Kaltura Live Room
8. Mar 26, 2020 9:30 - 14:00: First programming contest (live) TCR
9. Apr 2, 2020 Presentation 4: Matrix Exponentiation
Presentation 5: Backtracking with Bitmasks
Presentation 6: Union-find disjoint sets

Practice problem virtualfriends, control
10. Apr 9, 2020 9:30 - 14:30: Second programming contest (live) TCR
10. Apr 10, 2020 Note: Friday 11:00 session
Presentation 7: Min cost flow
Presentation 8: Graph matching
Presentation 9: Chinese postman problem
Practice problems: miscostmaxflow, mincut, catering
Practice problems: catvsdog, paintball
Practice problems: joggingtrails
11. Apr 16, 2020 Presentation 10: Ternary search
Presentation 11: Suffix trees
Presentation 12: Cycle-finding in functions

Practice problems: happyprimes, rats
12. Apr 23, 2020 Presentation 13: Bitonic TSP
Presentation 14: Closest pair problem
Presentation 15: Dinic's algorithm
Presentation 16: Lowest common ancestor
13. Apr 30, 2020 9:30 - 14:30: Third programming contest (live) TCR
May 11, 2020 Deadline for topic report Click here to upload your report

Presentation and report - Topics

As part of the course, all students give a presentation and write a report about a topic related to competitive programming. The topic of the 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. During the February 27 lecture, topics will be assigned to students. 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. There are a few more topics than students.

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