19315401 Lecture

SoSe 19: Advanced Topics in Algorithms

László Kozma

Additional information / Pre-requisites

Target Audience

Masters students in Computer Science or Mathematics, advanced Bachelor students.

Prerequisites

"Advanced Algorithms" or a similar class

Comments

Randomized algorithms

The word "random" often has negative connotations: if something is random, then it may be unpredictable, unprecise, noisy, erratic, difficult to understand. It is therefore surprising that randomness is of great help in algorithmic problem-solving. Algorithms that use randomness are often more efficient, easier to implement and easier to understand than their deterministic counterparts, and in some cases, the only efficient method we know for solving a problem is a randomized one. Randomness can also be viewed as a useful (and often limited) computational resource, similarly to time and space usage. Understanding the exact role that randomness plays in computation is one of the great scientific questions of our time.

This course will survey various algorithmic techniques, covering different aspects of the use of randomness in computation. Topics include (but are not limited to): randomized binary search trees, hashing-based data structures, random sampling, random walks, linear-time minimum spanning trees, cuts in graphs, verifying matrix multiplication, predicting the future with the help of experts, geometric algorithms, randomized incremental construction, load balancing, pattern matching, the probabilistic method, Chernoff bounds, primality testing, isolation, online algorithms, ski-rental and paging, approximation and LP-rounding.

(The course will be given in English.)

close

Suggested reading

[MR] R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995

[MU] M. Mitzenmacher, E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005

[CLRS] T. H. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, MIT Press 2009

[KT] J. Kleinberg, E. Tardos. Algorithm Design, Addison-Wesley 2005.

[M] J. Matoušek. Lectures in Discrete Geometry. Springer Verlag, 2002

close

27 Class schedule

Regular appointments

Tue, 2019-04-09 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Tue, 2019-04-16 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Tue, 2019-04-23 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Tue, 2019-04-30 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Tue, 2019-05-07 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Tue, 2019-05-14 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Tue, 2019-05-21 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Tue, 2019-05-28 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Tue, 2019-06-04 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Tue, 2019-06-11 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Tue, 2019-06-18 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Tue, 2019-06-25 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Tue, 2019-07-02 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Tue, 2019-07-09 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Thu, 2019-04-11 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Thu, 2019-04-18 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Thu, 2019-04-25 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Thu, 2019-05-02 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Thu, 2019-05-09 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Thu, 2019-05-16 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Thu, 2019-05-23 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Thu, 2019-06-06 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Thu, 2019-06-13 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Thu, 2019-06-20 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Thu, 2019-06-27 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Thu, 2019-07-04 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Thu, 2019-07-11 10:00 - 12:00

Lecturers:
Prof. Dr. László Kozma

Location:
T9/055 Seminarraum (Takustr. 9)

Subjects A - Z