COL870: Lecture Notes

  • Jan 05: Introduction

  • Jan 06: Data Representation, k-means

  • Jan 07: k-means

  • Jan 13: Center-based clustering (k-means/median/center)

  • Jan 15: Center-based clustering (k-means/median/center)
    • Please take a look at Sanjoy Dasgupta's course notes here for some of the material being covered in class.

  • Jan 20: Center-based clustering (k-means/median/center)

  • Jan 22: Center-based clustering (k-means/median/center)
    • Look at the following paper for the discussion on the use of bi-criteria approximation algorithm.
    • Look at the following paper for the discussion on k-mean++.

  • Jan 27: Center-based clustering (k-means/median/center)
    • See this and this for discussion on pseudo-approximation using sampling idea.

  • Jan 29: Center-based clustering (k-means/median/center)

  • Feb 03: Hierarchical Clustering

  • Feb 05: An Axiomatic Framework for Clustering
    • Link for the paper discussed in class.

  • Feb 10: Online and Streaming Clustering

  • Feb 12: Class cancelled
    • Minor-1 Exam

  • Feb 19: Coresets and Streaming algorithms

  • Feb 24: Ideas about coreset construction
    • A Link for the simple coreset construction discussed in class.

  • Feb 26: Gaussian Mixture Model

  • Mar 10: Johnson-Lindenstrauss Theorem
    • A Link for the paper discussed in class.

  • Mar 12: Dimensionality reduction, PCA
    • A Link for the material discussed in class.

  • Mar 17: Spectral analysis
    • A Link for lecture notes from Luca Trevisan.