Recitation: Thursday, February 22 at 9:30AM (Monday Schedule)
Lecture 9: Tuesday, February 20
More IRVs (resuming at the hat-check problem). Division method for hashing. Open addressing. Brief description of Universal hashing and Perfect hashing.
Reading: Section 15
and section 13.2.
Universal and perfect hashing are not in the course notes and will not be on the exam. If interested see the textbook.
Exam 1: Thursday, February 15
Please be 5-minutes early, if possible.
Please use the entire auditorium, and leave one empty seat between you and your neighbor on each side.
Lecture 8: Tuesday, February 13
Intro to hashing / Chaining / Simple uniform hashing. Intro to expectation / IRVs.
Reading: Section 13.1 (the end, on "choosing hash functions", is FYI. However, CLRS Theorem 11.2 will be discussed in detail).
Section 15 (up to page 33 of full notes)
Recitation: Monday, February 12
Exam review.
Lecture 7: Thursday, February 8
Counting sort and Radix sort. And possibly Strassen's algorithm.