Competitive Programming Markus Bläser, Karl Bringmann, Christoph Weidenbach Advanced Lecture, 6 CP, Summer Semester 2020

News

31.07.2020

Final Exam: Results & Exam Inspection

The results of the final exam and your grade are now available on your personal status page.

If you have any questions regarding your exam please come to our virtual exam inspection on Wednesday, 05.08. from 10:00AM to 12:00 (noon) on our Discord-Server.

28.07.2020

Exam: Final Remarks

The exam will take place tomorrow at 9:00 AM in the Günter-Hotz-Lecture Hall (E2.2). Please enter the lecture hall through the back entrances, and fill the lecture hall from front to back and from the middle of the rows to the outer seats. Also, please only take... Read more

The exam will take place tomorrow at 9:00 AM in the Günter-Hotz-Lecture Hall (E2.2). Please enter the lecture hall through the back entrances, and fill the lecture hall from front to back and from the middle of the rows to the outer seats. Also, please only take seats that have a printed exam at their table.

You have to bring your laptop with you. For further information consider https://cms.sic.saarland/cp20/3/Exams.

Please note the following:
If your answer is "yes" to one or more of the following questions, then you are not allowed to attend the exam. If you provide a doctor’s certificate to the examination office later on, the examination attempt will be canceled and will not count.

Did you have definite contact with a Covid-19 patient, who was tested positive, in the last 14 days?
Do you have any of the following symptoms?
▪️ Cough / Husten
▪️ Sore throat / Halsschmerzen
▪️ Nasal congestion / runny nose / Schnupfen
▪️ Diarrhoea / Durchfall
▪️ Fever / Fieber
▪️ Aches and pains / Gliederschmerzen
▪️ Loss of smell (e.g. no longer able to smell burnt food) / Geruchsverlust
▪️ Loss of taste (e.g. unable to distinguish when food is burnt) / Geschmacksverlust

27.07.2020

Cheat-Sheet: Deadline Extension

Due to popular request, we have re-opened the submission for the cheat-sheet. If you did not do so yet: Please submit your cheat-sheet until 28.07. (tomorrow) 13:00. 

25.07.2020

Exam: Room & Remarks

The exam on Wednesday will take place in the Günter-Hotz Lecture Hall. Please enter the lecture hall from the back entrances (i.e. the two entrances far from the blackboard). Further information about the exam can be found at ... Read more

The exam on Wednesday will take place in the Günter-Hotz Lecture Hall. Please enter the lecture hall from the back entrances (i.e. the two entrances far from the blackboard). Further information about the exam can be found at https://cms.sic.saarland/cp20/3/Exams.

All registered students must consider the following information:
You are registered for the exam Competitive Programming. Please note that it is absolutely necessary for you to bring your own protection mask with you. Students who have a doctor’s certificate that they cannot wear protection masks have to bring their own face shields and wear these instead of a mask.

21.07.2020

Exams & Tutorial & Evaluation

Please consider the remarks about the exam at https://cms.sic.saarland/cp20/3/Exams. Note that you have to register until tomorrow (22.07.) to take part in the exam.

Tomorrow (22.07.) at 16:00 an exam preparation tutorial will take place in the usual Zoom... Read more

Please consider the remarks about the exam at https://cms.sic.saarland/cp20/3/Exams. Note that you have to register until tomorrow (22.07.) to take part in the exam.

Tomorrow (22.07.) at 16:00 an exam preparation tutorial will take place in the usual Zoom meeting. We will discuss solutions for the midterm exam as well as for the exam preparation sheet.

Please take part in the course evaluation. You can find the link to it in the materials section.

06.07.2020

Midterm Exam: Results

The results of the midterm exam are now available on your personal status page. 

The midterm will contribute with a maximum of 10% to your final grade. Bonus points are interpolated linearly between 0 and 100 points. The formula (<points>/10)% indicates how many... Read more

The results of the midterm exam are now available on your personal status page. 

The midterm will contribute with a maximum of 10% to your final grade. Bonus points are interpolated linearly between 0 and 100 points. The formula (<points>/10)% indicates how many bonus points you have reached for the final or re-exam.

There will be no dedicated exam inspection. If you have any questions regarding your correction, please visit the office hours.  

19.06.2020

Midterm: Final Remarks

The midterm will take place tomorrow, June 20, at 10am (CEST) sharp.
Please join the Lecture Zoom meeting before 10am.

We now assume that all of you can boot the virtual machine, connect to the VPN and use the judge from within the VM without any problems.
You... Read more

The midterm will take place tomorrow, June 20, at 10am (CEST) sharp.
Please join the Lecture Zoom meeting before 10am.

We now assume that all of you can boot the virtual machine, connect to the VPN and use the judge from within the VM without any problems.
You may already download your cheatsheet from https://compro.mpi-inf.mpg.de/cheatsheet inside the VM when connected to the VPN.

The judge will be disabled for all external traffic starting this evening until after the exam.
During this timespan, you will only be able to access the judge when connected to the VPN through your virtual machine.
Note that it will be impossible to submit solutions to the current exercise sheet in this timeframe.

11.06.2020

Contest VM: Installation

We have released the Contest VM. Please find the installation instructions here.

Make sure to install the VM enough time (at least a few days) ahead of the Midterm-Contest.

05.06.2020

Contest VM: Software Requests

Please have a look at the Software request for the Contest VM forum post. If you want to have any additional software installed, please reply to this post until 06. June 23:59.

We will provide the virtual machine next week. Therefore, you should have enough time... Read more

Please have a look at the Software request for the Contest VM forum post. If you want to have any additional software installed, please reply to this post until 06. June 23:59.

We will provide the virtual machine next week. Therefore, you should have enough time for installing the VM and testing your setup.

12.05.2020

Second Lecture & First Tutorial

Reminder: The second lecture will take place today at 16:00 (sharp). All further lectures will begin at 16:00 sharp.

The first central tutorial will start tomorrow at 16:00 (sharp) in the same Zoom room that is used for the lecture.

04.05.2020

First Lecture

The first lecture will take place tomorrow at 16:00 (sharp). It will be held via Zoom, you can find the meeting information at the Materials page.

Show all
 

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.



Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators