Probability and Computing

Probability and Computing

MSc Lecture - Summer 2024

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

Description

The lecture will be held in English.

Probabilistic methods and randomness are a central topic in modern computer science. This lecture will cover recent and classic breakthroughs in computer science that rely on probability theory. Students should be already familiar with the basic tools and concepts of probability theory.

The topics of this lecture will include:

• Randomised algorithms
• The Markov chain Monte Carlo method
• The probabilistic method and the Lovász local lemma
• Random structures and phase transitions
• Discrete time stochastic processes

Organisation

The course will be organised via the Moodle of the Algorithm Engineering Chair. You can log in with your usual HPI-Login, and register for the course. Registration on the moodle page is required for all participants because the exercise sheets will be published and graded there.

Timeslots and venue:

• Mondays: 15:15-16:45 in HS3
• Wednesdays: 15:15-16:45 in HS3

Examination:

For examination, each student will give a 30 minute presentation and produce a written report on one topic of the course. The presentation counts for 50% of the final grade, and the report for 50%.

An average homework grade of at least 50% is required for students to participate in the final exam, but does not contribute towards the grade.

Requirements

Participants are expected to have basic knowledge of probability theory and an interest in rigorous analysis of algorithms.

Team

The seminar is offered by the Chair for Algorithm Engineering. The following people are involved: