1. In the maximum subarray problem, where the input is an array of length n, give a condition under which the output of the FIND-MAXIMUM-SUBARRAY algorithm is ( i, i+1, sum ) for some index "i" and a positive value "sum".

2. Suppose that in the maximum subarray problem the input is an array such that the values A[ i ] alternate between positive and negative (say, A[ 1 ] > 0, A[ 2 ] < 0, A[ 3 ] > 0, A[ 4 ] < 0, ..., etc.). Is it possible that the output of the FIND-MAXIMUM-SUBARRAY algorithm has the form

(i) ( i, i, sum )

(ii) ( i, i+1, sum )

(iii) ( i, i+2, sum )

for some index i and positive value sum?

Argue why or why not.

3. Suppose that a divide and conquer algorithm for multiplication of n x n matrices is found such that it requires 6 multiplications and 31 additions of n/2 x n/2 submatrices. Write the recurrence for the running time T(n) of this algorithm and find the order of T(n).