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 17: Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search

• Lecture 18: Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints

[Videos embedded below also]

Readings

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

• After Lecture 17:
  • Section 22.2
  • Chapter 24
• Prior to Lecture 19 (originally for recitation):
  • Sections 22.3-22.4

Other material

• Optional:
  • Peteris Krumins' comments and lecture notes for Lectures 17, 18, and 19 (only the first 2 parts are relevant to this week's lectures)

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 7 is based on material from the previous week's worth of material. It was originally due during Lecture 17, on 11/14/2005.

Videos

Lecture 17

Lecture 18