Randomized Algorithms and Probabilistic Methods

Aus VISki
Wechseln zu: Navigation, Suche

Overview

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.

Summaries

Exams

VIS Exam Collection (n.ethz login)

Additional Material

Literature

  • no literature here yet