People: Prof. Dr. Tobias Friedrich, Dr. Andreas Göbel
Links: Courses IT-Systems Engineering, Algorithm Engineering Moodle (TBA)

This lecture will be held in English and consists of of two parts.

The first part is a general introduction to the topic of probability theory. We will look at concentration barriers (such as Chernobi barriers) and general techniques for estimating probabilities (for example, Bernoulli's inequality).

The second part examines the use of randomness in Algorithms. Topics include.

• How algorithms can use randomness to make decisions that improve their run-time.
• How well algorithms perform when given a random input.
• Analysis of random structures.

The course requires mathematical curiosity, interest in solving riddles and basic understanding of mathematical notation and language. In particular, the ability to understand and use Landau notation (O notation) and basic knowledge of algorithm design and analysis. No knowledge in probabilities is required as this will be introduced completely in the lecture.

Students will be given homework weekly. The successful hand in of homework is required for students to participate in the final exam. The full grade is determined by the final exam (plus bonus points from the exercises), which will be a take-home exam with oral examination.

• Mondays: 13:30-15:00 in A-2.2.
• Wednesdays: 9:15-10:45 in A-1.1.