ECS 222B - Winter 2008 Advanced Algorithms
Announcements
- Finals week OH: Tuesday 18th 11-12; Thursday 20th 1-2:30
- Graded problem set 5 available. Stop by to pick it up
-
- Problem Set 5 Solutions, pdf , 3/18
-
- Monday 3/10: Guest lecture, the first topic will be taken from
``The Perfect Phylogeny Problem" by D. Fernandez-Baca, which is
a survey paper in the book ``Steiner Trees in Industry" and
available at
http://www.cs.iastate.edu/~fernande/pubs.html
-
- Ps5 solutions (in latex), if you have trouble dealing with this, send me email and I can send you a pdf version
- Problem Set 5 Solutions, latex , 3/9
-
- Extra OH Wed. 12:45-1:45. No OH Friday.
-
- PS5 notes: for 4.2 you can assume min-cuts are computed in the original graph (though it also works to compute them in the new graph). Also, for 4.4 you may use result 4.1 of the prior problem. Note a typo in equation 4.1 (in older editions): should be f(u,v) >= ... (NOT, f(u,w) >= ...)
-
- Problem Set 5 Due March 7 , 2/27
-
- Problem Set 4 solutions , 2/27
-
-
- Chapter 4 discusses the gomory-hu tree to represent all min-cuts. a nice improvement on this is in: Very Simple Methods for all Pairs Network Flow analysis, by Dan Gusfield. SIAM J. on computing, Vol. 19, 1, pp. 143-55, 1990.
-
- Min-cost flow notes (from MIT class)
-
-
Old Announcements
Clarification for PS4, problem 4, iii): The basic goal in iii) is different
from ii). You only want a schedule of length 1, and in that first time unit you want a set of job's that use as much of resource 1 as possible
(after time 1 you don't care what happens).
Clarifications on problem 3.2 in the text: i) graph is undirected. ii) paths between senders and recievers need not be disjoint (just some path for each reciever, and not all senders need to be connected).
NOTE: typo in 3a of the problem set. Your goal is to "find a clique of size at least k" (not "at most k").
The web site below has some powerpoint slides (lecture 7 link) on a variant of the scheduling algorithm we did last week and the distance label network flow algorithm.
Problem set 4 is now out:
Problem Set 4 Due Monday, 2/25
Problem Set 2 solutions.
Problem set 3 is now out:
Problem Set 3 NOT Due
notes
Problem set 2 is now out:
Problem Set 2 due Monday 2/4/08.
Problem Set 1 solutions.
Office hour change: now M 1:45-2:45 and Friday 12:45-1:45 (or by appointment)
Page now mostly reflects new quarter, but still under construction.
- Clarification for problem 4: Note that in the search from t we reverse
the direction of the arcs (i.e. if an arc (a,t) has cost 10 in G, we now use an arc (t,a) of cost 10).
- Textbook info:
- Main text: Approximation Algorithms by Vijay Vazirani
- Also: Algorithm Design by Kleinberg and Tardos (used recently in 222A) We will cover a few of the advanced topics skipped in 222A.
- NOTE: we will cover several topics in neither book and will not use the main text till several weeks into the quarter.
- You may be able to find the text book online for a better price
-
Syllabus, Readings, and General Information
Homeworks and Homework Solutions (live)
Supplemental Readings
Exams
- For the sample midterm below problems 2-5 are a good fit for things that could be on an exam this year.
- Sample Midterm.
Useful links
Web Page created with vi, .