算法分析代写 | CS570 Analysis of Algorithms Exam II

本次美国代写是算法分析的一个限时测试

1. Mark the following statements as TRUE or FALSE. No need to provide any justification.

 [ TRUE/FALSE ]

Given a weighted, directed graph with no negative-weight cycles, the shortest path
between every pair of vertices can be determined in worst-case time O(V3).

 

[ TRUE/FALSE ]

Any problem that can be solved using dynamic programming has a polynomial time
worst case time complexity with respect to its input size.

 

[ TRUE/FALSE ]

Ford-Fulkerson algorithm will always terminate as long as the flow network G has
edges with strictly positive capacities.

 

[ TRUE/FALSE ]

For any graph G with edge capacities and vertices s and t, there always exists an edge
such that increasing the capacity on that edge will increase the maximum flow from s to t.
(Assume there is at least one path in the graph from s to t)

 

[ TRUE/FALSE ]

For any network and any maximum flow on this network, there always exists an edge such
that decreasing the capacity on that edge with decrease the network’s max flow.

 

[ TRUE/FALSE ]

In the final residual graph constructed during the execution of the Ford–Fulkerson

Algorithm, there’s no path from source to sink.

 

[ TRUE/FALSE ]

For edge any edge e that is part of the minimum cut in G, if we increase the capacity
of that edge by any integer k>1, then that edge will no longer be part of the minimum cut.

 

[ TRUE/FALSE ]

0/1 knapsack problem can be solved in polynomial time using dynamic programming

 

[ TRUE/FALSE ]

One can find the value of the optimal solution AND the optimal solution to the
sequence alignment problem using only O(n) memory where n is the length of the
smaller sequence.

 

[ TRUE/FALSE ]
In a flow network if all edge capacities are irrational (not rational numbers) then the max flow is irrational.

You are trying to help a supermarket to distribute n types of coupons to a total of m customers. However, each type of coupon is of interest to only a subset of m customers . No coupon should be sent to a customer who is not interested in it. On the other hand, each customer can receive at most k coupons. No customer can receive duplicated coupons.

 

Design an efficient network flow based algorithm that given the list of customers of interest for each of the n coupons, and the upper bound k, will determine what coupons should be sent to each customer so as to maximize the total number of coupons sent. Show the running time (using parameters given above). You can assume that m>>n.

 


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


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

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


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

blank

发表评论