Course Syllabus

Tue/Thu: 1045-1205. WEB L114

Course Mechanics

• 80%: 5-6 Assignments (please read the homework policy)
• 20%: Project (read the project guidelines). 

Policies

• School of Computing Academic Policies Links to an external site.
• College of Engineering Guidelines Links to an external site.

Lectures

• Core Geometric Objects
• (1/11-1/8) Convex Hulls I: Convexity, representation of convex hulls, the gift-wrapping algorithm, divide-and-conquer, Chan's optimal algorithm, linear classification.  Notes Download Notes
  . 
  • Assignment 1 due Jan 29. 
• (1/18-1/25):  Voronoi Diagrams. Notes Download Notes
  .
• (1/30-2/6): Delaunay Triangulations Links to an external site. (Mount, starting at page 74)
• (2/6-2/20): Arrangements, duality and sweep-line algorithms.
• Data Structures
• (2/27) Range trees & kd-trees Links to an external site. (Mount, starting at page 48)
• (3/1) Quad trees (Har-Peled, Chapter 2 Links to an external site.)
• (3/6) Well-separated pair decompositions (Har-Peled, Chapter 3 Links to an external site.)
• Sampling and Learning (Har-Peled, Chapter 5 Links to an external site.)
• VC dimension
• epsilon-nets and epsilon-samples
• discrepancy-based constructions
• High Dimensional Geometry
• SVDs, PCA and MDS
• Random projections Links to an external site. (and an application to clustering Links to an external site.)
• Near neighbors (see these nice Euclidean LSH notes Links to an external site., and this for the main LSH resource page Links to an external site.)
• Core sets and extents (see Chapter 23 from this book Links to an external site.)
• The Geometry of Learning
• Kernels and Hilbert spaces Links to an external site.
• Support Vector Machines
• The graph Laplacian
• Bregman Divergences. 
• Polyhedra and Optimization
  • Polyhedra
  • Linear programming (2D linear programming Links to an external site.)
  • Simplex Links to an external site. and Ellipsoid Links to an external site. methods