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 9: Relation of BSTs to Quicksort - Analysis of Random BST

• Lecture 10: Red-black Trees, Rotations, Insertions, Deletions

(Videos embedded below)

Readings

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

• After Lecture 9:
  • Section 12.4
• After Lecture 10:
  • Chapter 13
• Prior to Lecture 11 (originally for recitation):
  • Chapter 18

Other material

• Optional:
  • Peteris Krumins' comments and lecture notes for Lectures 9 and 10

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.

No assignment is due this week, but by the end of this week's readings you will be ready to complete Problem Set 4, which is due next week.

Videos

Lecture 9:

Lecture 10: