Scribd Logo
Upload

Welcome to Scribd!

  • 18 views

    Design and Analysis of Algorithms Assignment 3

    Uploaded by

    Anas
    The document discusses the matrix chain multiplication problem and its solution using dynamic programming. It describes that the problem is to find the most efficient way to multiply a sequence of matrices by minimizing the number of scalar multiplications. It presents the recursive solution to build the optimal solutions for larger subproblems from the optimal solutions of smaller subproblems. The time and space complexity of the algorithm is O(n^3) and O(n^2) respectively. It also provides an example of running the algorithm on a sample input and constructing the optimal parenthesization.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Design and Analysis of Algorithms Assignment 3

    Uploaded by

    Anas
    18 views5 pages
    The document discusses the matrix chain multiplication problem and its solution using dynamic programming. It describes that the problem is to find the most efficient way to multiply a sequence of matrices by minimizing the number of scalar multiplications. It presents the recursive solution to build the optimal solutions for larger subproblems from the optimal solutions of smaller subproblems. The time and space complexity of the algorithm is O(n^3) and O(n^2) respectively. It also provides an example of running the algorithm on a sample input and constructing the optimal parenthesization.

    Original Title

    Daa

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses the matrix chain multiplication problem and its solution using dynamic programming. It describes that the problem is to find the most efficient way to multiply a sequence of matrices by minimizing the number of scalar multiplications. It presents the recursive solution to build the optimal solutions for larger subproblems from the optimal solutions of smaller subproblems. The time and space complexity of the algorithm is O(n^3) and O(n^2) respectively. It also provides an example of running the algorithm on a sample input and constructing the optimal parenthesization.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    18 views5 pages

    Design and Analysis of Algorithms Assignment 3

    Uploaded by

    Anas
    The document discusses the matrix chain multiplication problem and its solution using dynamic programming. It describes that the problem is to find the most efficient way to multiply a sequence of matrices by minimizing the number of scalar multiplications. It presents the recursive solution to build the optimal solutions for larger subproblems from the optimal solutions of smaller subproblems. The time and space complexity of the algorithm is O(n^3) and O(n^2) respectively. It also provides an example of running the algorithm on a sample input and constructing the optimal parenthesization.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 5

    Design and Analysis of Algorithms

    Assignment 3

    Muhammad Anas Qureshi


    BCS213186
    Matrix Chain Multiplication Problem (Dynamic Programming)

    Understanding:
     Goal: Find the most efficient way to multiply a sequence of matrices, minimizing scalar
    multiplications.
     Overlapping Subproblems: Optimal solutions for larger sub chains often reuse those for smaller ones.
     Optimal Substructure: The optimal solution for a larger problem can be built from optimal solutions
    of smaller ones.

    Solution:
     Recursive Structure:
    a. m[i][j] represents the minimum cost to multiply matrices from i to j.
    b. m[i][j] = min(m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]), for k from i to j-1

     Memorization or Tabulation:
    a. Store results of subproblems to avoid redundant calculations.
    b. Fill a table m[i][j] in a bottom-up manner.

    Steps:
     Initialize: Create tables m (n x n) for minimum costs and p (n+1) for dimensions.
     Base Cases: m[i][i] = 0 (single matrix costs 0).
     Fill Table: Iterate through m, filling entries using the recursive formula.
     Find Minimum Cost: The minimum cost is in m[1][n].

    Explanation:
     The recursive formula explores different splits of the matrix chain to find the most efficient one.
     Memorization/tabulation avoids recalculations.
     The bottom-up approach builds solutions for larger subproblems from smaller ones.

    Time Complexity: O(n^3)

    Space Complexity: O(n^2)


    Run on random data:
    Find an optimal parenthesizing of a matrix-chain product whose sequence of dimensions is: (5, 10, 3, 12, 5, 50,
    6).

    We have:
    p0 = 5
    p1 = 10
    p2 = 3
    p3 = 12
    p4 = 5
    p5 = 50
    p6 = 6

    The corresponding matrices are:


    A1 – 5x10 A2 – 10x3 A3 – 3x12 A4 – 12x5 A5 – 5x50 A6 – 50x6

    From the algorithm, we have, for all x, m[x,x] = 0. m[1,2] = m[1,1] + m[2,2] + p0 * p1 * p2

    m[1,2] = 0 + 150
    m[1,2] = 150

    m[3,4] = m[3,3] + m[4,4] + p2 * p3 * p4 m[3,4] = 0 + 180


    m[3,4] = 180

    m[4,5] = m[4,4] + m[5,5] + p3 * p4 * p5 m[4,5] = 0 + 3000


    m[4,5] = 3000

    m[5,6] = m[5,5] + m[6,6] + p4 * p5 * p6 m[5,6] = 0 + 1500


    m[5,6] = 1500

    m[1,3] = min of { m[1,1] + m[2,3] + p0 * p1 * p3 = 750 }


    { m[1,2] + m[3,3] + p0 * p2 * p3 = 330 }

    m[2,4] = min of { m[2,2] + m[3,4] + p1 * p2 * p4 = 330}


    { m[2,3] + m[4,4] + p1 * p3 * p4 = 960}
    m[3,5] = min of { m[3,3] + m[4,5] + p2 * p3 * p5 = 4800}
    { m[3,4] + m[5,5] + p2 * p4 * p5 = 930 }

    m[4,6] = min of { m[4,4] + m[5,6] + p3 * p4 * p6 = 1860 }


    { m[4,5] + m[6,6] + p3 * p5 * p6 = 6600 }

    m[1,4] = min of { m[1,1] + m[2,4] + p0 * p1 * p4 = 580 }


    { m[1,2] + m[3,4] + p0 * p2 * p4 = 405 }
    { m[1,3] + m[4,4] + p0 * p3 * p4 = 630 }

    m[2,5] = min of { m[2,2] + m[3,5] + p1 * p2 * p5 = 2430 }


    { m[2,3] + m[4,5] + p1 * p3 * p5 = 9360 }
    { m[2,4] + m[5,5] + p1 * p4 * p5 = 2830 }

    m[3,6] = min of { m[3,3] + m[4,6] + p2 * p3 * p6 = 2076 }


    { m[3,4] + m[5,6] + p2 * p4 * p6 = 1770 }
    { m[3,5] + m[6,6] + p2 * p5 * p6 = 1830 }

    m[1,5] ={ m[1,1] + m[2,5] + p0 * p1 * p5 = 4930 }


    { m[1,2] + m[3,5] + p0 * p2 * p5 = 1830 }
    { m[1,3] + m[1,4] + p0 * p3 * p5 = 6330 }
    { m[1,4] + m[1,5] + p0 * p4 * p5 = 1655 }

    m[2,6] ={ m[2,2] + m[3,6] + p1 * p2 * p6 = 1950 }


    { m[2,3] + m[4,6] + p1 * p3 * p6 = 2940 }
    { m[2,4] + m[5,6] + p1 * p4 * p6 = 2130 }
    { m[2,5] + m[6,6] + p1 * p5 * p6 = 5430 }

    m[1,6] ={ m[1,1] + m[2,6] + p0 * p1 * p6 = 2250 }


    { m[1,2] + m[3,6] + p0 * p2 * p6 = 2010 }
    { m[1,3] + m[4,6] + p0 * p3 * p6 = 2550 }
    { m[1,4] + m[5,6] + p0 * p4 * p6 = 2055 }
    { m[1,5] + m[6,6] + p0 * p5 * p6 = 3155 }

    M 1 2 3 4 5 6
    6 2010 1950 1770 1840 1500 0
    5 1655 2430 930 3000 0
    4 405 330 180 0
    3 330 360
    2 150
    1 0 The minimum cost is therefore
    2010 and the optimal
    And using this, we construct the S table:
    parenthesizing is:
    ((A1 * A2) * (A3 * A4) * (A5 *
    S 1 2 3 4 5 A6)).
    6 2 2 4 4 5
    5 4 2 4 4
    4 2 2 3
    3 2 2
    2 1

    You might also like