CSE 291: Geometric algorithms

Time
TuTh 3.30-5 in CSE 2154

Instructors:
Sanjoy Dasgupta and Mohan Paturi
Office hours for Sanjoy: Wed 3-5 in CSE 4138
Office hours for Mohan: TBA

Syllabus and administrative details

Topics covered:

• 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

1. The k-center clustering problem (Apr 2)
2. The k-median problem (Apr 4)
3. Algorithms for k-means clustering (Apr 9,11)
4. Online and streaming algorithms for clustering (Apr 16,18,23)
5. Hierarchical clustering (Apr 25)

Topic 2: Population recovery

Topic 3: Nearest-neighbor search