### 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
• Ps2 clarification: For each problem you should justify the correctness of y our answer, and when providing a solution algorithm analyze the run time.
• A paper with extensive results on sports elimination numbers link
• PS1 solutions out on myucdavis class web page.
• Problem Set 2 PDF (10/10/08)
• correction to TA's email in the info sheet: smathews AT cs DOT ucdavis DOT edu
• Slides for lectures posted on other class web page.
• Class is being webcast, access for enrolled students only (for now)
• Two corrections to PS1: for problem 3. A) the array S is of size m; B) the run time should be O(mn) not m+n (which is not possible). pdf corrected below fo r B).
• Note that the room for this class has changed: It will be in 1062 Bainer ( a TV room)
• Problem Set 1 PDF (9/30/08)
• stuf from last class below
• link for baseball elmination and other optimization stuff
• useful link for graph algorithms
• Since we have a new book, lecture topics, and of course chapter pointers fro m prior quarters will change (some).
• The first 6 chapters of the book cover background topics which people shoul d already know (though I'm sure most will not have seen all the subtopics, and w e will look at several of the more advanced ones in chapter 6).
• Lectures are videotaped, and tapes for each day's lecture will be at 1101 H art Hall that evening by 6 pm. Students can view them there but are not allowed to take them home or make copies.
• We will be using a new book this year: Algorithm Design by Jon Kleinberg and Eva Tardos, ISBN: 0321295358