Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
Summative Assignment 1
(1) Each row has a unique maximum value,
(2) If the maximum value in row i of the matrix is located at column j, then the maximum value in row i+1 of the matrix is located at a column k, where k ≥ j.
The goal of this assignment is to find the maximum value in such a matrix.
Question 1. Write a function maxIndex that finds the index of the maximum entry of of a row between columns with indices start and end inclusively. The row is given as an array row. What is the time complexity of your solution? Explain your answer.
Question 2. A rectangular block of a matrix is given by a row and column of the upper-left corner in startRow and startCol, and row and column of the lower-right corner endRow and endCol, such that startRow ≤ endRow and startCol ≤ endCol. Write a function blockMaxValue that finds the value of the maximum entry of a given block assuming that the block satisfies the properties (1) and (2) above.
Hint: Use the divide-and-conquer strategy.
Question 3. Write a function matrixMaxValue that finds the maximum value of a matrix that satisfies properties (1) and (2) above, and provide a better upper bound for the time complexity of this function than O(nm). Explain your answer.