We also need to proof the correctness of the algorithm (by Induction), and the time complexity of the algorithm (explaining why it is O(n^2)).

Question 3. (25 points) Let A be an nn matrix of n2 arbitrary numbers (positive or negative), and let R={R1,,Rm} be a set of m=n2 rectangular regions in A where each Ri is specified by 2 row indices i1,i2(i1i2) and two column indices j1,j2(j1j2); therefore the 4 corners of rectangle Ri are the matrix entries A[i1,j1],A[i1,j2],A[i2,j1], A[i2,j2]. Let ri denote the sum of the entries of A that are covered by rectangle Ri : ri=i1ki2,j1j2A[k,] Give an O(n2) time algorithm for computing all of r1,,rm