Schedule

Please keep in mind that this is preliminary and may change.

Week 1

Tue 17-JanLecture 1: Linear-time Selection[notes] [slides] [video]
Homework 1 released[homework 1]
Thu 19-JanLecture 2: Concrete Models and Tight Upper/Lower Bounds [notes] [slides] [video] [extra video]

Week 2

Mon 23-JanRecitation 1: Recurrences and Lower Bounds[recitation 1] [solutions]
Tue 24-JanLecture 3: Amortized Analysis [notes] [slides] [video]
Wed 25-JanHomework 1 due
Thu 26-JanLecture 4: Splay Trees [notes] [video]
Homework 2 released[homework 2]

Week 3

Mon 30-JanRecitation 2: Amortized Analysis and Splay Trees [recitation 2] [solutions]
Tue 31-JanLecture 5: Hashing I: Universal and Perfect Hashing [notes] [slides] [video]
Wed 1-FebHomework 2 due
Thu 2-FebLecture 6: Range Query Data Structure [notes] [slides] [video]
Homework 3 released[homework 3]

Week 4

Mon 6-FebRecitation 3: SegTrees and Hashing[recitation 3] [solutions]
Tue 7-FebLecture 7: Hashing II: Streaming Algorithms [notes] [slides] [video]
Wed 8-FebHomework 3 orals
Thu 9-FebLecture 8: Hashing III: Fingerprinting and Other Applications [notes] [slides] [video]
Homework 3 orals
Fri 10-FebHomework 3 orals

Week 5

Mon 13-FebRecitation 4: Streaming and Fingerprinting[recitation 4] [solutions]
Tue 14-FebMidterm I
Thu 16-FebLecture 9: Dynamic Programming I [notes] [video]
Homework 4 released[homework 4]

Week 6

Mon 20-FebRecitation 5: Dynamic Programming[recitation 5] [solutions]
Tue 21-FebLecture 10: Dynamic Programming II [notes] [video]
Wed 22-FebHomework 4 due
Thu 23-FebLecture 11: Network Flows I: Flows and Matchings [notes] [slides] [video]
Homework 5 released[homework 5]

Week 7

Mon 27-FebRecitation 6: Dynamic Programming and Flows[recitation 6] [solutions]
Tue 28-FebLecture 12: Network Flows II [notes] [slides] [video]
Wed 1-MarHomework 5 due
Thu 2-MarLecture 13: Network Flows III [notes] [slides] [video]

Spring Break

Mon 6-MarSpring Break begins
Fri 10-MarSpring Break ends

Week 8

Mon 13-MarRecitation 7: More Flows[recitation 7]
Tue 14-MarLecture 14: Zero Sum Games [notes] [slides] [video]
Homework 6 released[homework 6]
Thu 16-MarLecture 15: Linear Programming I [notes] [video]

Week 9

Mon 20-MarRecitation 8: Zero Sum Games and LPs[recitation 8] [solutions]
Tue 21-MarLecture 16: Linear Programming II [notes] [video]
Wed 22-MarHomework 6 orals
Thu 23-MarLecture 17: Mechanism Design [notes] [slides] [video]
Homework 6 orals
Fri 24-MarHomework 6 orals

Week 10

Mon 27-MarRecitation 9: Mechanism Design and LP Duality [recitation 9]
Tue 28-MarMidterm II
Thu 30-MarLecture 18: Approximation Algorithms [notes] [slides] [video]
Homework 7 released[homework 7]

Week 11

Mon 3-AprRecitation 10: Approximation Algorithms[recitation 10]
Tue 4-AprLecture 19: Online Algorithms [notes] [slides] [video]
Wed 5-AprHomework 7 due
Thu 6-AprLecture 20: Multiplicative Weights Algorithm [notes] [slides] [video]
Homework 8 released[homework 8]

Week 12

Mon 10-AprRecitation 11: Online Algorithms[recitation 11]
Tue 11-AprLecture 21: Computational Geometry I: Geometric Primitives and Convex Hull [notes] [video (spring 23)] [video (spring 22)]
Wed 12-AprSpring Carnival begins
Sat 15-AprSpring Carnival ends

Week 13

Tue 18-AprLecture 22: Computational Geometry II: Sweepline and Sweepangle [notes] [video]
Wed 19-AprHomework 8 due
Thu 20-AprLecture 23: Computational Geometry III: Closest Pair and Smallest Enclosing Circle [notes] [SEC Slides] [video (spring 22)] [video (spring 23)]
Homework 9 released[homework 9]

Week 14

Mon 24-AprRecitation 13: More Computation Geometry / Final Review[recitation 13]
Tue 25-AprLecture 24: Fast Fourier Transform and Applications [notes] [Veritasium Video] [spr22 Lecture]
Wed 26-AprHomework 9 orals
Thu 27-AprLecture 25: The Algorithmic Magic of Polynomials [notes] [slides] [video]
Homework 9 orals
Fri 28-AprHomework 9 orals

Finals

Tue 2-MayFinal Exam

Course Calendar