Course Material and Schedule

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

Links

Week 1

Tue 27-AugLecture 1: Introduction, Algorithm Analysis, Linear-time Selection [Notes] [Slides]
Thu 29-AugLecture 2: Concrete Models and Lower Bounds [Notes] [Slides]
Homework 1 released[Homework 1]
Fri 30-AugRecitation 1: Lower Bounds[Recitation 1] [Solutions]

Week 2

Tue 3-SepLecture 3: Integer Models and Integer Sorting [Notes] [Slides]
Wed 4-SepHomework 1 due[Solutions]
Thu 5-SepLecture 4: Hashing: Universal and Perfect Hashing [Notes] [Slides]
Homework 2 released[Homework 2]
Fri 6-SepRecitation 2: Integer Sorting and Hashing[Recitation 2] [Solutions]

Week 3

Tue 10-SepLecture 5: Fingerprinting [Notes] [Slides]
Programming Problem 1 Released[Programming 1]
Wed 11-SepHomework 2 due[Solutions]
Thu 12-SepLecture 6: Range Query Data Structures [Notes] [Slides]
Homework 3 released[Homework 3]
Fri 13-SepRecitation 3: Fingerprinting and SegTrees[Recitation 3] [Solutions]

Week 4

Tue 17-SepLecture 7: Amortized Analysis [Notes] [Slides]
Wed 18-SepHomework 3 orals
Thu 19-SepLecture 8: Union-Find (More Amortized Analysis!) [Notes] [Slides]
Homework 3 orals
Fri 20-SepRecitation 4: Amortized Analysis and Union Find[Recitation 4] [Solutions]
Homework 3 orals[Solutions]
Programming Problem 1 due

Week 5

Tue 24-SepMidterm One at 7:00pm
Thu 26-Sep Lecture 9: Dynamic Programming [Notes] [Slides]
Homework 4 released[Homework 4]
Fri 27-SepRecitation 5: Dynamic Programming[Recitation 5] [Solutions]

Week 6

Tue 1-Oct Lecture 10: Dynamic Programming II [Notes] [Slides]
Programming Problem 2 Released[Programming 2]
Wed 2-OctHomework 4 due[Solutions]
Thu 3-Oct Lecture 11: Network Flows I: Flows, Cuts, and Matchings† [Notes] [Slides]
Homework 5 released[Homework 5]
Fri 4-OctRecitation 6: Network Flow[Recitation 6] [Solutions]
†Lecture recording missing audio. Consider watching last semester's recording.

Week 7

Tue 8-OctLecture 12: Network Flows II: Advanced Flow Algorithms [Notes] [Slides]
Wed 9-OctHomework 5 due[Solutions]
Thu 10-Oct Lecture 13: Network Flows III: Minimum-cost Flows [Notes] [Slides]
Fri 11-OctRecitation 7: Advanced Flow[Recitation 7] [Solutions]
Programming Problem 2 due

Fall Break!

Mon 14-OctFall Break begins
Fri 18-OctFall Break ends

Week 8

Tue 22-OctLecture 14: Game Theory [Notes] [Slides]
Programming Problem 3 Released[Programming 3]
Thu 24-OctLecture 15: Linear Programming [Notes] [Slides]
Homework 6 released[Homework 6]
Fri 25-OctRecitation 8: Game Theory and LPs[Recitation 8] [Solutions]

Week 9

Tue 29-OctLecture 16: Linear Programming II: Duality [Notes] [Slides]
Wed 30-OctHomework 6 orals
Thu 31-OctLecture 17: Linear Programming III: Polytopes and Integrality [Notes] [Slides]
Homework 6 orals
Fri 1-NovRecitation 9: More Linear Programming[Recitation 9] [Solutions]
Homework 6 orals[Solutions]
Programming Problem 3 due

Week 10

Tue 5-NovMidterm Two at 7:00pm
Thu 7-Nov Lecture 18: Approximation Algorithms [Notes] [Slides]
Homework 7 released[Homework 7]
Fri 8-NovRecitation 10: Approximation Algorithms[Recitation 10] [Solutions]

Week 11

Tue 12-NovLecture 19: Online Algorithms [Notes] [Slides]
Programming Problem 4 Released[Programming 4]
Wed 13-NovHomework 7 due[Solutions]
Thu 14-NovLecture 20: Streaming Algorithms [Notes] [Slides]
Homework 8 released[Homework 8]
Fri 15-NovRecitation 11: Online and Streaming Algorithms[Recitation 11] [Solutions]

Week 12

Tue 19-NovLecture 21: Computational Geometry [Notes] [Slides]
Wed 20-NovHomework 8 due[Solutions]
Thu 21-NovLecture 22: Computation Geometry II: Randomized Incremental Algorithms [Notes] [Slides]
Homework 9 released[Homework 9]
Fri 22-NovRecitation 12: Computational Geometry[Recitation 12] [Solutions]
Programming Problem 4 due

Week 13

Tue 26-NovLecture 23: Computational Geometry III: Sweepline[Notes] [Slides] [Demo]
Wed 27-NovThanksgiving Break begins
Fri 29-NovThanksgiving Break ends

Week 14

Tue 3-DecLecture 24: The Algorithmic Magic of Polynomials[Notes] [Slides]
Wed 4-DecHomework 9 orals
Thu 5-DecLecture 25: The Fast Fourier Transform[Notes] [Slides]
Homework 9 orals
Fri 6-DecRecitation 13: Polynomials and FFT[Recitation 13] [Solutions]
Homework 9 orals[Solutions]

Finals

Tue 10-DecFinal Exam at 5:30pm