Spring 2007: Computational Geometry, 22C:196:005

In this course, we will discuss some of the algorithmic research work done over the past decade or so on the following themes:

If time permits, we will also talk about (a) results on embedding metrics into geometric spaces and their applications and (b) recent use of geometric ideas in approximately solving combinatorial optimization problems like sparsest cut.

The expectation from the students is that will they will (i) share in scribing notes of the lectures, (ii) solve two or three homeworks, and (iii) either (a) give a presentation at a time scheduled outside class hours, based on their understanding of some agreed upon research paper, or (b) implement and experimentally evaluate one or more of the algorithms for the problems we will discuss in class, and submit a report based on this work. All students in the course are not required, but are welcome, to attend student presentations that will be made outside class hours. The standards for (iii)(a) and (iii)(b) will be clarified at the beginning of the course.

Here is the schedule of talks.

If your talk is in B13, and you plan to use a projector, make sure that you can get one from the office and set it up with your laptop.