算法分析代写 | CSE 347 Analysis of Algorithms Homework 4: Maximum Flow
本次美国代写是一个算法分析的作业
Please remember to
- typeset your homework;
- include a header with your name, 6-digit student ID, and the homework number at the
top of each page; - include any figures (typeset or hand-drawn) inline or as oats;
- upload and submit your PDF to Gradescope before class time on the due date;
- select the pages corresponding to each problem after uploading the PDF.
Always show your work.
1. This problem considers a particular choice in the Ford-Fulkerson algorithm of how to choose the next
path on which to push ow. You’ll discuss some aspects of this algorithm in recitation, but for this
problem, all you really need is to understand our proof of the Max- ow Min-cut Theorem.
The \fattest-path” version of Ford-Fulkerson specifies that, whenever we want to choose an s-t path
in the graph (with its added back edges) on which to push more ow, we choose a path whose width
(that is, the least capacity of any of its edges) is maximum. In recitation, you’ll develop an efficient
algorithm for finding such a path, but let’s just assume you have one that runs in time Omega(h(n)).
(a) Suppose the graph has n vertices and m edges, and that the maximum ow from s to t in this
graph has size F. Assuming that all edge capacities are integers, show that there exists a path
from s to t of width at least F=m.
Hint : use a similar construction to our Max- ow Min-cut proof to show that, if no such path
exists, there is a cut of the graph with very small capacity. Why is this a problem?
(b) Show that if the original graph has m edges and maximum ow of size F, then after only
O(mlog F) successive rounds of finding a widest path and pushing ow on it, the residual graph
must have a maximum s-t ow of 0.
Hint : what fraction of the original maximum ow remains after finding and using the widest path
k times? Use your result from (a). It may help to note that
The above observations imply a Omega(h(|V |)|E| log F) algorithm for maximum ow. Because this algo-
rithm’s cost scales logarithmically with the max ow size, its cost is logarithmic in the edge capacities
specified for the graph, rather than linear as for naive Ford-Fulkerson. (\Linear” here means that if
we double all the capacities, the algorithm might take twice as long to run { stay tuned for a future
lecture where we’ll discuss why this is bad!)
2. Zach is a Lego maniac. He has created designs for series of a massive Lego sculptures, but he has
no money to buy Legos. He plans to sneak into the LegoLand warehouse overnight and steal enough
Legos to realize his vision… but he’s afraid someone will notice the missing Legos and discover his
crime.
Zach has a total of p designs. Zach’s kth design requires dki pieces of type i, for 1 <= i <= m. The
warehouse has n bins b1 : : : bn of Legos, such that bin bj contains bji pieces of type i. To avoid detection,
Zach cannot steal more than 5% of the pieces in any one bin.
Give an efficient algorithm to determine whether Zach is able to acquire all the pieces he needs to build
all of his sculptures without getting caught.