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

News

30.09.2022

Re-Exam: More information

Dear students,

as promised, some more information about the re-exam:

  • The re-exam will take place on 05.10. at 14:00 in the Günter-Hotz lecture hall (E2 2).
  • Please read through our exam guide carefully. In particular, make sure to test your setup... Read more

Dear students,

as promised, some more information about the re-exam:

  • The re-exam will take place on 05.10. at 14:00 in the Günter-Hotz lecture hall (E2 2).
  • Please read through our exam guide carefully. In particular, make sure to test your setup again.
  • Students that cannot register in LSF: please register in CMS until 04.10. 14:00. If you are already registered in LSF your registration status in CMS should be registered as well automatically.
  • If you need a spare laptop for the re-exam: Contact us as soon as possible.

 

28.09.2022

Re-Exam: Registration

Dear students,

the re-exam is approaching fast. Please register in LSF today until midnight if you want to participate.

You can submit a new cheat-sheet for the re-exam. Submission is possible until 04.10. at 14:00.

More details about the exam will follow... Read more

Dear students,

the re-exam is approaching fast. Please register in LSF today until midnight if you want to participate.

You can submit a new cheat-sheet for the re-exam. Submission is possible until 04.10. at 14:00.

More details about the exam will follow in the next days.

04.08.2022

Exam: Results & Inspection

Dear students,

the exam results are now available. You can see your points as well as the overall grade on your personal status page.
Bonus points from the midterm are automatically applied iff you passed the exam (i.e. achieved >= 40 points without any... Read more

Dear students,

the exam results are now available. You can see your points as well as the overall grade on your personal status page.
Bonus points from the midterm are automatically applied iff you passed the exam (i.e. achieved >= 40 points without any bonus).

If you have any questions about your exam please visit our exam inspection tomorrow (Friday, 05.07.) from 10:00–11:00 on our Discord server. In case you cannot make it tomorrow, please let us know via E-Mail.

02.08.2022

Exam: Final Remarks

Dear students,

the exam is taking place tomorrow in the Günter-Hotz lecture hall (E2.2). The exam will start at 10:00. Please arrive by 09:45 at latest. Do not forget to bring your student ID and a laptop with the VM set up.

The online judge will not be... Read more

Dear students,

the exam is taking place tomorrow in the Günter-Hotz lecture hall (E2.2). The exam will start at 10:00. Please arrive by 09:45 at latest. Do not forget to bring your student ID and a laptop with the VM set up.

The online judge will not be available from this evening until the exam tomorrow.

27.07.2022

Exam, Solutions & Office Hour

Dear students,

the exam is approaching fast. Please read thoroughly through our exam notes. In particular, note that you must register for the exam until today (27.07.).

As there were no tutorials for Exercise Sheet 11, we uploaded solution slides instead to... Read more

Dear students,

the exam is approaching fast. Please read thoroughly through our exam notes. In particular, note that you must register for the exam until today (27.07.).

As there were no tutorials for Exercise Sheet 11, we uploaded solution slides instead to the CMS. Furthermore, we uploaded solution spoilers for the sample final exam.

If you have any questions or problems with your setup for the exam, we offer an additional Office Hour tomorrow (28.07.) at 16:00-16:30 online on our Discord. Furthermore, you can always contact us via E-Mail.

20.06.2022

GCPC & No tutorials this week

Dear students,

the GCPC (German Collegiate Programming Contest) will take
place this Saturday, 25. June. The most important points about the GCPC are:

  • The GCPC is a team competition: Participants need to solve competitive programming problems in teams of... Read more

Dear students,

the GCPC (German Collegiate Programming Contest) will take
place this Saturday, 25. June. The most important points about the GCPC are:

  • The GCPC is a team competition: Participants need to solve competitive programming problems in teams of 3, while only having one computer available.
  • Problems in the contest should be very similar to the exercises for this lecture.
  • The contest starts at 11:00 and lasts 5 hours.
  • We will provide pizza for the participants.

Registration is possible until Thursday (23.06.) right after the lecture. In case you already have a team, please enter a team name on your personal status page (this name should be equal for all members). Otherwise, we will try to build teams from lone participants. If you have any further questions, please contact Julian.

Lastly, there will be no tutorials this week. The lecture will take place as usual on Thursday. Tutorials will take place regularly the next week.

13.06.2022

Midterm: Results and Inspection & Exercise Sheet 7

Dear students,

the results for the Midterm exam are published on your personal status page. If you correctly solved a (sub-)task, you should see full points for the (sub-)task there. We reviewed all last incorrect submissions and awarded partial points in case of... Read more

Dear students,

the results for the Midterm exam are published on your personal status page. If you correctly solved a (sub-)task, you should see full points for the (sub-)task there. We reviewed all last incorrect submissions and awarded partial points in case of a correct idea or only minor errors in the code.

We offer an exam inspection for the midterm on Wednesday, 15.06. at 10:00 (our usual Office-Hour slot). Please come if you have any questions about your submissions or the grading.

Furthermore, we have released Exercise Sheet 7. This exercise sheet deals with the contents of lecture 7. It is due on Thursday, 23.06. at 16:00 (right before the next lecture).

Lastly, remember that this Thursday (16.06.) is a public holiday, and there will be no lecture this week. Next week (20. and 21.06.) there will also be no tutorials.

07.06.2022

Cheatsheet: Deadline extension

Due to the CMS outage on the weekend, the deadline for the cheat sheet submission has been moved to Wednesday, June 8th (i.e. tomorrow) evening (23:59).

Note that the registration deadline for the midterm is still today.

07.06.2022

Midterm, Office Hours & Judge downtime

Dear students,

the registration and cheatsheet deadline for the Midterm exam is today at 23:59.

In case of any problems: We are offering an extra Office Hour today at 14:15 in E1.3 SR014 in addition to our regular Office Hour tomorrow at 10:00 (online).

Our... Read more

Dear students,

the registration and cheatsheet deadline for the Midterm exam is today at 23:59.

In case of any problems: We are offering an extra Office Hour today at 14:15 in E1.3 SR014 in addition to our regular Office Hour tomorrow at 10:00 (online).

Our online judge will have a planned downtime from tomorrow in the late afternoon until shortly before the exam. Please check that you can reach the judge from your VM beforehand. Also, if you want to submit any solutions for past exercise sheets, please do this until tomorrow afternoon.

01.06.2022

Installation of VM & Troubleshooting & Exam Info

Dear students,

to participate in the exams, you need to install a custom virtual machine. Installation should be done as soon as possible. Please follow the installation instructions here.

If you encounter any difficulties while installing the VM, we offer an... Read more

Dear students,

to participate in the exams, you need to install a custom virtual machine. Installation should be done as soon as possible. Please follow the installation instructions here.

If you encounter any difficulties while installing the VM, we offer an extra Office Hour tomorrow from 15:00-15:45 (before the lecture). The office hour will take place in E1.3 SR0.16.

To participate in the midterm exam, please read the exam guide here. In particular, you have to register on your personal status page. Also, you can submit your cheat sheet there. Further information regarding the exams will be announced in the next lecture.

22.04.2022

Tutorials assigned & Exercise Sheet 2

Dear students,

you now can see your assigned tutorial on your personal status page. Tutorials will start next week (from 25.04. onwards). Please note that the tutorial on Mondays will start at 16:00 sharp, whereas the Tuesday tutorials will start... Read more

Dear students,

you now can see your assigned tutorial on your personal status page. Tutorials will start next week (from 25.04. onwards). Please note that the tutorial on Mondays will start at 16:00 sharp, whereas the Tuesday tutorials will start at 14:15.

During the tutorials, sample solutions for the past exercise sheets will be presented. Furthermore, we will discuss debugging and testing techniques and you will be given extra competitive programming tasks to train.

The exercises for week 2 have also been released. You can switch between different weeks on the judge system by using the button in the upper right corner.

13.04.2022

First lecture

Dear students,

the Competitive Programming lecture will start tomorrow (Thursday, 14.04.) at 16:00 s.t. / sharp in HS002, E1.3. We will also broadcast the lecture via Zoom. The link to join the meeting is available in the materials section. The lecture will also... Read more

Dear students,

the Competitive Programming lecture will start tomorrow (Thursday, 14.04.) at 16:00 s.t. / sharp in HS002, E1.3. We will also broadcast the lecture via Zoom. The link to join the meeting is available in the materials section. The lecture will also be recorded and uploaded afterwards.

Show all
 

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++, Java, 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: Thursdays 16:00-18:00 on-site in HS002, E1.3.
Lectures will likely be live-streamed and recorded as well if technically possible.

 

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++, Java, Python and Rust (to be confirmed).

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 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), submission is possible through a portal provided by us.



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