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
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
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
- 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
- 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,