COS 226 Homework #8
Due: Tuesday, May 3, 2005

Written Exercises

Follow the instructions on the assignments page on how and when to turn these in.  Point values of each problem are shown in brackets.  For questions 2 and 4, you can print out the figures and indicate your answers right on them.  Be sure to also complete the programming part of this assignment, including the program report.

  1. [8] Enthusiastic celebration of a sunny day at a prominent northeastern university has resulted in the arrival at the university's medical clinic of 169 students in need of emergency treatment.  Each of the 169 students requires a transfusion of one unit of whole blood.  The clinic has supplies of 170 units of whole blood.  The number of units of blood available in each of the four major blood groups and the distribution of patients among the groups is summarized below: 
    Blood type  A   B   O   AB
Supply     46  34  45   45
Demand     39  38  42   50
    Type A patients can only receive type A or O; type B patients can receive only type B or O; type O patients can receive only type O; and type AB patients can receive any of the four types.
     
    1. Give a max flow formulation that determines a distribution that satisfies the demands of a maximum number of patients. Draw the directed graph and put the edge capacity above each edge.  Your network should have 10 vertices: a source (named 0), a supply node for each of the four blood types (named 1 to 4, in the order given above), a demand node for each blood type (named 5 to 8), and a sink (named 9).
       
    2. Solve the maximum flow problem using the Ford-Fulkerson augmenting path algorithm.   Do the first augmentation on the path 0-2-8-9.  (This will force you to use a backwards edge at some point during the rest of the algorithm.)  Afterwards, always choose the augmenting path with the fewest number of arcs, breaking ties in favor of the lexicographically smallest path (e.g., choose 0-2-7-9 over 0-4-6-9).  List each of the augmenting paths.  Also, write and circle the final flow values on each arc in the network drawn in the last part.
       
  2. [4] Show how the Graham scan algorithm would compute the convex hull of the following set of points:




    In particular, number the points in the order in which they would be processed.  Then indicate the sequence of values of the stack following each iteration of the main outer loop of the algorithm.  (Use the stack-based algorithm given in class, or see Section 33.3 of CLRS.)
     
  3. [6] (CLRS exercise 33.4-3, slightly adapted)  The distance between two points can be defined in ways other than the usual Euclidean distance.  In the plane, the Lm-distance between points p1 and p2 is given by the expression (|x1 - x2|m + |y1 - y2|m)1/m.  Euclidean distance, therefore, is L2-distance.  Explain how the closest-pair algorithm would have to be modified to use the L1-distance, also known as the Manhattan distance (since it measures the distance needed to travel between two points when traveling only horizontally or vertically, as on a city grid like Manhattan's).
     
  4. [4] Show how the horizontal-sweep algorithm given in class would compute all intersections of the following set of line segments:



    In particular, use vertical lines to indicate where each "interesting event" occurs.  At each of these, indicate the "active" line segments and their order.  Also indicate which pairs of lines are tested for intersection at each of these events, and which intersections are discovered.
     
  5. [4] (adapted from Chvatal)  PU Dining Services wonders how little money they can spend on food while still supplying sufficient energy (200 kcal), protein (55g), and calcium (800mg) to meet the minimum Federal guidelines and avert a potential lawsuit.  A limited selection of potential menu items along with their nutrient content and maximum tolerable quantities per day is given in the table below. 
                     Serving   Energy   Protein   Calcium   Cost per serving   Max servings
Food                Size   (kcal)       (g)      (mg)            (cents)        per day
---------------------------------------------------------------------------------------
Oatmeal              28g      110         4         2                  3              4
Chicken             100g      205        32        12                 24              3
Eggs             2 large      160        13        54                 13              2
Whole milk         237cc      160         8       285                  9              8
Cherry pie          170g      420         4        22                 20              2
Pork with beans     260g      260        14        80                 19              2
    Formulate (but do not solve) a linear program to find the most economical menu.
     
  6. [15] This question refers to the programming part of this assignment, and asks you to argue carefully and convincingly why the method given for converting a min-cut into a certificate of elimination actually works.

    Consider the elimination network constructed to test the elimination of a particular team x.  Let C = (S, T) be any min-cut (i.e., minimum capacity s-t cut) of this network.  Let R be the set of team nodes on the source side of the cut (i.e., in S).  Let n be the number of teams in R.  Let m = w[x] + r[x] be the most games that team x can win.
     

    1. Let L be the sum of all edges leaving R.  Give an expression for L in terms of n and m.
       
    2. Let I be the sum of all capacities of edges leaving s and entering any game node or team node involving only teams in R (that is, either a team node i, where i is in R, or a game node i-j where both i and j are in R).  Explain why, regardless of the outcomes of all future games, the total number of games won by all the teams in R will total at least I.
       
    3. Let C' = (S',  T') be a cut that separates s from the rest of the network (that is, S' = {s}).  Show that if I <= L then the capacity of C' is at most the capacity of C, and therefore that C' is also a min-cut.
       
    4. Suppose that the value of the max-flow is strictly less than the total capacity of all edges leaving s.  Show that C' is not a min-cut in this case, and therefore that I > L.
       
    5. Conclude that if the value of the max-flow is strictly less than the total capacity of all edges leaving s then the average number of games won by teams in R is strictly greater than m, the best possible number of games winnable by x.