Question
1 n = A.rows
2 let C be a new n×n matrix
3 if n == 1
4 c11 = a11 · b11
5 else partition A, B, and C
6 C11 = Square-Matrix-Multiply-Recursive(A11, B11) +Square-Matrix-Multiply-Recursive(A12, B21)
7 C12 = Square-Matrix-Multiply-Recursive(A11, B12) +Square-Matrix-Multiply-Recursive(A12, B22)
8 C21 = Square-Matrix-Multiply-Recursive(A21, B11) +Square-Matrix-Multiply-Recursive(A22, B21)
9 C22 = Square-Matrix-Multiply-Recursive(A21, B12) +Square-Matrix-Multiply-Recursive(A22, B22)
10 return C
Since the matrices A and B is n × n matrices , they can be represented in regular arrays of size n2 . The coefficient Cij in matrix ( 0 - indexed) is accessed when the array a with a [ in + j] .
You will implement two versions , one that copies submatrix into new arrays , and one that uses two index variables to indicate which part of the array being worked on.
You must be reasoned you find one Recurrence equation for both editions , and explain why the same equation can be used to describe both. You should then make an analysis using rekursjonstrær so that you arrive at a guess for a function that describes the running time of the algorithm . This shall then verify both the substitution method ( mathematical induction) and masterteoremet .
Although copying edition has a higher cost than the index release both Editions same asymptotic notation. The difference is only one constant between the two editions when we analyze the running time . Is this also the case in practice? Test the two versions of the algorithm with different input sizes and judge it only distinguishes between a constant or not. Discuss the results and emphasize explain why it may not be true that it only distinguishes a constant.
Hints:
A[(n/2) * k + i, (n/2)m + j]
one square to split into four square
over left square: A11 k = 0 m = 0
over right square: A12 k = 0 m = 1
under left square: A21 k = 1 m = 1
under right square: A22 k = 1 m = 1
Solution Preview
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.
public class SquareMatrixMultiplyRecursive {public static int[] square_matrix_multiply_recursive_copy(int[] A, int[] B)
{
int[] C;
int n = A.length;
C = new int[n];
if(n == 1)
C[0] = A[0] * B[0];...
By purchasing this solution you'll be able to access the following files:
Solution.java and Solution1.java.