Announcements
- A poll was posted on Piazza asking students to report how much time Problem Set 1 took, so the workload can be monitored
0:00. - The scribe slot for September 30 (a week from Tuesday) became vacant and needs a volunteer; students with later slots may swap earlier
0:16. - The videographer is open to requests about how the blackboard is framed in the recordings
0:16. - Two bugs in the notes were fixed: an off-by-one in cuckoo hashing, and the previously unproved lemma for the power-of-two-choices result
0:38.
Where the course goes next
- The course leaves the word RAM model behind, at least for now
1:02. - New theme: amortized analysis, applied to data structures
1:02. - Planned structures: binomial heaps (as the stepping stone), Fibonacci heaps, and later splay trees
1:02,1:34. - Prerequisite assumption: students who took CS 124 have seen a little amortized analysis via union-find; the lecture goes further
1:34.