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 Classes (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 (your GSI) | |
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: Hardness for Dynamic Problems | |
Thurs 3/13 | Open Problem Session 8 | |
Mon 3/17 | Lecture 16: Parameterized Algorithms: Branching and Kernelization | |
Tues 3/18 | HW 3 due | |
Wed 3/19 | Lecture 17: Color Coding | HW 4 released |
Thurs 3/20 | Open Problem Session 9 | |
Mon 3/24 | Lecture 18: Treewidth | |
Wed 3/26 | Lecture 19: Hardness for Parameterized Problems | |
Thurs 3/27 | Open Problem Session 10 | |
Mon 3/31 | TBD | |
Tues 4/1 | HW 4 due | |
Wed 4/2 | TBD | HW 5 released |
Thurs 4/3 | Open Problem Session 11 | |
Mon 4/7 | TBD | |
Wed 4/9 | TBD | |
Thurs 4/10 | Open Problem Session 12 | |
Mon 4/14 | TBD | |
Tues 4/15 | HW 5 due | |
Wed 4/16 | TBD | |
Thurs 4/17 | Open Problem Session 13 | |
Mon 4/21 | TBD |