program 代做、代写 java 设计编程
Summative Assignment 1
LC Data Structures and Algorithms due date 5 March 2025, 12pm
You are given an n × m matrix with integer entries that has the following properties:
(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.
Hint: The complexity of linear search is O(nm), do better than that!
Submission
Submission is via Canvas, and it should contain two files:
• Java source code named ‘solution.java’ containing a class Solution with the following meth- ods:
public class Solution {
public static int maxIndex(int[] row, int start, int end);
public static int blockMaxValue(int[][] matrix,
int startRow, int startCol, int endRow, int endCol);
public static int matrixMaxValue(int[][] matrix);
}
Do not rename the class or the methods, otherwise your solution will fail the test cases.
• A text/pdf file containing the explanation of the complexity of your code.
1