Hauptregion der Seite anspringen
TU Dresden — Fakultät Informatik — Institut für Theoretische Informatik

Randomized Algorithms (Summer 2025/26)

Algorithms that use randomness are often faster, easier to implement and easier to understand than deterministic algorithms, and in some cases, the only efficient algorithm we know for solving a problem is a randomized one. Understanding the role that randomness plays in computation is a great scientific question of our time. This course will survey various algorithmic techniques, covering different aspects of the use of randomness in computation.

Possible topics may include (but are not limited to): random sampling, random walks, randomized data structures, random graph models, minimum spanning trees and cuts in graphs, randomized verification, randomized geometric algorithms, randomized incremental construction, load balancing, pattern matching, the probabilistic method, Chernoff bounds, primality testing, isolation, ski-rental and paging, approximation and LP-rounding, randomized online algorithms.

(The course will be given in English.)

Prerequisites are basic knowledge of algorithms and relevant mathematics. All bachelor/master/diploma students interested in advanced algorithmic techniques are welcome. The lectures will be in English.

Organization

Lectures take place every Wednesday from 9:20 am to 10:50 am and every Thursday from 1 pm to 2:30 pm in APB/E005/U, starting April 15.

Tutorials take place every Wednesday from 11:10 am to 12:40 am in APB/E005/U, starting April 22.

Exercises and other material

Exercises, possible additional material and plan of topics will be uploaded as we go to this folder.

(Let me know if you cannot access the material for technical reasons.)

Literature

  1. Alon, N. and Spencer, J.H. 2008. The Probabilistic Method. Wiley-Interscience.
  2. Mitzenmacher, M. and Upfal, E. 2017. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press.
  3. Motwani, R. and Raghavan, P. 1995. Randomized Algorithms. Cambridge University Press.

Kontakt

Stand: 08.04.2026 01:00 Uhr