# Probability and Computing (Sommersemester 2019)

Lecturer: Prof. Dr. Tobias Friedrich (Algorithm Engineering) , Dr. Andreas Göbel (Algorithm Engineering)
Course Website: https://hpi.de/en/friedrich/teaching/ss19/probability-and-computing.html

## General Information

• Weekly Hours: 4
• Credits: 6
• Teaching Form: Lecture / Exercise
• Enrolment Type: Compulsory Elective Module
• Course Language: English
• Maximum number of participants: 30

## Programs & Modules

IT-Systems Engineering MA
Data Engineering MA
• DATA-Konzepte und Methoden
• DATA-Techniken und Werkzeuge
• DATA-Spezialisierung
• SCAL-Konzepte und Methode
• SCAL-Techniken und Werkzeuge
• SCAL-Spezialisierung

## Description

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.

## Requirements

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.

## Literature

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

## Examination

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.

## Dates

• Mondays: 13:30-15:00 in HS1
• Wednesdays:  11:00-12:30 in HS1

Zurück