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 university is closed for the remainder of the semester as a result of COVID-19. From now on, the course will be online.

  • The upcoming student presentations will be prerecorded by students, preferably via Kaltura Capture or another tool where you can have at least both slides and sound, accessible via a URL. The deadline for sending the lecturer the URL of your video is 11.00 on the Wednesday before the Thursday you are presenting. You can still send me your slides on for example Monday for some feedback, before creating the video.
  • The weekly seminars will be online via a Kaltura Live Room, weekly on Thursday at 10.00. A link to connect to the room will appear on the course website. The videos of presenting students will be made available the day before, and all students are expected to watch these videos and digitally give feedback through an online form, similar to how we did this with the paper forms last week.
  • The live programming contests will take place remotely.

Live Room March 19

New Live Room from March 26 onwards

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 1 2
10. Apr 9, 2020 9:30 - 14:00: 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
11. Apr 16, 2020 Presentation 10: Ternary search
Presentation 11: Suffix trees
Presentation 12: Cycle-finding in functions
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:00: Third programming contest (live)
May 11, 2020 Deadline for topic 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)