Understanding Dynamic Programming: Chain Matrix Multiplication Concepts
Dive into the world of dynamic programming with a focus on chain matrix multiplication. Explore key concepts such as optimal substructure, recurrence relations, and cost calculations to efficiently multiply matrices. Enhance your understanding of algorithm design and analysis through detailed explanations and examples.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSCI 3160 Design and Analysis of Algorithms Tutorial 5 Chengyu Lin
Outline Dynamic programming Chain Matrix Multiplication Longest increasing subsequence (LIS) Goal: help understand the lecture materials further
Dynamic programming A method for solving complex problems by breaking them down into simpler subproblems (from Wikipedia) Three steps Find the optimal substructure Formulate the problem recursively Compute the values bottom up
Chain Matrix Multiplication You want to multiply N matrices A1, , AN Suppose the cost of multiplying an m-by-n matrix with an n-by-l matrix is mnl. The product is an m-by-l matrix What is the minimum total cost to get the product of the N matrices P = A1 AN?
Chain Matrix Multiplication Each order of multiplication corresponds to a parenthesization ((A1(A2A3))(A4((A5A6)A7))) Optimal substructure If the above parenthesization is optimal, then (A1(A2A3)) is optimal for multiplying A1, , A3 (A4((A5A6)A7)) is optimal for multiplying A4, , A7 ((A5A6)A7) is optimal for multiplying A5, , A7 Every subparenthesization of an optimal parenthesization is optimal
Chain Matrix Multiplication Recurrence Let C(i,j) be the optimal cost of multiplying Ai, Aj C(i,i) = 0 for any i (No multiplication needed) C(i,j) = mini k j-1{C(i,k) + C(k+1,j) + mi-1mkmj } for i j-1 Build an N-by-N matrix to store the C(i,j) s Our optimal value is then C(1,N) mi (Ai) mi-1
Example Let A1 be a 5-by-20 matrix, A2 be a 20-by-10 matrix, A3 be a 10-by-3 matrix, A4 be a 3-by-2 matrix m0 = 5, m1 = 20, m2 = 10, m3 = 3, m4 = 2 i \ j 1 2 3 4 1 0 2 - 0 3 - - 0 4 - - - 0
Example m0 = 5, m1 = 20, m2 = 10, m3 = 3, m4 = 2 C(1,2) = C(1,1) + C(2,2) + m0m1m2 = 5 20 10 = 1000 C(2,3) = , C(3,4) = . i \ j 1 2 3 4 1 0 1000 2 - 0 3 - - 0 4 - - - 0
Example m0 = 5, m1 = 20, m2 = 10, m3 = 3, m4 = 2 C(1,2) = C(1,1) + C(2,2) + m0m1m2 = 5 20 10 = 1000 C(2,3) = 600, C(3,4) = 60. i \ j 1 2 3 4 1 0 1000 2 - 0 600 3 - - 0 60 4 - - - 0
Example m0 = 5, m1 = 20, m2 = 10, m3 = 3, m4 = 2 C(1,3) = min { C(1,1) + C(2,3) + m0m1m3, C(1,2) + C(3,3) + m0m2m3 } = min { 0 + 600 + 300, 1000 + 0 + 150 } = 900 i \ j 1 2 3 4 1 0 1000 900 2 - 0 600 3 - - 0 60 4 - - - 0
Example m0 = 5, m1 = 20, m2 = 10, m3 = 3, m4 = 2 C(2,4) = min { C(2,2) + C(3,4) + m1m2m4, C(2,3) + C(4,4) + m1m3m4 } = min { 0 + 60 + 400, 600 + 0 + 30 } = 460 i \ j 1 2 3 4 1 0 1000 900 2 - 0 600 460 3 - - 0 60 4 - - - 0
Example m0 = 5, m1 = 20, m2 = 10, m3 = 3, m4 = 2 C(1,4) = min { C(1,1) + C(2,4) + m0m1m4, = min { 0 + 460 + 200, = . , } , } i \ j 1 2 3 4 1 0 1000 900 2 - 0 600 460 3 - - 0 60 4 - - - 0
Example m0 = 5, m1 = 20, m2 = 10, m3 = 3, m4 = 2 C(1,4) = min { C(1,1) + C(2,4) + m0m1m4, C(1,2) + C(3,4) + m0m2m4, C(1,3) + C(4,4) + m0m3m4 } = min { 0 + 460 + 200, 1000 + 60 + 100, 900 + 0 + 30 } = 660. i \ j 1 2 3 4 1 0 1000 900 660 2 - 0 600 460 3 - - 0 60 4 - - - 0
Example Hence, the optimal cost of computing P = A1 A4is 660. i \ j 1 2 3 4 1 0 1000 900 660 2 - 0 600 460 3 - - 0 60 4 - - - 0
Analysis Space complexity = O(N2) Time complexity = O(N3) A for loop (k = i .. j-1) is run every time we compute the value of a table entry
Longest increasing subsequence (LIS) Given a sequence of N integers a1, , aN, find a subsequence ai1, , aik(1 i1< < ik N) such that Increasing: ai1< < aik Longest: its length k is maximum among all increasing subsequences Example: 3, 1, 6, 0, 8 Can you give another LIS?
Longest increasing subsequence (LIS) We can construct a graph 3 1 6 0 8 Optimal substructure If ai1, , aik is an LIS ending at position ik, then ai1, , aij is an LIS ending at position ij for any j k In the language of longest paths: a subpath of a longest path is longest
Longest increasing subsequence (LIS) Add an imaginary node - at the front - 3 1 6 0 8 Recurrence Let L(j) be the length of the LIS ending at position j L(0) = 0 L(j) = 1 + maxi : ai < aj L(i), for j 1 Our longest length is then maxj L(j)
Example Use a linear array to store the values - 3 1 6 0 8 j 0 1 2 3 4 5 L(j) 0
Example - 3 1 6 0 8 j 0 1 2 3 4 5 L(j) 0 1
Example - 3 1 6 0 8 j 0 1 2 3 4 5 L(j) 0 1 1
Example - 3 1 6 0 8 j 0 1 2 3 4 5 L(j) 0 1 1 2
Example - 3 1 6 0 8 j 0 1 2 3 4 5 L(j) 0 1 1 2 1
Example - 3 1 6 0 8 j 0 1 2 3 4 5 L(j) 0 1 1 2 1 3
Example - 3 1 6 0 8 j 0 1 2 3 4 5 L(j) 0 1 1 2 1 3 Length of LIS = maxj L(j) = 3
Analysis Space complexity = O(N) O(N2) if you store the graph, since there can be (N) arrows pointing to a node Time complexity = O(N2) Each arrow is gone through once
End Questions
