program 代做、代写 java 设计编程

日期：2025-02-22 08:50

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