VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.
Randomized algorithms and probabilistic methods
Randomisierte Algorithmen und probabilistische Methoden
Last Updated: 2026-02-05 15:14:58
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
- English
- Levels
- BSC , DS , DR , MSC
- Frequency
- Yearly recurring
Examination
- Type
- end-of-semester examination
Course Components
| Type | Title | Time & Place | Hours |
|---|---|---|---|
| lecture | Randomisierte Algorithmen und probabilistische Methoden |
|
2 h weekly |
| exercise | Randomisierte Algorithmen und probabilistische Methoden |
|
1 h weekly |