QuestionQuestion

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

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse 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.

$30.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats