matrices

Question 1

What is the run time to Matrix sum two n by n matrices?

Answer 1

Theta of (n²)

Question 2

What is the naive algo for matrix mult with the run time?

Answer 2

3 nest loops

for i < n

for j < n

for k < n

c[i][j] += a[i][k] * b[k][j]

Run time: Theta of (n³)

Question 3

For matrice multiplication, what happens during

Divide

Conquer

Combine

Answer 3

Question 4

What is the run time analysis of divide-and-conquer for multiplying two n-by-b matrices? (in general)

Answer 4

Question 5

User the Master thereom to determine the run time of the divide and conquer algorithm listed below

Answer 5

Question 6

what is the recursive formula for Strassen Algorithm.

What is the run time?

Answer 6

Question 7

Strassen Algorithm:

What are the following actions:

Divide

Conquer

Combine

Basecase

Answer 7

Question 8

For matrix multiplication how are each of the C cells determined?

Answer 8

Question 9

Using strassed Algorithm

How are the C cells determined?

Answer 9

Question 10

In general, how do you prove the correctness of the Strassen algorithm?

Answer 10

Show that after all the required calculations the c cells equal what they should: see below