ECS 222B  Spring 2010 Advanced Algorithms
Announcements
Old Announcements
Matching algirithms (summary)
(for 4/29/10 lecture)
Main text: Approximation Algorithms by Vijay Vazirani
Also: Algorithm Design by Kleinberg and Tardos (used recently in 222A) We will cover a couple of the advanced topics skipped in 222A. Don't buy this if you don't have it. We will only cover a little in it.
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
Office hours (starting April 2): Friday 1:452:45, and Tuesday 12:301:25, or by appointment
Papers for 4/1/10 Lecture Below
Expected Dijkstra (for 4/1/10 lecture)
A* and shortest paths (for 4/1/10 lecture)
Syllabus, Readings, and General Information
Homeworks and Homework Solutions ()
 NOTE: 08 dates are from last time, new ones will have 2010 dates.
 Solutions will be on the myucdavis class web page.

 Problem Set 1 due 4/16/10.

 Problem Set 2 due 4/29/10.


 Problem Set 3 due 5/27/10.

Supplemental Readings
 A useful book on graph algorithms: Network Flows by
Author Ahuja, Magnanti, and Orlin

 Expected Dijkstra (for 4/1/10 lecture)

 A* and shortest paths (for 4/1/10 lecture)

 References for 4/8 and 4/13 lectures below:
 Teofilo Gonzalez , Sartaj Sahni, Preemptive Scheduling of Uniform Processor Systems, Journal of the ACM (JACM), v.25 n.1, p.92101, Jan. 1978
 Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Techniques
A. Federgruen and H. Groenevelt
Management Science, Vol. 32, No. 3 (Mar., 1986), pp. 341349
 Determining edge connectivity in 0(nm)
David Matula.
Proceedings of the 28th Annual Symposium on Foundations of Computer Science
Pages: 249251
Year of Publication: 1987
 HORN, W.Some simple scheduling algorithms Naval Res Log Q 21 (1974), 177185. (the scheduling application of network flow, sorry no free versions online)
 Notes on Mincost Flow a

Matching algirithms (summary)
(for 4/29/10 lecture)

a survey paper in the book ``Steiner Trees in Industry" and
available at
here
 A nice improvement for GomoryHu trees is in: Very Simple Methods for all Pairs Network Flow analysis, by Dan Gusfield. SIAM J. on computing, Vol. 19, 1, pp. 14355, 1990.

 Melhorn paper on faster steiner tree approximation
 Mincost flow notes (from MIT class)

 Algorithm Design, Jon Kleinberg and Eva Tardos, Nice Algorithms book
with coverage of many of the topics in this class (including randomized closest points
algorithm)
Exams
Useful links
Web Page created with vi, .