代做CS4820、Java，Python编程代写

日期：2023-10-28 09:57

Introduction to Analysis of Algorithms HW7: Reductions, Flows, and Cuts

CS4820/5820 Fall 2023 Due: October 25, 11:59pm

Design-an-Algorithm Instructions: Homework problems often ask you to design an algorithm. In this case, you must:

1. explain your algorithm at a high level in English. You can use pseudocode (but not code) as

needed to make your ideas clearer, but remember to keep all explanations at a high level,

2. prove the algorithm’s correctness, and

3. analyze its running time, that is, you must show the running time is bounded by a polynomial function of the input size.

Reductions: You may sometimes realize that you can solve a homework problem using an algorithm from lecture or the textbook as a black box. We call this a reduction. In this case, you need

not explain the details of the existing algorithm, its running time and correctness. However, you

must fully explain the reduction by providing

1. a clear reference to the existing algorithm, along with the protocol that turns an instance

of the homework problem into an input for this algorithm,

2. a proof that the output given by the existing algorithm on the input created by your protocol

correctly solves the homework problem, and

3. a running time analysis that bounds the time of the combined process of creating the input for the existing algorithm, and executing the algorithm on this input by a polynomial

function of the homework problem’s input size.

Academic Integrity: You may not consult outside sources when working on the homework

(this means any resources besides your lecture notes, the textbook, and documents/information

contained on the course Canvas page / Ed discussion board).

Collaboration Policy: Collaboration (in groups of up to three students) is encouraged while

solving the problems, but:

1. list the netids of those in your group;

2. you may discuss ideas and approaches, but you should not write a detailed argument or

code outline together;

3. notes of your discussions should be limited to drawings and a few keywords; you must

write up the solutions and write code on your own.

We recommend solving the warm up questions (posted as a separate document) before you start

Homework 7.

Problem 1. A large street food company is deciding whether to start a business selling raw

herring in a European city. The company has information about potential vending opportunities

organized as an undirected graph G = (V, E). The node set V is a list of possible locations for

placing herring stalls. For each location v ∈ V , the company estimates a sales volume sv > 0.

Each herring sold gives a profit of p > 0. The company can choose multiple locations and assumes

the sales volumes at a location is independent of other locations selected (so if they choose a set

of locations S, the sales volume is P

v∈S

sv).

The edges of the graph represent the city streets. If the seller puts a herring stall at location v,

the city requires them to pay for street cleaning on all streets corresponding to edges incident to

v. Each edge e = (u, v) ∈ E is labeled with an integer ce > 0; if the company has a stall at one

or both of the locations u, v, it has to pay ce for cleaning the street represented by e.

The company will do business in the city if there is a set of stall locations S ⊆ V for which the

estimated profit is more than the cost of cleaning the streets incident to the chosen locations.

Design an algorithm that takes as input the graph G, the per-herring profit p, predicted sales

volume sv for each v ∈ V , and the cleaning cost ce for each e ∈ E and returns such a set S if it

exists. The runtime of your algorithm should be polynomial in n = |V |, m = |E|, and C =

X

e∈E

ce.

Problem 2. Implement your algorithm from Problem 1.

Input / output formatting and requirements. The algorithm should read in data from stdin

in the following expected format:

• The first line has three space-separated integers n, m and p;

• In the following n lines, the i-th line contains the expected sales volume at the i-th potential

location

• The following m lines contain the edges: each line has three space-separated integers

(u, v, c) with u, v ∈ {1, . . . , n} being the endpoints of the edge, and c ≥ 0 being the

cost of cleaning the corresponding street.

The algorithm should output data to stdout in two lines, where:

• the first line contains two space-separated integers giving the maximum profit and the

number of stations at which the company sells herring;

• the second line contains a space-separated list of the locations at which the company sells

herring.

In particular, if the optimal solution is to not sell any herrings, then the output should be 0\n\n

because the second line is an empty list (so not 0\n).

You may find it helpful to use the max flow code we posted on github.

2

Problem 3. There is an outbreak of a new highly contagious disease on the island nation Fifi.

There are two main cities on the island, Sourcisia and Targista, and the disease was detected only

in Sourcisia thus far.

In an attempt to ensure that the disease does not reach Targista, island officials are planning to

close off some of the towns; once a town is closed off, no traffic can pass through that town.

They have modeled the island as an undirected graph G = (V, E), where V contains a node for

Sourcisia and Targista, and a node for every other town on the island; each edge in E represents

a road between the towns. For each town v, you are also provided an integer p(v) > 0 giving the

size of the population of v.

They believe that closing off towns with more than P people in total will lead to a popular revolt, so they are asking your help to determine whether there is a set of towns whose combined

population is at most P such that closing off these towns will ensure that no traffic can go from

Sourcisia to Targista. (The cities of Sourcisia and Targista themselves are not eligible to being

closed off.)

Design an algorithm that determines whether such a set exists, and if so, returns a set of towns

with combined population at most P that can be closed off to ensure no traffic can go from

Sourcisia to Targista.

The runtime of your algorithm should be polynomial in n = |V |, m = |E|, and P

v

pv.

3