Transcript PPT

Dynamic Programming 2
Neil Tang
4/22/2008
CS223 Advanced Data Structures and Algorithms
1
Course Survey
Please complete the course survey by May 3 (Sat) at:
http://www.cs.montana.edu/survey/
CS223 Advanced Data Structures and Algorithms
2
Class Overview
 Basic idea
 Matrix multiplication
 Ordering matrix multiplication
CS223 Advanced Data Structures and Algorithms
3
Basic Idea
 Mathematically express the problem in the recursive form.
 Solve it by a non-recursive algorithm that systematically
records the answers to the subproblems in a table.
CS223 Advanced Data Structures and Algorithms
4
Matrix Multiplication
 C=AB.
 If the size of A is wy, then the size of B must be yz, i.e.,
the number of columns of A must be equal to the number of
rows of B.
y
 The size of C is wz and
cij   aihbhj
h 1
CS223 Advanced Data Structures and Algorithms
5
An Example
 Compute ABCD with |A|=5010, |B| = 1040, |C|=4030
and |D|=305.
 (((AB)C)D) involves 20,000+60,000+7,500 =87,500
multiplications.
 (A((BC)D)) involves 12,000+1,500+2,500 =16,000
multiplications.
 (A(B(CD))) involves 6,000+2,000+2,500 =10,500
multiplications.
CS223 Advanced Data Structures and Algorithms
6
Ordering Matrix Multiplications
 Consider AleftAleft+1…Ai…Aright
 mleft,right =
min leftiright {mleft,i + mi+1,right+cleft-1cicright}
CS223 Advanced Data Structures and Algorithms
7
Ordering Matrix
Multiplications
The time
complexity is O(n3)
CS223 Advanced Data Structures and Algorithms
8
Another Example
right
left
right
CS223 Advanced Data Structures and Algorithms
left
9