Old Announcements
OH Friday (2/24): 10:0010: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 ac are for a directed graph with edge weights, parts d and e
refer to a flow network that also has nonnegative 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 mincut 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 Apath 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


Class Webcast 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