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