本次美国代写是一个算法分析的作业

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.

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

**E-mail:** itcsdx@outlook.com **微信:**itcsdx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。