CSE201, Winter 2025, Lec 9: The optimal parentheses for Matrix Multiplication, and DAG optimization
C. Seshadhri · 81:15
The lecture shows how to choose an optimal parenthesization for a chain of matrix multiplications using dynamic programming, then argues that this is the same pattern as path optimization on a DAG—and that every DP ta...