CS 288 Exam #2: Algorithms

1. A dating service receives data from n men and n women.  These data determine what pairs of men and women are mutually compatible. (In this problem, compatibility is binary. A couple is either compatible or not.)

a. Since the dating service's commission is proportional to the number of dates it arranges, it would like to determine the maximum number of compatible couples that can be formed.  Explain how to formulate this problem as a maximum flow problem.

b. Consider the attraction matrix below

    [ 0 0 1 1 ]
A = [ 1 0 0 0 ]
    [ 1 0 1 0 ]
    [ 0 0 0 0 ]
where aij = 1 if the ith man and the jth woman are attracted to each other, 0 otherwise. Carry out the flow algorithm to find an optimal pairing.
Here is a reminder of the flow algorithm. Given are a directed graph G = (V, E) and a capacity function c: V x V -> R.

Initialize flow f to 0
while (there is a path p from the source to the sink in Gf = (V, { (u, v) | c(u,v) - f(u,v) > 0 })
   augment f along p
return f

Also remember that f(v, u) = -f(u,v).

2. Given are a set of n men, a set of n women, and a matrix A = (aij), where aij is the mutual attraction between the ith man and the jth woman (this time, as a number between 0 and 10). The problem is to pair up the men and women so that the total mutual attraction, measured as

    A(p) = Σ mip(i)

is maximized. Here p: { 1 . . . n } -> { 1 . . . n } is the pairing function, such that p(i) is the index of the woman that is paired up with the ith man.

a. Show that this problem has optimal substructure.

b. Explain why the following formula finds an optimal solution for the problem of size n, assuming that optimal solutions for problems of size n - 1 are available.

OPT-A({1 . . . n}, {1 . . . n }) = max { OPT-A({1 . . . n - 1}, {1 . . . i - 1,  i + 1 . . . n}) + ani | 1 ≤ i ≤ n }

Here OPT-A(I, J) is the optimum attraction that can be achieved by matching men with indexes from I and women with indexes from J. (I, J ⊆ { 1 . . . n }). That is, OPT-A(I, J) = max { A(p) | p: I -> J is a bijection }

c. Given the matrix

    [ 10 5  0]
A = [ 0  4 10]
    [ 5  5  5]

fill in the following table (starting from the bottom)

I
 J
 OPT-A(I, J)
{1, 2, 3}
 {1, 2, 3}
 max(     +     ,    +      ,    +      ) =    
{1, 2}
 {1, 2}
 max(     +     ,    +      ) =    
{1, 2}
 {1, 3}
 max(     +     ,    +      ) =    
{1, 2}
 {2, 3}
 max(     +     ,    +      ) =    
{1}
 {1}
{1}
 {2}
{1}
 {3}

d. Give pseudocode to show how this algorithm can be implemented in your favorite programming language. Hint: You may want to make use of a map (C++) or Map (Java) data structure to keep track of the intermediate results. What are the key and value types for the map? In what order do you fill the map? Show how to compute the optimum attraction value as well as  the pairing that realizes the optimum.


3. Consider the following stack implemented as a dynamically resizing array (in Java):
public class Stack
{
   public Stack()
   {
      elements = new Object[1];
      length = 0;
   }

   public void push(Object obj)
   {
      if (length == elements.size)
      {
         Object[] newElements = new Object[2 * elements.size];
         System.arraycopy(elements, 0, newElements, 0, length); // cost: length units
         elements = newElements;
      }
      elements[length] = obj; // cost: 1 unit
      length++;
   }

   public void pop(Object obj)
   {
      length--;
      Object r = elements[length]; // cost: 1 unit
      if (length == elements.size / 2)
      {
         Object[] newElements = new Object[elements.size / 2];
         System.arraycopy(elements, 0, newElements, 0, length); // cost: length units
         elements = newElements;
      }      
      return r;
   }

   private Object[] elements;
   private int length;
}

As you can see, pushing and popping is expensive when the array needs to be relocated. This happens whenever the length is a power of 2. We will assume that the cost of inserting an element is 1 unit, and the cost of relocating an array with t entries is t units.

a. Using the accounting method, show that the amortized cost of n = 2k push operations is O(n) units if you start with a stack of length 2k + 1.  (Hint: Charge 3 units of cost for every push.)

b. Show that the actual cost of a sequence of n push and pop operations may be higher than O(n) in certain cases. (Hint: Pop elements immediately after the array was expanded...)

c. This problem can be remedied by implementing the pop operation as follows:
   public void pop(Object obj)
   {
      length--;
      Object r = elements[length]; // cost: 1 unit
      if (length == elements.size / 4)
      {
         Object[] newElements = new Object[elements.size / 4];
         System.arraycopy(elements, 0, newElements, 0, length); // cost: length units
         elements = newElements;
      }      
      return r;
   }
With this modification, how much do you need to charge for every pop operation so that the amortized cost of a sequence of n push and pop operations is O(n)?

Here is a reminder of the terminology of the accounting method. Given a sequence of operations with actual costs ai, let âi denote the amortized cost of these operations. Then you need to show that Σ ai ≤ Σ âi.