Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Fundamentals of Algorithms - CS502 > Chapter 19 > Flashcards

Chapter 19 Flashcards

1
Q

What is chain matrix multiplication

A

In multiple chain of given sequence matrices, where dimension also identified, determine the order of multiplication so that there will be minimum number of operations.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

How much entries in matrix

A

theta (n square)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Each entry takes how much time in chain matrix multiplication

A

theta(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is total running time in chain matrix multiplication

A

theta (n square)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Does matrix multiplication associative or commutative operation

A

Associative

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is Catalan numbers

A

The P(n) recurrence in chain matrix multiplication is related to a famous function called Catalan numbers. Catalan numbers are related to the number of different binary trees on n nodes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is catalan formula

A

C(n) = 1/n+1(2n n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What will be the result of highest level of parenthesization we multiply two matrices

A

1..n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly

Fundamentals of Algorithms - CS502 (40 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions