Schedule

Please keep in mind that future weeks are always preliminary and may change.

Links

Week 1

Tue 16-JanLecture 1: Introduction, Algorithm Analysis, Linear-time Selection [Notes] [Slides] [Further Review]
Thu 18-JanLecture 2: Concrete Models and Lower Bounds [Notes] [Slides] [Further Review]
Homework 1 released[Homework 1]
Fri 19-JanRecitation 1: Lower Bounds[Recitation 1] [Solutions]

Week 2

Tue 23-JanLecture 3: Integer Models and Integer Sorting [Notes] [Slides]
Wed 24-JanHomework 1 due[Solutions]
Thu 25-JanLecture 4: Hashing: Universal and Perfect Hashing [Notes] [Slides] [Further Review]
Homework 2 released[Homework 2]
Fri 26-JanRecitation 2: Integer Sorting and Hashing[Recitation 2] [Solutions]

Week 3

Tue 30-JanLecture 5: Fingerprinting [Notes] [Slides] [Further Review]
Programming 1 Released[Programming 1]
Wed 31-JanHomework 2 due[Solutions]
Thu 01-FebLecture 6: Amortized Analysis with Potential Functions† [Notes] [Slides] [Further Review]
Homework 3 released[Homework 3]
Fri 02-FebRecitation 3: Fingerprinting and Potential Functions[Recitation 3] [Solutions]
†Lecture recording missing audio. Try F22 instead.

Week 4

Tue 06-FebLecture 7: Union-Find (More Amortized Analysis!) [Notes] [Slides]
Wed 07-FebHomework 3 orals
Thu 08-FebLecture 8: Range Query Data Structures [Notes] [Slides] [Further Review]
Homework 3 orals
Fri 09-FebRecitation 4: Union-Find and SegTrees (Range Queries)[Recitation 4] [Solutions]
Programming 1 due
Homework 3 orals[Solutions]

Week 5

Tue 13-FebMidterm One at 7:00pm
Thu 15-Feb Lecture 9: Dynamic Programming [Notes] [Slides] [Further Review]
Homework 4 released[Homework 4]
Fri 16-FebRecitation 5: Dynamic Programming[Recitation 5] [Solutions]

Week 6

Tue 20-Feb Lecture 10: Dynamic Programming II [Notes] [Slides] [Further Review]
Programming 2 Released[Programming 2]
Thu 22-Feb Lecture 11: Network Flows I: Flows, Cuts, and Matchings [Notes] [Slides] [Further Review]
Homework 4 due[Solutions]
Homework 5 released[Homework 5]
Fri 23-FebRecitation 6: Network Flow[Recitation 6] [Solutions]

Week 7

Tue 27-FebLecture 12: Network Flows II: Advanced Flow Algorithms [Notes] [Slides] [Further Review]
Wed 28-FebHomework 5 due[Solutions]
Thu 29-Feb Lecture 13: Network Flows III: Minimum-cost Flows [Notes] [Slides] [Further Review]
Fri 01-MarRecitation 7: Advanced Flow[Recitation 7] [Solutions]
Programming 2 due

Spring Break!

Mon 04-MarSpring Break begins
Fri 08-MarSpring Break ends

Week 8

Tue 12-MarLecture 14: Game Theory (alt. video) [Notes] [Slides] [Further Review]
Programming 3 released[Programming 3]
Thu 14-MarLecture 15: Linear Programming I: Fundamentals (alt. video) [Notes] [Slides] [Further Review]
Homework 6 released[Homework 6]
Fri 15-MarRecitation 8: Game Theory and Linear Programming[Recitation 8] [Solutions]

Week 9

Tue 19-MarLecture 16: Linear Programming II: Seidel's Algorithm (alt. video) [Notes] [Slides] [Further Review]
Wed 20-MarHomework 6 orals
Thu 21-MarLecture 17: Linear Programming III: Duality (alt. video) [Notes] [Slides] [Further Review]
Homework 6 orals
Fri 22-MarRecitation 9: LP Duality and Algorithms[Recitation 9] [Solutions]
Homework 6 orals[Solutions]
Programming 3 due

Week 10

Tue 26-MarMidterm Two at 7:00pm
Thu 28-MarLecture 18: Approximation Algorithms [Notes] [Slides] [Further Review]
Homework 7 released[Homework 7]
Fri 29-MarRecitation 10: Approximation Algorithms[Recitation 10] [Solutions]

Week 11

Tue 02-AprLecture 19: Online Algorithms [Notes] [Slides] [Further Review]
Programming 4 released[Programming 4]
Wed 03-AprHomework 7 due[Solutions]
Thu 04-AprLecture 20: Streaming Algorithms [Notes] [Slides] [Further Review]
Homework 8 released[Homework 8]
Fri 5-AprRecitation 11: Online and Streamling Algorithms[Recitation 11] [Solutions]

Week 12

Tue 09-AprLecture 21: Computational Geometry I: Fundamentals [Notes] [Slides] [Further Review]
Wed 10-AprHomework 8 due
Homework Bonus released[Homework Bonus]
Programming 4 due
Thu 11-AprSpring Carnival begins
Sat 13-AprSpring Carnival ends

Week 13

Tue 16-AprLecture 22: Computational Geometry II: Incremental Algorithms [Notes] [Slides] [Further Review]
Programming 5 released[Programming 5]
Thu 18-AprLecture 23: Polynomials in Algorithm Design [Notes] [Slides] [Further Review]
Homework 9 released[Homework 9]
Fri 19-AprRecitation 12: Computation Geometry[Recitation 12] [Solutions]

Week 14

Tue 23-AprLecture 24: The Fast Fourier Transform [Notes] [Slides] [Further Review]
Wed 24-AprHomework 9 orals
Thu 25-AprLecture 25: Online Learning (The Multiplicative Weights Algorithm) [Notes] [Slides] [Further Review]
Homework 9 orals
Fri 26-AprRecitation 13: Polynomials, FFT, Online learning[Recitation 13] [Solutions]
Homework 9 orals
Programming 5 due

Finals

Tue 30-AprFinal Exam at 5:30pm