19315401 Lecture

WiSe 16/17: Randomisierte Algorithmen

Wolfgang Mulzer, Paul Seiferth

Comments

The first class takes place on Tuesday, 18.10.2016.

Contents

  • Algorithms: linear programmimg, optimization, LP Rounding, satisfiability, routing, volume approximation, constructive local lemma, String search, randomized geometric algorithms (closest pair, minimum enclosing circle, ...), Johnson-Lindenstrauss, travels to cryptofantasia (differential privacy, homomorphic encryption, indistinguishability obfuscation)
  • data structures: Treaps, hash tables (universal, cuckoo, tabulation, two-Choice, Robin-Hood, ...), Bloom filter and Bloomier filter, nearest neighbor in high dimensions, range searching
  • Tools: concentration inequalities (Markov, Chebychev, Chernoff), Martingales, Markov-chains, coupling, hashing, fingerprinting, expander-graphs, Lovasz-local-lemma, Entropy, epsilon nets and VC dimension, backwards analysis, etc

Target Audience

M.S.-students in Computer Science, Mathematics or similar courses of study. Afterwards, you can obtain a topic for a Master thesis.

If desired, the class can be held in English.

Recommended Background

Basic knowledge in Mathematics and Theoretical Computer Science: discrete probability theory, discrete Mathematics, linear algebra, simple algebra and number theory, theory of algorithms, NP-completeness theory. More concretely: Contents of Mathematics for Computer Science, Theory of Computation, Algorithms and Data Structures, Advanced Algorithms

Website

http://www.inf.fu-berlin.de/lehre/WS16/RA/

close

Suggested reading

  • R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
  • M. Mitzenmacher, E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
close

32 Class schedule

Regular appointments

Tue, 2016-10-18 14:00 - 16:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/051 Seminarraum (Takustr. 9)

Tue, 2016-10-25 14:00 - 16:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/051 Seminarraum (Takustr. 9)

Tue, 2016-11-01 14:00 - 16:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/051 Seminarraum (Takustr. 9)

Tue, 2016-11-08 14:00 - 16:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/051 Seminarraum (Takustr. 9)

Tue, 2016-11-15 14:00 - 16:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/051 Seminarraum (Takustr. 9)

Tue, 2016-11-22 14:00 - 16:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/051 Seminarraum (Takustr. 9)

Tue, 2016-11-29 14:00 - 16:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/051 Seminarraum (Takustr. 9)

Tue, 2016-12-06 14:00 - 16:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/051 Seminarraum (Takustr. 9)

Tue, 2016-12-13 14:00 - 16:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/051 Seminarraum (Takustr. 9)

Tue, 2017-01-03 14:00 - 16:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/051 Seminarraum (Takustr. 9)

Tue, 2017-01-10 14:00 - 16:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/051 Seminarraum (Takustr. 9)

Tue, 2017-01-17 14:00 - 16:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/051 Seminarraum (Takustr. 9)

Tue, 2017-01-24 14:00 - 16:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/051 Seminarraum (Takustr. 9)

Tue, 2017-01-31 14:00 - 16:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/051 Seminarraum (Takustr. 9)

Tue, 2017-02-07 14:00 - 16:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/051 Seminarraum (Takustr. 9)

Tue, 2017-02-14 14:00 - 16:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/051 Seminarraum (Takustr. 9)

Fri, 2016-10-21 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/053 Seminarraum (Takustr. 9)

Fri, 2016-10-28 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/053 Seminarraum (Takustr. 9)

Fri, 2016-11-04 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/053 Seminarraum (Takustr. 9)

Fri, 2016-11-11 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/053 Seminarraum (Takustr. 9)

Fri, 2016-11-18 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/053 Seminarraum (Takustr. 9)

Fri, 2016-11-25 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/053 Seminarraum (Takustr. 9)

Fri, 2016-12-02 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/053 Seminarraum (Takustr. 9)

Fri, 2016-12-09 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/053 Seminarraum (Takustr. 9)

Fri, 2016-12-16 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/053 Seminarraum (Takustr. 9)

Fri, 2017-01-06 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/053 Seminarraum (Takustr. 9)

Fri, 2017-01-13 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/053 Seminarraum (Takustr. 9)

Fri, 2017-01-20 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/053 Seminarraum (Takustr. 9)

Fri, 2017-01-27 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/053 Seminarraum (Takustr. 9)

Fri, 2017-02-03 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/053 Seminarraum (Takustr. 9)

Fri, 2017-02-10 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/053 Seminarraum (Takustr. 9)

Fri, 2017-02-17 10:00 - 12:00

Lecturers:
Univ.-Prof. Wolfgang Mulzer
Paul Seiferth

Location:
T9/053 Seminarraum (Takustr. 9)

Subjects A - Z