Schedule

Please keep in mind that this is very preliminary and will change.

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
-- Cell-Chains
Wed Oct 18 Gary Lecture 21: Representing Topological Information and Decidability and Topology OldClassNotes -- Brisson-93 -- Cell-Chains
Fri Oct 20 Mid-Semester Break - No Class
Mon Oct 23 Gary Lecture 22: 2D-Closest Pair using Hashing OldClassNotes -- Har-Peled-Chap-1
Wed Oct 25 Gary Lecture 23: Approximate Nearest Neighbor OldClassNotes -- Har-Peled-Chap-17
Fri Oct 27 Gary Lecture 24: Approximate Nearest Neighbor Continued OldClassNotes -- Har-Peled-Chap-17
Mon Oct 30 Gary Lecture 25: 2D Mesh Generation: Quadtree OldClassNotes -- BKOS Chap 14 --Har-Peled-Chap-12
Wed Nov 01 Gary Lecture 26: Delaunay Refinement OldClassNotes -- Wikipedia Page
Fri Nov 03 Jakub Lecture 27: Homework 2 Presentations
Mon Nov 06 Gary Lecture 28: Delaunay Refinement II
Wed Nov 08 Gary Lecture 29: Delaunay Refinement III
Fri Nov 10 Gary Lecture 30: VC dimension and epsilon-nets OldClassNotes -- Har-Peled-Chap-5
Mon Nov 13 Gary Lecture 31: Homework 3 Presentations
Wed Nov 15 Gary Lecture 32: VC dimension and epsilon-nets II OldClassNotes -- Har-Peled-Chap-5
Fri Nov 17 Gary Lecture 33: VC dimension and epsilon-nets III OldClassNotes -- Har-Peled-Chap-5
Mon Nov 20 Gary Lecture 34: Bezier Curves and Bossoms OldClassNotes -- Chapter 3 -- Chapter 4 -- Chapter 5
Wed Nov 22 Thanksgiving Holiday - No Class
Fri Nov 24 Thanksgiving Holiday - No Class
Mon Nov 27 Gary Lecture 35: B-Splines OldClassNotes -- Chapter 8
Wed Nov 29 Gary Lecture 36: Recursive Subdivisions OldClassNotes -- Chapter 21 -- Evaluation of Loop
Fri Dec 01 Gary Lecture 37: Brunn-Minkowski OldClassNotes --Har-Peled-Chap-19
Mon Dec 04 Gary Lecture 38: Johnson Lindenstrauss OldClassNotes --Har-Peled-Chap-19
Wed Dec 06 Gary Lecture 39: Johnson Lindenstrauss OldClassNotes --Har-Peled-Chap-19
Fri Dec 08 Gary Lecture 40: Generating a Distribution: Exponential and Normal OldClassNotes