COV 886 : Spl Module in Algorithms
Semester II 2017-2018
Instructor: Sandeep Sen
Venue : TBA
Prerequisites: CSL 356 (Algorithms) or equivalent, Basic Probability theory and Discrete Strcutures.
1. Randomized Geometric algorithms and fundamentals (14 hours = 7 X 2hrs) Randomized Incremental Construction (RIC), Computing Cuttings by random sampling, epsilon-nets and approximations, VC dimensions and applications to geometric optimization, Discrepancy, Derandomization
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.
Lecture 1 (RIC : Closest Pair )
Lecture 2: A talk on randomized geometric algorithms
Small Dimensional Linear programming and Convex Hull Made Easy, R. Seidel
An elementary proof of a theorem of Johnson and Lindenstrauss Dasgupta and Gupta