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

252-0417-00L 10 Credits BSC , DZ , SHE , DR , MSC , WBZ D-ITET , D-INFK , D-MATH
You're viewing possible stale or outdated data. Please check the latest semester for more up-to-date information.

Randomized Algorithms and Probabilistic Methods

Lecturers & Examiners: Prof. Dr. Angelika Steger
VVZ CR 3.4

Last Updated: 2026-02-05 15:48:27

Abstract

Las Vegas & Monte Carlo algorithms; inequalities of Markov, Chebyshev, Chernoff; negative correlation; Markov chains: convergence, rapidly mixing; generating functions; Examples include: min cut, median, balls and bins, routing in hypercubes, 3SAT, card shuffling, random walks

Objective

After this course students will know fundamental techniques from probabilistic combinatorics for designing randomized algorithms and will be able to apply them to solve typical problems in these areas.

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 deterministic 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

Yes.

Literature

- Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press (1995) - Probability and Computing, Michael Mitzenmacher and Eli Upfal, Cambridge University Press (2005)

General Information

Language
English
Levels
BSC , DZ , SHE , DR , MSC , WBZ
Frequency
Yearly recurring

Examination

Type
end-of-semester examination
Mode
written 180 minutes
Aids
None
Exercises 30% to the final grade (compulsory continuous performance assessments): In week 4, 7 and 10 of the term (roughly) we will hand out a specially marked exercise, whose solution (typeset in LaTeX or similar) is due two weeks later. These solutions will be graded; the grades will each account for 10% of the final grade.End of term: written exam accounting for 70% of the grade; open book exam: you are allowed to consult any books, handouts, and personal notes. The use of electronic devices is not allowed.

Course Components

Type Title Time & Place Hours
lecture Randomized Algorithms and Probabilistic Methods
  • Wed 08:15-09:00 (ML D 28)
  • Thu 16:15-18:00 (ML D 28)
3 h weekly
exercise Randomized Algorithms and Probabilistic Methods
  • Tue 14:15-16:00 (HG D 1.2)
  • Tue 16:15-18:00 (HG D 1.2)
2 h weekly
independent project Randomized Algorithms and Probabilistic Methods
Project Work, no fixed presence required.
No time listed 4 h weekly

Offered In