CSL 863: Spl Topics in Algorithms Semester I 2014-2015 Instructors : Sandeep Sen and Amit Kumar

Lectures:

Venue : IIA 204

Prerequisites: CSL 356 (Algorithms) or equivalent, Basic Probability theory and Discrete Strcutures.

Course Outline

1.  Randomized Geometric algorithms and fundamentals  (15-20 hours)

  Randomized Incremental Construction (RIC), Computing Cuttings by
random sampling, epsilon-nets and approximations, VC dimensions and
applications to geometric optimization, Discrepancy, Derandomization

2. Data streaming: distinct elements, sketching, frequency moments, stable
distributions, lower bounds using communication complexity (10 hrs)

3. Random walks, rapid mixing and approximate counting (10 hrs)

Organization:

Reference books

Randomized Algorithms, R. Motwani and P. Raghavan, Cambridge

Computational Geometry: an Introduction through randomization, K. Mulmuley, Prentice Hall

Geometric Approximation Algorithms Sariel Har-Peled , AMS Series in Mathematical Surveys and Monographs. Preliminary Version

Link to Muthukrishnan's page on Streaming Algorithms including his book

Material related to lectures

Small Dimensional Linear programming and Convex Hull Made Easy, R. Seidel

An elementary proof of a theorem of Johnson and Lindenstrauss Dasgupta and Gupta

Assignments

Problem Set 1

Problem Set 2