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 8 Credits BSC , DS , DR , MSC , WBZ D-USYS , D-MTEC , D-BAUG , D-MAVT , D-INFK , D-MATH , D-PHYS , D-BIOL , D-ERDW , D-GESS , D-ITET , D-ARCH , D-CHAB

Randomized Algorithms and Probabilistic Methods

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

Last Updated: 2026-02-05 15:25:12

Abstract

Las-Vegas & Monte-Carlo alg; 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

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

Yes.

General Information

Language
English
Levels
BSC , DS , DR , MSC , WBZ
Frequency
Yearly recurring

Examination

Type
end-of-semester examination
Written Exam: December 18, 08.00-11.00, Open book exam, you are allowed to consult any books, handouts, and personal notes. The use of electronic devices is not allowed.Exercises: In week 4, 6, 8 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, and three best grades will each account for 10% of your final grade.

Course Components

Type Title Time & Place Hours
lecture Randomized Algorithms and Probabilistic Methods
  • Tue 13:15-14:00 (CAB H 57)
  • Thu 08:15-10:00 (CAB G 61)
  • 18.12 Date 07:15-12:00 (LFW E 11)
3 h weekly
exercise Randomized Algorithms and Probabilistic Methods
  • Tue 16:15-18:00 (CAB H 57)
2 h weekly

Offered In