Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 3: Problem 12

Find the optimal order, and its cost, for evaluating the product \(A_{1} \times A_{2} \times A_{3} \times A_{4} \times A_{5}\) where $$\begin{aligned} &A_{1} \text { is }(10 \times 4)\\\ &A_{2} \text { is }(4 \times 5)\\\ &A_{3} \text { is }(5 \times 20)\\\ &A_{4} \text { is }(20 \times 2)\\\ &A_{5} \text { is }(2 \times 50) \end{aligned}$$

Short Answer

Expert verified
The optimal ordering of multiplying these set of matrices starts from \(A_2 \times A_3\), then multiplying this with \(A_1\), then with \(A_4\) and finally with \(A_5\). The minimum cost of scalar multiplications achievable for this optimal multiplication operation is 1900 scalar multiplications.

Step by step solution

01

Understanding the simplistic approach

If we take a simplistic approach, and multiply the matrices in the given order, the operation would be like: ((\((A_1 \times A_2)\) \times A_3 \times A_4 \times A_5)\). The number of scalar multiplications for each matrix multiplication would then look like: \(10 \times 4 \times 5 + 10 \times 5 \times 20 + 10 \times 20 \times 2 + 10 \times 2 \times 50 = 2600\). This approach may not yield the minimal number of scalar multiplications.
02

Using the dynamic programming approach

The dynamic programming approach requires the construction of a table. We first start with smaller matrix multiplications and then gradually build up larger ones. Let's assume M[i][j] will store the minimal scalar multiplications for multiplying a chain of matrices from matrix i to matrix j inclusively.
03

Setting up initial conditions

We'll initialise the primary diagonal of M, (that is when i = j), to be 0, because multiplying a single matrix to itself does not require any scalar multiplications.
04

Filling the table

We will fill the table M by moving in a bottom-up manner. For each cell M[i][j], we will consider all possible multiplications between matrices i to j inclusively by factoring a k, where i <= k < j. We try to minimise the operation M[i][j] = min(M[i][k]+M[k+1][j]+p_i-1×p_k×p_j), where p represents the dimensions of the matrices.
05

Obtaining optimal order and cost

By following this bottom-up approach we can iteratively fill up the entire table M. The minimal cost of scalar multiplications would be given at the cell M[1][n]. Additionally, we can also trace the optimal order of multiplications from the computed table M while making sure we perform the least scalar multiplications.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Find an optimal circuit for the weighted, direct graph represented by the following matrix \(W\) Show the actions step by step.$$W=\left[\begin{array}{ccccc} 0 & 8 & 13 & 18 & 20 \\ 3 & 0 & 7 & 8 & 10 \\ 4 & 11 & 0 & 10 & 7 \\ 6 & 6 & 7 & 0 & 11 \\ 10 & 6 & 2 & 1 & 0 \end{array}\right]$$

Write an efficient algorithm that will find an optimal order for multiplying \(n\) matrices \(A_{1} \times A_{2}\) \(x \ldots x A_{n},\) where the dimension of each matrix is \(1 \times 1,1 \times d, d \times 1,\) or \(d \times d\) for some positive integer \(d\). Analyze your algorithm and show the results using order notation.

Create the optimal binary search tree for the following items, where the probability occurrence of each word is given in parentheses: CASE (.05), ELSE (.15), END (.05), IF (.35), OF (.05), THEN (.35)

Find an efficient way to compute \(\sum_{m=i}^{j} p_{m},\) used in the Optimal Binary Search Tree algorithm (Algorithm 3.9).

Let us consider two sequences of characters \(S_{1}\) and \(S_{2}\). For example, we could have \(S_{1}-\) \(\mathrm{A} \$ \mathrm{CMA}^{*} \mathrm{MN}\) and \(S_{2}=\mathrm{AXMC} 4 \mathrm{ANB}\). Assuming that a subsequence of a sequence can be constructed by deleting any number of characters from any positions, use the dynamic programming approach to create an algorithm that finds the Iongest common subsequence of \(S_{1}\) and \(S_{2}\). This algorithm returns the maximum-length common subsequence of each sequence.
See all solutions

Recommended explanations on Computer Science Textbooks

Data Structures

Read Explanation

Computer Organisation and Architecture

Read Explanation

Issues in Computer Science

Read Explanation

Computer Network

Read Explanation

Algorithms in Computer Science

Read Explanation

Theory of Computation

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free