News
Deadline Extension Exercise Sheet 5Written on 11.05.26 by Yasmine Melina Briefs Dear students, as you might have noticed, our online judge is currently down. We hope to bring it back up soon. To give you more time to work on the problems, we have decided to extend the deadline for exercise sheet 5 to next Monday, May 18 at 23:59. Although the judge is down, you can still find… Read more Dear students, as you might have noticed, our online judge is currently down. We hope to bring it back up soon. To give you more time to work on the problems, we have decided to extend the deadline for exercise sheet 5 to next Monday, May 18 at 23:59. Although the judge is down, you can still find the exercise sheet in the CMS and work on the tasks already now. |
Tutorial MergeWritten on 05.05.26 by Yasmine Melina Briefs Dear students, due to low attendence, we have decided to merge our tutorials. Your timeslot stays the same, just the room might have changed. All 10:15 tutorials now take place in SR 016 in E1.3 and all 16:15 tutorials now take place in SR 015 in E1.3. You can also find your tutorial room on your… Read more Dear students, due to low attendence, we have decided to merge our tutorials. Your timeslot stays the same, just the room might have changed. All 10:15 tutorials now take place in SR 016 in E1.3 and all 16:15 tutorials now take place in SR 015 in E1.3. You can also find your tutorial room on your personal status page. We encourage you to attend the tutorials and to upsolve all problems on the exercise sheet that you weren't able to complete before. |
Tutorial AssignmentWritten on 09.04.26 (last change on 09.04.26) by Yasmine Melina Briefs Dear students, we have assigned the tutorials. You can find your tutorial on your personal status page. Tutorials start on Tuesday next week (April 14). In the tutorials, we will use Codeforces for additional practice. In preparation for the first tutorial, you can already create an account… Read more Dear students, we have assigned the tutorials. You can find your tutorial on your personal status page. Tutorials start on Tuesday next week (April 14). In the tutorials, we will use Codeforces for additional practice. In preparation for the first tutorial, you can already create an account on Codeforces and join our group. We prepared instructions on how to use Codeforces here: https://cms.sic.saarland/cp26/4/Codeforces. |
Competitive Programming
Advanced Course, 6 CP
Competitive Programming is the art of solving algorithmic problems and implementing solutions in a time-constrained environment. Such problems usually need insight into algorithms 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.
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 write basic programs in C++, Python or Rust. 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 laptop to solve problems on exercise sheets and participate in the exam. If you don't have access to a laptop, please contact the lecture staff.
Course Preparation
If you want to prepare for the course, 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 also hosts competitive programming contests about once a week.
Dates
Lectures: Wednesday 14:00 ct. in the Günter-Hotz lecture hall (E2.2).
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
- Finding subgraphs
- Trees
- Lowest common ancestor
- Minimal spanning tree
- Mathematical Basics
- Segment trees
- String algorithms
- Parsing
- 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++, Python and Rust.
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. Internet/LLM usage for exercise sheets is strongly discouraged, but not forbidden.
Exams
Exams are practical contests. You are given a set of problems where you have to find, implement, and submit a solution. Exam solutions are implemented on your computer (inside of a VM provided by us with no internet connection or LLM access), submission is possible through a portal provided by us. More information on the exams and grading can be found here.