Scribd
Upload
34 views2 pages

Matrix Multiplication

This document describes how to implement an efficient matrix multiplication algorithm based on Strassen's method for multiplying two square matrices of size N×N, where N is a power of 2. The algorithm should have complexity less than O(N^3). It will be evaluated based on correctness on sample cases and efficiency on large unseen cases, with bonuses for faster performance compared to the naive algorithm. The function signature and examples are provided.

Uploaded by

Mostafa Elkaramany
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
34 views2 pages

Matrix Multiplication

This document describes how to implement an efficient matrix multiplication algorithm based on Strassen's method for multiplying two square matrices of size N×N, where N is a power of 2. The algorithm should have complexity less than O(N^3). It will be evaluated based on correctness on sample cases and efficiency on large unseen cases, with bonuses for faster performance compared to the naive algorithm. The function signature and examples are provided.

Uploaded by

Mostafa Elkaramany
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Matrix Multiplication

Description
Given TWO square matrices of size N×N, implement an efficient algorithm based on Strassen’s
method to multiply them?

NOTE:

 N is power of 2 (i.e. 2, 4, 8, 16, 32… 2i)

Complexity
The complexity of your algorithm should be less than O(N3)

Evaluation
Sample Cases UNSEEN Large Cases
Total
(Correctness) (Efficiency)

2 Marks 6 Marks 8 MARKS

Bonus & Competition#2


Criteria BONUS

Just Faster +1 Mark


Vs. Naïve
1x Faster +3 Marks
(on Large Cases)
[N]x Faster +[N]x2 Marks

TOP5 Correct & Speed 2~4 Marks

Function: Implement it!

static public int[,] MatrixMultiply(int[,] M1, int[,] M2, int N)

MatrixMultiplication.cs includes this method.


Examples
EX#1 EX#2
M1: M2: M1: M2:
1 1 1 1 1 -1 1 -1 -1 1 -1 1
1 0 1 0 1 -1 1 -1 -1 1 -1 1
1 -1 1 -1 -1 1 -1 1
1 -1 1 -1 -1 1 -1 1
Res: Res:
2 1 0 0 0 0
1 1 0 0 0 0
0 0 0 0
0 0 0 0

C# Help
Getting the size of 1D array
int size = array1D.GetLength(0);

Getting the size of 2D array


int size1 = array2D.GetLength(0);

int size2 = array2D.GetLength(1);

Creating 1D array
int [] array1D = new int [size]

Creating 2D array
int [,] array2D = new int [size1, size2]

Sorting single array


Sort the given array "items" in ascending order

Array.Sort(items);

Sorting parallel arrays


Sort the first array "master" and re-order the 2nd array "slave" according to this sorting

Array.Sort(master, slave);

You might also like