Instructor: Nicole Wein (she/her)
Office Hours: Monday/Wednesday 3-4 (after lecture) at BBB 4624
GSI: Gary Hoppenworth (he/him)
Office Hours: Friday 3-5 at BBB 3956
Meeting times:
MW 1:30-3:00, BBB 1620: Lecture
Th 3:30-5:30, EWRE 185: Open Problem Session (optional)
Links:
Syllabus
Lecture Slides
Lecture Recordings
Homework
Piazza
Gradescope
Coauthor
Calendar
Wed 1/8 | Lecture 1: Introduction + Triangle Finding | |
Thurs 1/9 | NO open problem session | |
Mon 1/13 | Lecture 2: Cycle Finding | |
Wed 1/15 | Lecture 3: Hitting Sets | HW 1 released |
Thurs 1/16 | Open Problem Session 1 | |
Mon 1/20 | No Class (MLK Day) | |
Wed 1/22 | Lecture 4: Diameter Approximation | |
Thurs 1/23 | Open Problem Session 2 | |
Mon 1/27 | Lecture 5: Fine-Grained Complexity: Hardness of Diameter | |
Wed 1/29 | Lecture 6: More Fine-Grained Complexity: APSP and Negative Triangle | |
Thurs 1/30 | Open Problem Session 3 | |
Mon 2/3 | Lecture 7: Spanners | |
Tues 2/4 | HW 1 due | |
Wed 2/5 | Lecture 8: Distance Oracles | HW 2 released |
Thurs 2/6 | Open Problem Session 4 | |
Mon 2/10 | Lecture 9: Compact Routing | |
Wed 2/12 | Lecture 10: Shortcut Sets | |
Thurs 2/13 | Open Problem Session 5 | |
Mon 2/17 | Guest Lecture by Gary Hoppenworth (GSI): Probabilistic Tree Embedding | |
Wed 2/19 | Lecture 11: Dynamic Edge Orientation | |
Thurs 2/20 | Open Problem Session 6 | |
Mon 2/24 | Lecture 12: Dynamic Matching | |
Tues 2/25 | HW 2 due | |
Wed 2/26 | Lecture 13: More Dynamic Matching | HW 3 released |
Thurs 2/27 | Open Problem Session 7 | |
3/3-3/7 | No Class (Spring Break) | |
Mon 3/10 | Lecture 14: Dynamic Connectivity | |
Wed 3/12 | Lecture 15: Dynamic Connectivity Part 2 | |
Thurs 3/13 | Open Problem Session 8 | |
Mon 3/17 | Lecture 16: Hardness for Dynamic Problems | |
Tues 3/18 | HW 3 due | |
Wed 3/19 | Lecture 17: Parameterized Algorithms: Branching and Kernelization | HW 4 released |
Thurs 3/20 | Open Problem Session 9 | |
Mon 3/24 | Lecture 18: Color Coding | |
Wed 3/26 | Lecture 19: Treewidth | |
Thurs 3/27 | Open Problem Session 10 | |
Mon 3/31 | Lecture 20: Hardness for Parameterized Problems | |
Tues 4/1 | HW 4 due | |
Wed 4/2 | Lecture 21 (Bonus): c-Closed Graphs | HW 5 released |
Thurs 4/3 | Open Problem Session 11 | |
Mon 4/7 | Guest Lecture by Gary Hoppenworth (GSI): Graph Connectivity Preservers | |
Wed 4/9 | Lecture 22 (Bonus): Shortest Paths and Aspect Ratio | |
Thurs 4/10 | Open Problem Session 12 | |
Mon 4/14 | NO lecture | |
Tues 4/15 | HW 5 due | |
Wed 4/16 | NO lecture | |
Thurs 4/17 | Open Problem Session 13 | |
Mon 4/21 | NO lecture |