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/