Java Programming Assignment

Square-Matrix-Multiply-Recursive(A, B)
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

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];...

This is only a preview of the solution. Please use the purchase button to see the entire solution