Algorithms II
2006-07
Principal lecturer: Dr Frank Stajano
Taken by: Part IB, Part II (General), Diploma
Syllabus
Past exam questions
Feedback
All participants are warmly encouraged to submit anonymous
feedback at the end of the course, noting good points that they
think should be preserved and bad points that they think should
change. A summary of feedback
so far received is available (from .cam.ac.uk).
Additional material
One of you asked why the Ford-Fulkerson method might fail to
terminate altogether, even with a pessimal choice of paths, as opposed
to just taking a very long time, since edge capacities are finite and
the number of edges is finite. The answer is not trivial or intuitive
(Ford and Fulkerson's own example had 10 vertices and 48 edges), but
the minimal example appeared in Uri Zwick, "The
smallest networks on which the Ford-Fulkerson maximum flow procedure
may fail to terminate", Theoretical Computer
Science 148, 165-170 (1995).
|
