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.

This course is organized around solving actual competitive-programming problems using a local DOMjudge installation. In each week we focus on a specific design strategy or algorithm (see list below)

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.

Course Contents

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.

  1. Introduction, warm-up exercises for parsing input
  2. Graph algorithms I : graph representations, DF/BF search, reachability
  3. Graph algorithms II : shortest paths, minimum spanning trees
  4. Graph algorithms III: strongly connected components, topological order
  5. Number Theory: gcd, lcd, prime numbers, Chinese Remainder Theorem
  6. Geometric problems
  7. Dynamic programming I
  8. Dynamic programming II
  9. String algorithms
  10. Problem solving paradigms (simulation, brute force, divide and conquer)
  11. Bitwise tricks
  12. Seminar talk: Gale-Shapely stable marriage
  13. Seminar talk: Union-find
  14. Seminar talk: Suffix trees

For further information see also the official course website. If you are interested in the handouts, please drop me a mail.

Evaluation

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.