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 university is closed for the remainder of the semester as a result of COVID-19. From now on, the course will be online.
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, firstname.lastname@example.org, room 157b
Assistant : Ludo Pulles BSc, email@example.com
Examination: individual assignment (20%), presentation and report (35%) and three programming contest rounds (together 45%)
Spoken language: English
Study points: 6 ECTS
|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
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|
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.