# 算法分析代写 | 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.

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