Schedule

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

>>> PDF Schedule <<<

Week 1

Tue 29-AugLecture 1: Linear-time Selection[Notes] [Slides] (complete)
Thu 31-AugLecture 2: Concrete Models and Lower Bounds [Notes] [Slides] (complete)
Homework 1 released[Homework 1]
Fri 01-SepRecitation 1: Lower Bounds[Recitation 1] [Solutions]

Week 2

Tue 5-SepLecture 3: Hashing, Universal and Perfect Hashing[Notes] [Slides] (complete)
Wed 8-SepHomework 1 due
Thu 7-SepLecture 4: Hashing Applications: Fingerprinting[Notes]
Homework 2 released[Homework 2]
Fri 08-SepRecitation 2: Hashing[Recitation 2] [Solutions]

Week 3

Tue 12-SepLecture 5: Amortized Analysis[Notes]
Wed 13-SepHomework 2 due
Thu 14-SepLecture 6: Union-Find and More Amortized Analysis[Notes]
Homework 3 released[Homework 3]
Fri 15-SepRecitation 3: Amortized Analysis[Recitation 3] [Solutions]

Week 4

Tue 19-SepLecture 7: Range Queries[Notes] [Slides] (complete)
Wed 20-SepHomework 3 orals
Thu 21-SepLecture 8: Splay Trees[Notes]
Homework 3 orals
Fri 22-SepRecitation 4: Range Queries and Splay Trees[Recitation 4] [Solutions]
Homework 3 orals

Week 5

Tue 26-SepLecture 9: Dynamic Programming I[Notes] [Slides] (complete)
Midterm One at 7:00pm
Thu 28-SepLecture 10: Dynamic Programming II[Notes] [Slides] (complete)
Homework 4 released[Homework 4]
Fri 29-SepRecitation 5: Dynamic Programming[Recitation 5] [Solutions]

Week 6

Tue 3-OctLecture 11: Depth-first search and biconnected components[Notes]
Thu 5-OctLecture 12: Network Flows I: Flows and Matchings[Notes]
Homework 4 due
Homework 5 released[Homework 5]
Fri 6-OctRecitation 6: Graphs and Network Flow[Recitation 6] [Solutions]

Week 7

Tue 10-OctLecture 13: Network Flows II: Advanced Flow Algorithms[Notes] [Slides] (complete)
Thu 12-OctLecture 14: Network Flows III: Minimum-cost Flows[Notes] [Slides] (complete)
Homework 5 due
Fri 6-OctRecitation 7: Advanced Flows[Recitation 7] [Solutions]

Fall Break

Mon 16-OctFall Break begins
Fri 20-OctFall Break end

Week 8

Homework 6 released[Homework 6]
Tue 24-OctLecture 15: Matrix Games[Notes]
Thu 26-OctLecture 16: Linear Programming I: Fundamentals[Notes] [Slides] (complete)
Fri 27-OctRecitation 8: Game Theory and Linear Programming[Recitation 8] [Solutions]

Week 9

Tue 31-OctLecture 17: Linear Programming II: Duality[Notes] [Slides] (complete)
Wed 1-NovHomework 6 orals
Thu 2-NovLecture 18: Linear Programming III: Polytopes, Simplex, Integrality[Notes] [Slides]
Homework 6 orals
Fri 3-NovRecitation 9: LP Duality and Polytopes[Recitation 9] [Solutions]
Homework 6 orals

Week 10

Tue 7-NovNo class (Democracy Day)
Thu 9-NovLecture 19: Approximation Algorithms[Notes]
Midterm Two at 7:00pm
Fri 10-NovRecitation 10: Approximation Algorithms[Recitation 10] [Solutions]

Week 11

Mon 13-NovHomework 7 released[Homework 7]
Tue 14-NovLecture 20: Online Algorithms [Notes]
Thu 16-NovLecture 21: Computational Geometry I: Intro[Notes] [Slides] (complete)
Fri 17-NovRecitation 11: Online Algorithms and Geometry[Recitation 11] [Solutions]

Week 12

Mon 20-NovHomework 7.5 (Programming) released[Homework 7.5]
Tue 21-NovLecture 22: Computational Geometry II: Randomized Incremental Algorithms[Notes] [Slides] [complete]
Homework 7 due
Wed 22-NovThanksgiving Break begins
Fri 24-NovThanksgiving Break ends

Week 13

Mon 27-NovHomework 8 released[Homework 8]
Tue 28-NovLecture 23: Computational Geometry III: Sweepline and Sweepangle [Notes]
Thu 30-NovLecture 24: Convolutions and their Applications [Notes]
Fri 17-NovRecitation 12: More Geometry and Convolutions[Recitation 12] [Solutions]

Week 14

Mon 4-DecHomework 7.5 (Programming) due
Tue 5-DecLecture 25: The Algorithmic Magic of Polynomials[Notes] [Slides]
Wed 6-DecHomework 8 orals
Thu 7-DecLecture 26: The Fast Fourier Transform[Notes] [Slides] (complete)
Homework 8 orals
Fri 8-DecRecitation 13: Polynomials and FFT[Recitation 13] [Solutions]
Homework 8 orals

Finals

Thu 14-DecFinal Exam at 8:30am

Course Calendar