COV 886 : Spl Module in Algorithms

Semester II 2017-2018

Instructor: Sandeep Sen

Lectures:

Wed 12 - 1:45 pm

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

Organization:

Grading will be based on a Final Exam (50%) and Assignments (50%) (subject to minor adjustments that will be discussed in class)

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

Lectures

  Lecture 1 (RIC : Closest Pair )
Lecture 2: A talk on randomized geometric algorithms

Assignment Sheet 1

Assignment Sheet 2

Notes taken by Shashwat Garg in a previous course

Final Exam with solutions

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

Sandeep Sen
Last modified: Mon Jan 12 2009