Old Announcements

  • OH Friday (2/24): 10:00-10:45
  • Notes on Ps4, problem 1: part c: the last line of first paragraph should end wit h: "let h(v) be this shortest distance from D to v" (NOT "from s to v").
  • Also, parts a-c are for a directed graph with edge weights, parts d and e refer to a flow network that also has non-negative edge costs. Also, part c uses a du mmy node D, part d has no such dummy node.
  • Revised Problem Set 4 Due Tuesday 2/21 2/15 /12
  • Revised PS4 (below): 1c) should be Prove that w'(i, j) = w(i, j) + h(i) - h(j) > = 0 for each edge (i, j) in G.
  • HW3 solutions posted under resources on smartsite.
  • Sample midterm and solutions now posted on Smartsite under resources.
  • Problem Set 3 PDF NOT TO BE TURNED IN
  • Global min-cut notes PDF (1/12)
  • Problem Set 1 Solutions are on smartsite.
  • REVISED problem set 2 below. (removed problem 4b).
  • Problem Set 2 PDF Due Friday Feb. 3, 3:45
  • Notes on an efficient algorithm for the sho rtest A-path Also, below under supplemental reading