due March 4.  Exact time will be annouced by the TAs.
Note that the lecture of March 4 has been rescheduled to March 3,
8:30.

Reading: Chapter 7 of Kleinberg Tardos.  (section 7.1,7.2, also all of
7.5-7.12 are recommended and should be understandable, we did only
some of these in class).  If you read other books and use their
notation, that is also fine, but please indicate if your
formulation/notation is different from what is used in class/Kleinberg
Tardos.

1.  (Problem 7.8 of KT)  Suppose we have in stock 50,36,11,8 units of
    blood, respectively of type O,A,B,AB.  The demand for these types
    is respectively 45,42,8,3 units.  It turns out that type O blood
    can be used in place of any type, type A can be used either for
    type A or type AB, type B for type B or type AB, and type AB can
    only be used for type AB.

    Can the available stock be used to satisfy the demand?  Formulate
    this as a flow problem and answer.

2.  (7.14) We have a directed graph G representing a road network.  A
           subset X of the vertices are towns, and another subset Y
           are "safe areas".  X and Y are disjoint.  Suppose all towns
           have the same population, and all safe areas are capable of
           accommodating the population of 1 town.  In case of an
           emergency, the population of each town is to be moved to a
           distinct area in Y.  In order to not congest the roads, it
           is desired that the path from each town to its safe
           location be edge disjoint.  Show how you can decide if such
           paths exist in polynomial time.  Suppose now that the paths
           also need to be node disjoint.  Show how this can also be
           done.  

3. (a) Answer true or false with justification: 

          (7.5) let (A,B) be a minimum s,t cut in a graph G.  Suppose
          we add 1 to the capacity of every edge.  Then (A,B) remains
          a min-cut with respect to the new capacities.

          (7.11) Consider an algorithm for finding maximum flow:
          repeatedly augment (push flow) along an s-t path and then
          reduce the capacities.  Note that in this we only reduce
          capacities but do not work with the residual graph.  In this
          case we are guaranteed that we will get a flow of at least
          1/100 the value of the maximum flow.

    (b) (Extension to 7.14) Give an example in which node disjoint
        paths are not possible but edge disjoint paths are.  Make your
        example as simple as possible.

4. (7.16) Suppose n users browse the net on a certain day.  Each user
          might have one or more of the m attributes, e.g. "likes
          Indian classical music", "likes Shakespeare", "lives in
          Amravati", "is in age group 30-40" and so on.  The network
          provider knows the attributes for each user.  Based on this
          the provider is to show exactly one advertisement to each
          user.

	  This must be done so that the network provider satisfies its
	  contract with the advertisers.  This contract is of the
	  following kind: Each advertiser A_i wants her advertisement
	  to be shown to users possessing one or more of a given
	  collection C_i of attributes.  For example, if A_i is
	  advertising expensive sports shoes, C_i could be the
	  attributes "likes football", "age group 20-30".  Further,
	  the provider has agreed to show the advertisement to r_i
	  such users.  

	  Show how to determine in polynomial time whether the
	  contract can be honoured.  You should assume that max flow
	  can be done in polynomial time.

--