Introduction to Algorithms (MIT 6.046J)

Lectures

Lecture links to the MIT OCW site include the video or audio lecture itself in several formats, along with a transcript and a PDF set of lecture notes.

• Lecture 7: Hashing, Hash Functions

• Lecture 8: Universal Hashing, Perfect Hashing

(Videos embedded below)

Readings

All readings, unless otherwise specified, are from Introduction to Algorithms, 2nd Edition.

• After Lecture 7:
  • Sections 11.1-11.3
• After Lecture 8:
  • Section 11.5

Other material

• Optional:
  • Peteris Krumins' comments and lecture notes for Lectures 7 and 8

Assignment Notes

Assignments are listed under the Curious Reef "lesson" containing the lecture on which they were due, rather than the lesson containing the lecture when they were assigned.

There are 2 assignments due this week, but less reading than usual. Problem Set 2 (listed as Assignment 1) is based on material from the previous 2 weeks' worth of lectures. It was originally due during Lecture 7, on 9/3/2005. The second assignment, Problem Set 3, is based on this week's (short) reading. It was originally due during recitation on 9/7/2005.

Videos

Lecture 7:

Lecture 8: