Competitive programming is a course to prepare students for programming contests like the ACM ICPC. TU Kaiserslautern did not have a strong tradition of actively recruiting student teams to for such contests, and Annette Bieniusa and I set out to change this in the summer term of 2017. This course is only a start in this respect, but the feedback from the students was very encouraging.
Since we invited students in all stages of their studies, we started with a brief (15-30min) recap of the involved mathematical facts, algorithms and data structures, with sample code on how to implement them as quickly as possible on handouts. This part was my main contribution to the course. Afterwards, students would start working on that week’s exercise problems in teams in class, with the option to ask Annette and me for support.
The course builds on the comprehensive collection of topics in Competitive Programming by the Halim brothers and Programming Challenges. The Programming Contest Training Manual by Steven Skiena and Miguel Revilla.
We selected 11 topics plus three seminar talks by students who reviewed some less often used topics and prepared them for use in programming contests.
- Introduction, warm-up exercises for parsing input
- Graph algorithms I : graph representations, DF/BF search, reachability
- Graph algorithms II : shortest paths, minimum spanning trees
- Graph algorithms III: strongly connected components, topological order
- Number Theory: gcd, lcd, prime numbers, Chinese Remainder Theorem
- Geometric problems
- Dynamic programming I
- Dynamic programming II
- String algorithms
- Problem solving paradigms (simulation, brute force, divide and conquer)
- Bitwise tricks
- Seminar talk: Gale-Shapely stable marriage
- Seminar talk: Union-find
- Seminar talk: Suffix trees
This is a screenshot of the final results of the course evaluation for Competitive Programming. The original website is only accessible from within the university network of TU Kaiserslautern.