CSE 5339 Algorithm design under a geometric lens
Spring, 2014.
Intructors:
Anastasios Sidiropoulos.
Time:
Wed Fri, 3:00-3:55pm.
Location:
Dreese Labs, Room 264.
Office hours:
Mon, 3:00-5:00pm, at Dreese Labs, Room 589.
Description
Large and complicated data sets have become ubiquitous in science and engineering. The analysis of such inputs has created new algorithmic challenges that cannot be addressed using classical techniques. This course will review some recent geometric tools that can be used to solve these problems. The topics that will be covered include:
-
Nearest-neighbor search (how to find similar items in a large data set).
-
Dimensionality reduction (how to reduce the number of attributes in a data base).
-
Clustering, and partitioning.
-
Metric embeddings (simplifying the geometry of data sets)
-
Spectral methods: Geometric methods for the analysis of graphs.
-
Geometric methods for manipulating strings: The geometry of edit distance.
Prerequisites
The course will be accessible to students with either a Computer Science / Engineering, or Mathematics background, having some basic knowledge of introductory algorithms, and probability theory. Some knowledge of graph theory, or geometry might be helpful, but will not be necessary. Programming experience is not required, although interested students will have the option of implementing some of the algorithms.
Lectures
-
Jan 8, 2014. Lecture 1: Introduction, metric spaces, metric embeddings.
Additional reading material:
-
Jan 10, 2014. Lecture 2: Random partitions.
Additional reading material:
-
Jan 15, 2014. Lecture 3: Random embeddings I.
Additional reading material:
-
Jan 17, 2014. Lecture 4: Random embeddings II.
-
Jan 22, 2014. Lecture 5: Embeddings into lp space I.
Additional reading material:
-
Jan 24, 2014. Lecture 6: Embeddings into lp space II.
-
Jan 29, 2014. Lecture 7: Bourgain's theorem.
-
Jan 31, 2014. Lecture 8: Dimensionality reduction.
Additional reading material:
-
Feb 5, 2014. Dimensionality reduction II.
Additional reading material:
-
Feb 7, 2014. Lecture 9: Nearest neighbor search I.
Additional reading material:
-
Feb 12, 2014. Lecture 10: Nearest neighbor search II.
-
Feb 14, 2014. Lecture 11: Doubling dimension I.
Additional reading material:
-
Feb 19, 2014. Lecture 12: Doubling dimension II.
-
Feb 21, 2014. Lecture 13: Clustering I.
Additional reading material:
-
Feb 26, 2014. Lecture 14: Clustering II.
-
Feb 28, 2014. Lecture 15: Clustering III. Project review.
-
Mar 5, 2014. Lecture 16: Earth-mover distance I.
Additional reading material:
-
Mar 7, 2014. Lecture 17: Earth-mover distance II.
-
Mar 19, 2014. Lecture 18: Minimum d-dimensional arrangement I.
Additional reading material:
-
Mar 21, 2014. Lecture 18: Minimum d-dimensional arrangement II.
-
Mar 26, 2014. Lecture 19: Cheeger's inequality I.
-
Mar 28, 2014. Lecture 20: Cheeger's inequality II.
-
Apr 2, 2014. Lecture by Luis Rademacher.
-
Apr 4, 2014. Lecture 21: Cheeger's inequality III.
-
Apr 9, 2014. Lecture by Alfred Rossi: Spectral partitioning and planar graphs.
Additional reading material:
Homework