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
Remaining schedule coming soon...