ECS 222B - Advanced Algorithms - Spring 2010

ECS 222B - Spring 2010 Advanced Algorithms

Announcements

Problem Set 4 solutions on myucd web page (NOTE, under 08.sol)
Problem Set 4 NOT DUE
Problem Set 3 solutions on myucd web page (NOTE, revised from an earlier version).
Final exam: Wed. 6/9 6-8PM (125 Wellman).
Melhorn paper on faster steiner tree approximation
Gusfield Gomory-Hu tree method.
slides from Amenta lecture on ucd web page
Movie from Amenta.
Problem Set 3 due 5/27/10.

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:45-2:45, and Tuesday 12:30-1: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

Course information sheet - You are responsible for everything on this
Planned Syllabus for this Course -->
lectures - completed and projected lecture topics.
lectures - completed and projected lecture topics from the last offering. This year will be similar.

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.92-101, 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. 341-349
Determining edge connectivity in 0(nm) David Matula. Proceedings of the 28th Annual Symposium on Foundations of Computer Science Pages: 249-251 Year of Publication: 1987
HORN, W.Some simple scheduling algorithms Naval Res Log Q 21 (1974), 177-185. (the scheduling application of network flow, sorry no free versions online)
Notes on Min-cost 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 Gomory-Hu trees 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.
Melhorn paper on faster steiner tree approximation
Min-cost 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, .