Competitive Programming

Competitive Programming

Advanced Course, 6 CP

Competitive Programming is the art of solving and implementing solutions to algorithmic problems in a time-constrained environment. Such problems usually need an algorithmic insight and efficient implementation to be solved successfully. This course will deal with general solution techniques as well as the algorithmic background knowledge to compete in programming contests. Since practice makes perfect, this course will include many tasks from previous competitions as hands-on exercises.

The best competitive programmers will qualify to participate in the Northwestern Europe Regional Contest (NWERC) in Reykjavik in November 2020, with all expenses paid.

Aside from preparing for competitions, the goal of this lecture is to improve programming ability and apply algorithms that are usually only taught theoretically.

Prerequisites

You should be able to program in C++ or Java. Code examples in the lecture will use C++.

Some knowledge of algorithms as taught in Grundzüge von Algorithmen und Datenstrukturen is an advantage.

You will need your own computer to attend lectures, solve problems on exercise sheets and participate in the exam. If you don't have access to a computer, please contact the lecture staff.

Course Preparation

Due to the current COVID-19 situation lectures will start on the 5th of May.

If you want to prepare for the lecture in the spare time, we recommend having a look at the book "Competitive Programming 3" which is available for registered students in our Materials section. If you already want to practice on some competitive programming tasks, you may have a look at the UVa Online Judge. The linked book recommends some problems on this website for each topic.
More problems can be found in the Codeforces problem set. Codeforces does also host competitive programming contests about once a week.

Dates

Lectures will start on the 5th of May.

Lecture: Tuesday 16:00-18:00 on Zoom

Tutorials:
- Wed. 16:00-18:00 (Central + Interactive)
- Fri. 10:00-11:00 (Interactive)
- Mon. 10:00-11:00 (Interactive)

Exams: 
- Midterm-Contest: 20. June 10:00
- Final: 29. July 09:00

Topics

These topics are preliminary and subject to change.

• Introduction to C++ for contests
• Basic algorithmic ideas
  • Brute-force
  • Backtracking
  • Greedy algorithms
  • Dynamic Programming
  • Divide & Conquer
• Dynamic Programming
• Graphs
  • Breadth-first search and depth-first search
  • Shortest paths
  • Topological sorting
  • Strongly connected components
  • Articulation points and bridges
  • Maximum Flow and Matching
• Trees
  • Lowest common ancestor
  • Minimal spanning tree
• Mathematical Basics
• Segment trees
• String algorithms
• Geometric problems

Weekly Exercises

There will be weekly exercises. Exercises will be purely practical and consist of a set of problems (usually about 4) that have to be solved, implemented and submitted. Solutions will be graded automatically against a set of test cases. Possible verdicts are Correct, Wrong Answer (your program produced wrong output), Time Limit Exceeded (your program took too long to compute an output) or general errors such as Compilation Error or Runtime Error. You are allowed to submit solutions for exercise sheets and exams in C++, Java, and Python.

Points will be awarded iff your solution is accepted as correct by our automated judge. You will need to reach 50% of all possible points to be admitted to the exam.

Exams

Exams will be practical contests. You will be given a set of problems where you have to find, implement, and submit a solution. Implementation will happen on a computer (with no internet connection), submissions will happen through a portal provided by us.