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/
closeSuggested 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.
32 Class schedule
Regular appointments
Tue, 2016-10-18 14:00 - 16:00
Tue, 2016-10-25 14:00 - 16:00
Tue, 2016-11-01 14:00 - 16:00
Tue, 2016-11-08 14:00 - 16:00
Tue, 2016-11-15 14:00 - 16:00
Tue, 2016-11-22 14:00 - 16:00
Tue, 2016-11-29 14:00 - 16:00
Tue, 2016-12-06 14:00 - 16:00
Tue, 2016-12-13 14:00 - 16:00
Tue, 2017-01-03 14:00 - 16:00
Tue, 2017-01-10 14:00 - 16:00
Tue, 2017-01-17 14:00 - 16:00
Tue, 2017-01-24 14:00 - 16:00
Tue, 2017-01-31 14:00 - 16:00
Tue, 2017-02-07 14:00 - 16:00
Tue, 2017-02-14 14:00 - 16:00
Fri, 2016-10-21 10:00 - 12:00
Fri, 2016-10-28 10:00 - 12:00
Fri, 2016-11-04 10:00 - 12:00
Fri, 2016-11-11 10:00 - 12:00
Fri, 2016-11-18 10:00 - 12:00
Fri, 2016-11-25 10:00 - 12:00
Fri, 2016-12-02 10:00 - 12:00
Fri, 2016-12-09 10:00 - 12:00
Fri, 2016-12-16 10:00 - 12:00
Fri, 2017-01-06 10:00 - 12:00
Fri, 2017-01-13 10:00 - 12:00
Fri, 2017-01-20 10:00 - 12:00
Fri, 2017-01-27 10:00 - 12:00
Fri, 2017-02-03 10:00 - 12:00
Fri, 2017-02-10 10:00 - 12:00
Fri, 2017-02-17 10:00 - 12:00
Contents
Algorithms: linear programmimg, optimization, LP Rounding, satisfiability, routing, volume approximation, ... read more