Probability and Computing (Sommersemester 2018)

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

General Information

• Weekly Hours: 4
• Credits: 6
• Graded: yes
• Enrolment Deadline: 30.04.2018
• Teaching Form: Lecture / Exercise
• Enrolment Type: Compulsory Elective Module
• Maximum number of participants: 30

Programs, Module Groups & Modules

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 A-2.2.
• Wednesdays: 9:15-10:45 in A-1.1.

Zurück