Multiplication order
- Algorithms course
- Advanced
- Lesson 21/56
- 4 min
Parenthesisation changes matrix chain cost.
Multiplication order
Matrix multiplication is associative but cost depends on order. (A1·A2)·A3 and A1·(A2·A3) need different numbers of scalar multiplications.
The goal is to find the parenthesization with the fewest scalar multiplications. This is a classic dynamic programming problem.
Dimension array
Each matrix is described by a dimension pair: Ai has size dims[i-1] × dims[i]. For example dims = [10, 20, 30, 40] gives three matrices.
Multiplying two adjacent matrices takes dims[i-1] × dims[i] × dims[i+1] scalar multiplications. This is the basis of the cost.
Practice init_dims function
Write init_dims(). Return the list [10, 20, 30, 40]. Print it with print(init_dims()).
Starter code
def init_dims():
# Return dimension arraySample solution
def init_dims():
# Return dimension array
return [10, 20, 30, 40]
print(init_dims())Expected output
[10, 20, 30, 40]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What does the best order minimize for three matrices?
- Scalar multiplication count Correct answer
- Matrix size
- Memory usage
- Loop count
Explanation: The best order minimizes scalar multiplications.
2 Dimension array definition
dims = ____dims = [10, 20, 30, 40]Explanation: [10, 20, 30, 40] is right.
3 Multiplication order: match the terms
| Term | Meaning |
|---|---|
A1 |
10×20 |
A2 |
20×30 |
A3 |
30×40 |
dims |
Dimension array |