Chapter 6, Problem 6.6.2E

Program Plan Intro

Parallelism:

The state of being parallel and having correspondence among them is referred as parallelism. Two or more tasks can be performed simultaneously, without affecting the performance of the either one.

Given Information:

It is given that for the following recursive merge sort algorithm, the basic idea is to divide an unsorted list x of m elements into two sub lists of about half the size of the original list. It is also assumed that “Y” is equal to length (m).

Matrix multiplication:

Two matrixes can be multiplied if the number of columns of the first matrix is equal to the number of rows in the second.

Let's assume we have an m x n matrix A and we want to multiply it by an n x p matrix B. We can express their product as an m x p matrix denoted by AB (or A dot B).

If we assign C = AB and $c_{i,j}$ denotes the entry C at position (i, j), then for each element i and j with $c_{i,j}$ $1<=i<=m$ and $1<=j<=p$. It is assumed that matrices are laid out in memory sequential as follows:

a1,1 , a2,1 , a3,1 ... etc.