| Date |
Day |
Notes |
|
| 1 |
8/27 |
Mon |
Intro -- the art gallery theorem For the first part of the class, you can find supplementary materials here. |
| 2 |
8/30 |
Thu |
optimization version of the art
gallery problem its hardness covering problems, greedy set cover |
| 9/3 |
Mon |
No class -- Labor Day |
|
| 3 |
9/6 |
Thu |
No class due to CDI workshop on
campus |
| 4 |
9/10 |
Mon |
randomized rounding set cover |
| 5 |
9/13 |
Thu |
Project proposals
are due geometric instanes of covering: Approximation schemes for covering and packing problems in image processing and VLSI |
| 6 |
9/17 |
Mon |
sampling and vc dimension epsilon net theorem |
| 7 |
9/20 |
Thu |
covering when the VC-dimension
is small |
| 8 |
9/24 |
Mon |
covering when the VC-dimension is small |
| 9 |
9/27 |
Thu |
project background presentation:
Nikhil |
| 10 |
10/01 |
Mon |
project background presentation:
Nikhil (cont) follow-up: Volkan |
| 11 |
10/04 |
Thu |
project background presentation:
Onur |
| 10/08 |
Mon |
No Class |
|
| 12 |
10/09 |
Tue |
School follows a monday schedule project background presentation: Wei |
| 13 |
10/11 |
Thu |
project background presentation:
Chris |
| 14 |
10/15 |
Mon |
range searching and point location |
| 15 |
10/18 |
Thu |
voronoi diagrams |
| 16 |
10/22 |
Mon |
dynamic programming |
| 17 |
10/25 |
Thu |
Watchman's route problem |
| 18 |
10/29 |
Mon |
convex hulls and delaunay triangulations |
| 19 |
11/1 |
Thu |
k-center, k-means etc. |
| 20 |
11/5 |
Mon |
Geometric Spanners |
| 21 |
11/8 |
Thu |
spanners (cont) |
| 22 |
11/12 |
Mon |
online algorithms |
| 23 |
11/15 |
Thu |
intro to game theory |
| 24 |
11/19 |
Mon |
Pursuit evasion on graphs |
| 11/22 |
Thu |
No Class -- Thanksgiving |
|
| 25 |
11/26 |
Mon |
project presentation: Chris and Wei |
| 26 |
11/29 |
Th |
Take-home final out project presentation: Onur and Nikhil |
| 27 |
12/3 |
Mon |
Take-home final due Concluding Remarks |