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 19: Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson

[Video embedded below also]

• Lecture 20 / Quiz 2 Review: The second lecture period for this week was used to review for Quiz 2, a take-home quiz that will form the entirety next week's lesson. Unfortunately, there are no lecture notes, videos, or transcripts for this review period. Use this time to look over your notes, and check out the "Other Material" section below for a practice quiz and solutions.

Readings

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

• After Lecture 17:
  • Chapter 25

Other material

• Highly Recommended:
  • Practice Quiz with Solutions: The second quiz for this class is a "take-home" quiz, and next week's lesson is entirely dedicated to taking it. This week, though, I suggest working through the practice quiz and solutions and reviewing your notes in the time you would normally have spent on a second lecture and its associated readings.

• Optional:

  • Peteris Krumins' comments and lecture notes for Lectures 17, 18, and 19 (only the last part is relevant to this week's lecture)

Assignment Notes

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

Problem Set 8 is based on material from the previous week's worth of material. It was originally due during Lecture 19, on 11/21/2005.

Video

Lecture 19