1. The input is an N by N matrix of numbers that is already in memory. Each individ- ual row is increasing from left to right. Each individual column is increasing from top to bottom. Give an O(N) worst-case algorithm that decides if a number X is in the matrix.
2. Design ef?cient algorithms that take an array of positive numbers a, and determine:
a. the maximum value of a[j]+a[i], with j ≥ i.
b. the maximum value of a[j]-a[i], with j ≥ i.
c. the maximum value of a[j]*a[i], with j ≥ i.
d. the maximum value of a[j]/a[i], with j ≥ i.