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