matrices Flashcards Preview

Comp 2080 Algos > matrices > Flashcards

Flashcards in matrices Deck (10)
Loading flashcards...
1
Q

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

A

Theta of (n2)

2
Q

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

A

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 (n3)

3
Q

For matrice multiplication, what happens during

Divide

Conquer

Combine

A
4
Q

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

A
5
Q

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

A
6
Q

what is the recursive formula for Strassen Algorithm.

What is the run time?

A
7
Q

Strassen Algorithm:

What are the following actions:

Divide

Conquer

Combine

Basecase

A
8
Q

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

A
9
Q

Using strassed Algorithm

How are the C cells determined?

A
10
Q

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

A

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