CSL 863: Spl Topics in AlgorithmsSemester I 2014-2015Instructors : Sandeep Sen and Amit Kumar |
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)
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
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