15-451 MINI #4: due 11:59pm Oct 16, 2012

Problem 1:

You are given a 2-dimensional n-by-n matrix of numbers A.  So A[i][j]
is the entry in the ith row and jth column, for 0 <= i,j < n.

Explain how to preprocess this information to build a new data
structure that can answer queries of the following form in O(1) time.

 sum(i1, j1, i2, j2) = the sum of all the numbers in A in rows between
                       i1 and i2 (inclusive) and columns j1 and j2 (inclusive).

In other words, this sums all the numbers in the rectangle with one corner
(i1,j1) and opposite corner (i2,j2).  Your data structure should use
only O(n^2) space (i.e., should not be (much) bigger than A).


Problem 2:

Give an algorithm to maintain a list of numbers x_1, x_2, ... x_n
and supports the following operations in O(log n) time.

   update(i, v):   replace x_i by v
   sum(i,j):       return x_i + x_{i+1} + ... + x_j
   max(i,j):       return the maximum of {x_i, x_{i+1}, ..., x_j}


Problem 3:
   (a) What is the maximum S-T flow in the graph G below?
   (b) Draw the residual graph you get at the very end of running the
       Ford-Fulkerson algorithm on this graph.  Remember to include
       the back-edges.

             3         5
         S------->a-------->T
         |        ^         ^
         |        |         |
         |7       |3        |6
         |        |         |
         v   6    |    4    |
         b------->c-------->d