COV 886 : Spl Module in AlgorithmsSemester II 2017-2018Instructor: Sandeep Sen |
Venue : TBA
Prerequisites: CSL 356 (Algorithms) or equivalent, Basic Probability theory and Discrete Strcutures.
Course Outline
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. Preliminary Version
Small Dimensional Linear programming and Convex Hull Made Easy, R. Seidel
An elementary proof of a theorem of Johnson and Lindenstrauss Dasgupta and Gupta