[SOLVED] CS algorithm Homework 7

Homework 7
Due date: 3/3/2021 right before class
Problem 1. Q8 page 418
Statistically, the arrival of spring typically results in increased accidents and increased need for emergency medical treatment, which often requires blood transfusions. Consider the problem faced by a hospital that is trying to evaluate whether its blood supply is sufficient. The basic rule for blood donation is the following. A persons own blood supply has certain antigens present (we can think of antigens as a kind of molecular signature); and a person cannot receive blood with a particular antigen if their own blood does not have this antigen present. Concretely, this principle underpins the division of blood into four types: A,B,AB, and O. Blood of type A has the A antigen, blood of type B has the B antigen, blood of type AB has both, and blood of type O has neither. Thus, patients with type A can receive only blood types A or O in a transfusion, patients with type B can receive only B or O, patients with type O can receive only O, and patients with type AB can receive any of the four types.
1. Let sO , sA , sB , and sAB denote the supply in whole units of the differ- ent blood types on hand. Assume that the hospital knows the projected demand for each blood type dO,dA,dB, and dAB for the coming week. Give a polynomial-time algorithm to evaluate if the blood on hand would suffice for the projected need.
2. Consider the following example. Over the next week, they expect to need at most 100 units of blood. The typical distribution of blood types in U.S. patients is roughly 45 percent type O, 42 percent type A, 10 percent type B, and 3 percent type AB. The hospital wants to know if the blood supply it has on hand would be enough if 100 patients arrive with the expected type distribution. There is a total of 105 units of blood on hand. The table below gives these demands, and the supply on hand.
Is the 105 units of blood on hand enough to satisfy the 100 units of de- mand? Find an allocation that satisfies the maximum possible number
1
blood type
supply
demand
O A B AB
50 36 11 8
45 42 8 3

of patients. Use an argument based on a minimum-capacity cut to show why not all patients can receive blood. Also, provide an explanation for this fact that would be understandable to the clinic administrators, who have not taken a course on algorithms. (So, for example, this explanation should not involve the words flow, cut, or graph in the sense we use them in this book.)
Problem 2. Q10 page 419
Suppose you are given a directed graph G = (V,E), with a positive integer capacityce oneachedgee,asourcesV,andasinktV. Youarealsogiven a maximum st flow in G, defined by a flow value fe on each edge e. The flow f is acyclic: There is no cycle in G on which all edges carry positive flow. The flow f is also integer-valued. Now suppose we pick a specific edge e E and reduce its capacity by 1 unit. Show how to find a maximum flow in the resulting capacitated graph in time O(m + n), where m is the number of edges in G and n is the number of nodes.
Problem 3. Q12 page 419
Consider the following problem. You are given a flow network with unit capacity edges: It consists of a directed graph G = (V, E), a source s V , and a sink tV;andce =1foreveryeE. Youarealsogivenaparameterk.
The goal is to delete k edges so as to reduce the maximum st flow in G by
as much as possible. In other words, you should find a set of edges F E so that
|F|=kandthemaximumstflowinG =(V,EF)isassmallaspossible subject to this. Give a polynomial-time algorithm to solve this problem.
Problem 4. Q14 page 421
We define the Escape Problem as follows. We are given a directed graph G = (V,E) (picture a network of roads). A certain collection of nodes X V are designated as populated nodes, and a certain other collection S V are designated as safe nodes. (Assume that X and S are disjoint.) In case of an emergency, we want evacuation routes from the populated nodes to the safe nodes. A set of evacuation routes is defined as a set of paths in G so that (i) each node in X is the tail of one path, (ii) the last node on each path lies in S, and (iii) the paths do not share any edges. Such a set of paths gives a way for the occupants of the populated nodes to escape to S, without overly congesting any edge in G.
1. Given G,X, and S, show how to decide in polynomial time whether such a set of evacuation routes exists.
2

2. Suppose we have exactly the same problem as in (a), but we want to enforce an even stronger version of the no congestion condition (iii). Thus we change (iii) to say the paths do not share any nodes. With this new condition, show how to decide in polynomial time whether such a set of evacuation routes exists. Also, provide an example with the same G, X, and S, in which the answer is yes to the question in (a) but no to the question in (b).
3