Probability and Computing (Sommersemester 2018)

Dozent: Prof. Dr. Tobias Friedrich (Algorithm Engineering) , Dr. Andreas Göbel (Algorithm Engineering)
Website zum Kurs: https://hpi.de/friedrich/teaching/ss18/probcomp.html

Allgemeine Information

• Semesterwochenstunden: 4
• ECTS: 6
• Benotet: Ja
• Einschreibefrist: 30.04.2018
• Lehrform: Vorlesung / Übung
• Belegungsart: Wahlpflichtmodul
• Maximale Teilnehmerzahl: 30

Studiengänge, Modulgruppen & Module

Beschreibung

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.

Voraussetzungen

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.

Literatur

The main textbook is ``Probability and Computing'' by Mitzenmacher and Upfal.

Leistungserfassung

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.

Termine

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

Zurück