VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.

251-0417-00L 5 Credits
You're viewing possible stale or outdated data. Please check the latest semester for more up-to-date information.

Randomized Algorithms

Randomisierte Algorithmen

Lecturers & Examiners: Prof. Dr. Angelika Steger
VVZ CR n/a

Last Updated: 2026-02-05 14:59:55

Abstract

Las-Vegas & Monte-Carlo alg., minimum cut, primality tests; inequalities of Markov, Chebyshev, Chernoff; comput. the median, balls and bins, routing in hypercubes, random walks on grids; Markov chains: gambler's ruin, 3SAT, convergence, rapidly mixing, generation vs. counting, self reducibile structures, permanent of a matrix; average case analysis: coloring graphs, knapsack problem

Content

Randomized Algorithms are algorithms that "flip coins" to take certain decisions. This concept extends the classical model of deterministic algorithms and has become very popular and useful within the last twenty years. In many cases, randomized algorithms are faster, simpler or just more elegant than determinictic ones. In the course, we will discuss basic principles and techniques and derive from them a number of randomized methods for problems in different areas.

Resources

Lecture Notes

Ja. Wird zu Beginn des Semesters verteilt.

Literature

R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press (1995).

General Information

Language
German
Frequency
Yearly recurring

Examination

Type
end-of-semester examination

Course Components

Type Title Time & Place Hours
lecture Randomisierte Algorithmen
  • Mon 10:15-12:00 (CAB G 61)
2 h weekly
exercise Randomisierte Algorithmen
  • Tue 13:15-14:00 (CAB H 53)
  • Tue 13:15-14:00 (CAB H 56)
  • Tue 14:15-15:00 (CAB H 53)
1 h weekly

Offered In