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 13: Amortized Algorithms, Table Doubling, Potential Method

• Lecture 14: Competitive Analysis: Self-organizing Lists

[Videos embedded below also]

Readings

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

• After Lecture 13:
  • Chapter 17
• After Lecture 14:
  • Sleator, Daniel D., and Robert E. Tarjan. "Amortized efficiency of list update and paging rules." Communications of the ACM 28, no. 2 (February 1985): 202-208.] (PDF from Daniel Sleator's site)

Other material

• Optional:
  • Peteris Krumins' comments and lecture notes for Lectures 13 and 14

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.

Problem Set 5 is based on material from the previous week's worth of material. It was originally due during Lecture 13, on 10/31/2005.

Videos

Lecture 13:

Lecture 14: