CSC349-Project 2 Part 2: Divide-and-conquer algorithms Solved

Goals of the assignment:   

Implement divide-and-conquer algorithms.
Implement two classic algorithms for matrix multiplication.
Handle intricate details of recursive matrix manipulation – identifying and working with segments of two-dimensional arrays, constructing two-dimensional arrays from smaller ones.
 Design and implement a class named MatrixProduct. 
 

The only content of MartixProduct class should be the implementation of the following 2 classic algorithms for matrix multiplication: the “simple” divide-and-conquer algorithm and the Strassen’s algorithm (see the lecture handout/slides for these algorithms). Both algorithms take two square matrices A(n×n) and B(n×n) and return a product-matrix C(n×n); n is required to be a power of 2 (you need it to be divisible by 2 without remainder at each level of recursion).

Both algorithms are recursive so for each algorithm you need to have the following members:

 

a public method that will get two square matrices A and B (both of the same size) and will initiate the recursion. It will return the final product-matrix (of the same size as A and B). The signature of this method for each algorithm (i.e. the name, the number and type of parameters, and the return-value type) is specified on the top of the next page*. 
  

  Important: The first thing to do in this method is the validity check, namely: 

Check if A and B are square matrices of the same size.
Check if the matrix size (i.e. the n-value) is a power of 2.
        IF at least one requirement is not satisfied, throw IllegalArgumentException exception. 

a private method that carries the recursion (see the lecture handout/slides)
as many private supporting methods as you need to do the work.
Note: the signature of private methods (name, type and number of parameters, return value’s type) is not mandated, but to stay on track and to avoid confusion, follow the path of the lecture handout/slides. Do NOT seek help on the internet – all you need is in the handout.

          1 Dr. Hasmik Gharibyan

CSC/CPE349 * The above-mentioned two public methods should have the following headers: 

 

public static  int[][]  matrixProduct_DAC(int[][] A,  int[][] B)

   //Compute and return the product of A, B matrices using “simple” DAC algorithm presented in class.

public static  int[][]  matrixProduct_Strassen(int[][] A,  int[][] B)

   //Compute and return the product of A, B matrixes using Strassen’s algorithm presented in class.

 

Note: both algorithms are working with integer values.

Design and implement application class(es) to test your two algorithms. 
 

You can make a single application class to test both algorithms, or you can create two separate classes – one for each algorithm. An application class will contain a main method very similar to the main method in your Project2_part1 assignment.

Reminder: when testing the functionality of your algorithms, make sure the input matrices are square and of the same size, and that their size is a power of 2 (the two mentioned algorithms can only multiply matrices that satisfy these conditions).