CSE 291: Geometric algorithms
TuTh 3.30-5 in CSE 2154
Sanjoy Dasgupta and Mohan Paturi
Office hours for Sanjoy: Wed 3-5 in CSE 4138
Office hours for Mohan: TBA
Syllabus and administrative details
- Clustering in metric spaces: approximation algorithms for k-center, k-median, k-means; online and streaming models; hierarchical clustering.
- Planted partition problems: spectral methods for planted bisections and for mixtures of Gaussians, semirandom instances.
- Nearest neighbor search: metric space methods, Euclidean methods.
- Other geometric proximity problems: reductions and complexity results.
Course requirements: There will be periodic homework assignments as well as a final project.
Lecture schedule, homework assignments, and optional accompanying readings
Topic 1: Clustering
- The k-center clustering problem (Apr 2)
- The k-median problem (Apr 4)
- Algorithms for k-means clustering (Apr 9,11)
- Online and streaming algorithms for clustering (Apr 16,18,23)
- Hierarchical clustering (Apr 25)
Topic 2: Population recovery
Topic 3: Nearest-neighbor search