| Day | Date | Instr | Topics Covered | Notes and Readings |
|---|---|---|---|---|
| Mon | Aug 28 | Gary | Lecture 1: Short Class for Introductions | |
| Wed | Aug 30 | No Class Yet - No Class | ||
| Fri | Sep 01 | Gary | Lecture 2: Preclass lecture on linear algebra | [ClassNotes] pdf -note |
| Mon | Sep 04 | Labor Day - No Class | ||
| Wed | Sep 06 | Gary | Lecture 3: Introduction, The Line Intersection Problem using Sweepline | [ClassNotes]
pdf
-note -- BKOS Chap 2 -- Intro Notes -- SweepLine Notes |
| Fri | Sep 08 | Gary | Lecture 4: Backwards Analysis of QuickSort: 2D Convex Hull: Reduction from sorting; Divide-and-Conquer |
[ClassNotes-Backwards Analysis]
pdf
-note [ClassNotes] pdf -note -- 2D Convex Notes |
| Mon | Sep 11 | Gary | Lecture 5: 2D Convex Hull: Random Incremental | 2D Convex Notes |
| Wed | Sep 13 | Gary | Lecture 6: 2D-LP and Random Incremental | [ClassNotes]
pdf
-note -- BKOS Chap 4 |
| Fri | Sep 15 | Gary | Lecture 7: 2D-LP and Random Incremental Continued & Checking for Unboundedness | |
| Mon | Sep 18 | Gary | Lecture 8: Geometric Transforms | [ClassNotes]
pdf
-note -- Doru Balcan's Notes |
| Wed | Sep 20 | Gary | Lecture 9: Geometric Transforms Continued | |
| Fri | Sep 22 | Gary | Lecture 10: Planar Point Location; Trapezoidation | [ClassNotes]
pdf
-note BKOS Chap 6 [Mount Chap 9 & 10 ] |
| Mon | Sep 25 | Gary | Lecture 11: Planar Point Location; Trapezoidation Continued | [ClassNotes]
pdf
-note BKOS Chap 6 [Mount Chap 9 & 10 ] |
| Wed | Sep 27 | Gary | Lecture 12: Traps and Chernoff Bounds | [ClassNotes]
pdf
-note BKOS Chap 6 [Mount Chap 9 & 10 ] |
| Fri | Sep 29 | Gary | Lecture 13: Triangulating a Polygon | [ClassNotes]
pdf
-note BKOS Chap 3 |
| Mon | Oct 02 | Gary | Lecture 14: Radon, Carathéodory, and Helly's Theorems | [ClassNotes]
pdf
-note -- Gil Kalai's Blog |
| Wed | Oct 04 | Gary | Lecture 15: Radon, Carathéodory, and Helly's Theorems Continued | [ClassNotes]
pdf
-note -- Gil Kalai's Blog |
| Fri | Oct 06 | Gary | Lecture 16: Centerpoints and Approximate Centerpoints | [ClassNotes]
pdf
-note -- Paper |
| Mon | Oct 09 | Gary | Lecture 17: Colorful Carathéodory and Tverberg Partition | [ClassNotes]
pdf
-note -- Gil Kalai's Blog -- Related Reading |
| Wed | Oct 11 | Gary | Lecture 18: Homework 1 Presentations | |
| Fri | Oct 13 | Gary | Lecture 19: Homework 1 Presentations continued | |
| Mon | Oct 16 | Gary | Lecture 20: Representing Topological Information | [ClassNotes]
pdf
-note -- Brisson-93 -- Cell-Chains |
| Wed | Oct 18 | Gary | Lecture 21: Representing Topological Information | |
| Fri | Oct 20 | Mid-Semester Break - No Class | ||
| Mon | Oct 23 | Gary | Lecture 22: 2D-Closest Pair using Hashing | [ClassNotes]
pdf
-note -- Har-Peled-Chap-1 |
| Wed | Oct 25 | Gary | Lecture 23: Quadtrees | [ClassNotes]
pdf
-note -- Har-Peled-Chap-2 |
| Fri | Oct 27 | Tim | Lecture 24: Well Separated Pairs Decomposition | [ClassNotes] -- Har-Peled-Chap-3 |
| Mon | Oct 30 | Tim | Lecture 25: Well Separated Pairs Decomposition Continued | [ClassNotes] -- Har-Peled-Chap-3 |
| Wed | Nov 01 | Gary | Lecture 26: Approximate Nearest Neighbor Continued | [ClassNotes]
pdf
-note -- Har-Peled-Chap-17 |
| Fri | Nov 03 | Gary | Lecture 27: 2D Mesh Generation: Quadtree | [ClassNotes]
pdf
-note -- BKOS Chap 14 --Har-Peled-Chap-12 |
| Mon | Nov 06 | Gary | Lecture 28: 2D Mesh Generation: Quadtree Contin. | [ClassNotes]
pdf
-note -- BKOS Chap 14 --Har-Peled-Chap-12 |
| Wed | Nov 08 | Gary | Lecture 29: Delaunay Refinement | [ClassNotes]
pdf
-note -- Wikipedia Page |
| Fri | Nov 10 | Gary | Lecture 30: Delaunay Refinement II | |
| Mon | Nov 13 | Gary | Lecture 31: Delaunay Refinement III | |
| Wed | Nov 15 | Timothy | Lecture 32: Homework 2-3 Presentations | |
| Fri | Nov 17 | Gary | Lecture 33: VC dimension | [ClassNotes]
pdf
-note -- Har-Peled-Chap-5 |
| Mon | Nov 20 | Gary | Lecture 34: VC dimension II | -- Har-Peled-Chap-5 |
| Wed | Nov 22 | Thanksgiving Holiday - No Class | ||
| Fri | Nov 24 | Thanksgiving Holiday - No Class | ||
| Mon | Nov 27 | Gary | Lecture 35: VC, epsilon-samples and epsilon-nets | [ClassNotes]
pdf
-note -- Har-Peled-Chap-5 |
| Wed | Nov 29 | Gary | Lecture 36: Bezier Curves and Bossoms | ClassNotes] [pdf -note -- Chapter 3 -- Chapter 4 -- Chapter 5 |
| Fri | Dec 01 | Gary | Lecture 37: B-Splines | [ClassNotes]
pdf
-note -- Chapter 8 |
| Mon | Dec 04 | Gary | Lecture 38: Brunn-Minkowski | ClassNotes] [pdf -note --Har-Peled-Chap-19 |
| Wed | Dec 06 | Gary | Lecture 39: Johnson Lindenstrauss | notes : >
[ClassNotes]
pdf
-note --Har-Peled-Chap-19 |
| Fri | Dec 08 | Gary | Lecture 40: Johnson Lindenstrauss | OldClassNotes --Har-Peled-Chap-19 |