Exercises · Pseudo-code

Exercises · Chapter 2 · each solution opens with a click · Chapter 2: Pseudo-code · Exercises, volume 1 (PDF)

Exercise 2.1: Pseudo-code (E1)

Given an array \(a[1..n]\) of \(n \ge 1\) integer numbers, consider the problem of determining the minimum value in the array.

Questions

1. Write the pseudo-code of an algorithm that finds the minimum value in an array \(a\) of \(n\) integer numbers. The algorithm should:

   • take as input an array \(a[1..n]\) of \(n \ge 1\) integer numbers;

   • return the minimum value \(min\) in the array;

   • use a single pass through the array.

2. Execute the algorithm step by step on the following instances:

   • Instance 1: \(a = [9, 12, 3, 16, 19, 11, 12]\) with \(n=7\);

   • Instance 2: \(a = [15, 7, 22, 4]\) with \(n=4\);

   • Instance 3: \(a = [100]\) with \(n=1\).

   For each instance, show the initial state of the variables, their state after each iteration, and the final result.

3. Write the pseudo-code of an algorithm that finds both the maximum and the minimum values in a single pass through the array.

Solution

1. Pseudo-code for finding the minimum value in an array:

   Algorithm: FindMinimum

   Input: An array \(a[1..n]\) of \(n \ge 1\) integer numbers

   Output: The minimum value in the array \(a\)

   1function FindMinimum(a, n)

   2\(min := a[1]\)

   3for \(i := 2\) to \(n\) do

   4if \(a[i] < min\) then

   5\(min \leftarrow a[i]\)

   6end

   7end

   8return \(min\)

   9end

   • We initialize \(min\) to \(a[1]\), the first element (it exists, since \(n \ge 1\)).

   • We iterate through each remaining element of the array, comparing it with the current minimum.

   • If the current element is smaller, we update the minimum.

   • Finally, we return the minimum value found.

2. Step-by-step execution on the instances.

   Instance 1: \(a = [9, 12, 3, 16, 19, 11, 12]\), \(n=7\)

   \(i\)	\(a[i]\)	\(a[i] < min\)?	\(min\)
   –	–	–	\(9\)
   \(2\)	\(12\)	No	\(9\)
   \(3\)	\(3\)	Yes	\(3\)
   \(4\)	\(16\)	No	\(3\)
   \(5\)	\(19\)	No	\(3\)
   \(6\)	\(11\)	No	\(3\)
   \(7\)	\(12\)	No	\(3\)

   Return: \(min = 3\)

   Instance 2: \(a = [15, 7, 22, 4]\), \(n=4\)

   \(i\)	\(a[i]\)	\(a[i] < min\)?	\(min\)
   –	–	–	\(15\)
   \(2\)	\(7\)	Yes	\(7\)
   \(3\)	\(22\)	No	\(7\)
   \(4\)	\(4\)	Yes	\(4\)

   Return: \(min = 4\)

   Instance 3: \(a = [100]\), \(n=1\)

   \(i\)	\(a[i]\)	\(a[i] < min\)?	\(min\)
   –	–	–	\(100\)
   no iterations: the loop starts at \(i = 2 > n = 1\)

   Return: \(min = 100\)

3. Pseudo-code to find both the maximum and the minimum in a single pass:

   Algorithm: FindMaxMin

   Input: An array \(a[1..n]\) of \(n \ge 1\) integer numbers

   Output: The pair \((max, min)\), where \(max\) is the maximum and \(min\) is the minimum of \(a\)

   1function FindMaxMin(a, n)

   2\(max := a[1]\)

   3\(min := a[1]\)

   4for \(i := 2\) to \(n\) do

   5if \(a[i] > max\) then

   6\(max \leftarrow a[i]\)

   7end

   8if \(a[i] < min\) then

   9\(min \leftarrow a[i]\)

   10end

   11end

   12return \(max\), \(min\)

   13end

   For example, on Instance 1 (\(a = [9, 12, 3, 16, 19, 11, 12]\)) the algorithm returns \((19, 3)\).

Exercise 2.2: Pseudo-code (E2)

Given an array \(a[1..n]\) of \(n \ge 1\) integer numbers, consider the problem of computing the sum of its values.

Questions

1. Write the pseudo-code of an algorithm that computes the sum of all the elements of an array \(a\) of \(n\) integer numbers. The algorithm should:

   • take as input an array \(a[1..n]\) of \(n \ge 1\) integer numbers;

   • return the sum \(sum\) of all the elements;

   • initialize a variable \(sum\) to \(0\) and add each element to it.

2. Execute the algorithm step by step on the following instances:

   • Instance 1: \(a = [5, 12, 3, 8]\) with \(n=4\);

   • Instance 2: \(a = [10, 20, 30]\) with \(n=3\);

   • Instance 3: \(a = [7]\) with \(n=1\).

   For each instance, show the initial value of the sum, its value after adding each element, and the final result.

3. Modify the pseudo-code to compute both the sum and the average \(avg = \frac{sum}{n}\) of the elements, with a single pass through the array.

Solution

1. Pseudo-code for computing the sum of all the elements of an array:

   Algorithm: ArraySum

   Input: An array \(a[1..n]\) of \(n \ge 1\) integer numbers

   Output: The sum of all the elements of the array \(a\)

   1function ArraySum(a, n)

   2\(sum := 0\)

   3for \(i := 1\) to \(n\) do

   4\(sum \leftarrow sum + a[i]\)

   5end

   6return \(sum\)

   7end

   • We initialize \(sum\) to \(0\).

   • We iterate through each element of the array, adding it to the running \(sum\).

   • Finally, we return the total \(sum\).

2. Step-by-step execution on the instances.

   Instance 1: \(a = [5, 12, 3, 8]\), \(n=4\)

   \(i\)	\(a[i]\)	\(sum\)
   –	–	\(0\)
   \(1\)	\(5\)	\(5\)
   \(2\)	\(12\)	\(17\)
   \(3\)	\(3\)	\(20\)
   \(4\)	\(8\)	\(28\)

   Return: \(sum = 28\)

   Instance 2: \(a = [10, 20, 30]\), \(n=3\)

   \(i\)	\(a[i]\)	\(sum\)
   –	–	\(0\)
   \(1\)	\(10\)	\(10\)
   \(2\)	\(20\)	\(30\)
   \(3\)	\(30\)	\(60\)

   Return: \(sum = 60\)

   Instance 3: \(a = [7]\), \(n=1\)

   \(i\)	\(a[i]\)	\(sum\)
   –	–	\(0\)
   \(1\)	\(7\)	\(7\)

   Return: \(sum = 7\)

3. Pseudo-code to compute both the sum and the average:

   Algorithm: ArraySumAndAverage

   Input: An array \(a[1..n]\) of \(n \ge 1\) integer numbers

   Output: The pair \((sum, avg)\), where \(sum\) is the total and \(avg\) is the average of the elements

   1function ArraySumAndAverage(a, n)

   2\(sum := 0\)

   3for \(i := 1\) to \(n\) do

   4\(sum \leftarrow sum + a[i]\)

   5end

   6\(avg := sum / n\)

   7return \(sum\), \(avg\)

   8end

   The precondition \(n \ge 1\) guarantees that the division \(sum / n\) is defined. For example, on Instance 1 (\(a = [5, 12, 3, 8]\), \(n=4\)) the algorithm returns \((28, 7)\), since the sum is \(28\) and the average is \(28/4 = 7\).

Exercise 2.3: Pseudo-code (E3)

Given a two-dimensional array \(b[1..m][1..n]\) of \(m \times n\) integer numbers and a threshold value \(k\), consider the problem of counting the number of its values strictly greater than \(k\).

Questions

1. Write the pseudo-code of an algorithm that counts how many elements of \(b\) are strictly greater than the threshold \(k\). The algorithm should:

   • take as input a two-dimensional array \(b[1..m][1..n]\), the dimensions \(m\) and \(n\), and the threshold \(k\);

   • return the number of elements satisfying \(b[i][j] > k\);

   • scan all the entries of the array with two nested loops.

2. Execute the algorithm step by step on the following instances, showing the value of \(count\) after each update:

   • Instance 1: \(b = \begin{bmatrix} 3 & 7 & 1 \\ 5 & 2 & 8 \end{bmatrix}\), \(m=2\), \(n=3\), \(k=4\);

   • Instance 2: \(b = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}\), \(m=3\), \(n=3\), \(k=5\).

3. Modify the pseudo-code so that, in addition to the count, the algorithm also returns an array of pairs \((i, j)\) listing the positions of all the elements of the two-dimensional array greater than \(k\).

Solution

1. Pseudo-code for counting the elements greater than a threshold:

   Algorithm: CountGreaterThan

   Input: A two-dimensional array \(b[1..m][1..n]\), the dimensions \(m\) and \(n\), and a threshold \(k\)

   Output: The number \(count\) of elements with \(b[i][j] > k\)

   1function CountGreaterThan(b, m, n, k)

   2\(count := 0\)

   3for \(i := 1\) to \(m\) do

   4for \(j := 1\) to \(n\) do

   5if \(b[i][j] > k\) then

   6\(count \leftarrow count + 1\)

   7end

   8end

   9end

   10return \(count\)

   11end

   • We initialize \(count\) to \(0\).

   • The outer loop iterates over the rows \(i = 1, 2, \dots, m\), the inner loop over the columns \(j = 1, 2, \dots, n\).

   • For each entry \(b[i][j]\), if it exceeds \(k\) we increase \(count\).

   • Finally, we return \(count\).

2. Step-by-step execution on the instances.

   Instance 1: \(b = \begin{bmatrix} 3 & 7 & 1 \\ 5 & 2 & 8 \end{bmatrix}\), \(m=2\), \(n=3\), \(k=4\)

   \(i\)	\(j\)	\(b[i][j]\)	\(b[i][j] > 4\)?	\(count\)
   –	–	–	–	\(0\)
   \(1\)	\(1\)	\(3\)	No	\(0\)
   \(1\)	\(2\)	\(7\)	Yes	\(1\)
   \(1\)	\(3\)	\(1\)	No	\(1\)
   \(2\)	\(1\)	\(5\)	Yes	\(2\)
   \(2\)	\(2\)	\(2\)	No	\(2\)
   \(2\)	\(3\)	\(8\)	Yes	\(3\)

   Return: \(count = 3\) (elements \(7\), \(5\), \(8\))

   Instance 2: \(b = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix}\), \(m=3\), \(n=3\), \(k=5\)

   \(i\)	\(j\)	\(b[i][j]\)	\(b[i][j] > 5\)?	\(count\)
   –	–	–	–	\(0\)
   \(1\)	\(1\)	\(1\)	No	\(0\)
   \(1\)	\(2\)	\(2\)	No	\(0\)
   \(1\)	\(3\)	\(3\)	No	\(0\)
   \(2\)	\(1\)	\(4\)	No	\(0\)
   \(2\)	\(2\)	\(5\)	No	\(0\)
   \(2\)	\(3\)	\(6\)	Yes	\(1\)
   \(3\)	\(1\)	\(7\)	Yes	\(2\)
   \(3\)	\(2\)	\(8\)	Yes	\(3\)
   \(3\)	\(3\)	\(9\)	Yes	\(4\)

   Return: \(count = 4\) (elements \(6\), \(7\), \(8\), \(9\))

3. Pseudo-code returning also the positions of the elements greater than \(k\). The array \(pos\) is declared with \(m \cdot n\) elements, the largest possible number of positions; only its first \(count\) elements are used.

   Algorithm: CountAndListGreaterThan

   Input: A two-dimensional array \(b[1..m][1..n]\), the dimensions \(m\) and \(n\), and a threshold \(k\)

   Output: The number \(count\) and the array \(pos[1..count]\) of the pairs \((i,j)\) with \(b[i][j] > k\)

   1function CountAndListGreaterThan(b, m, n, k)

   2\(count := 0\)

   3\(pos := \text{new array}[1..m \cdot n]\)

   4for \(i := 1\) to \(m\) do

   5for \(j := 1\) to \(n\) do

   6if \(b[i][j] > k\) then

   7\(count \leftarrow count + 1\)

   8\(pos[count] \leftarrow (i, j)\)

   9end

   10end

   11end

   12return \(count\), \(pos[1..count]\)

   13end

   For Instance 1, the algorithm returns \(count=3\) and \(pos = [(1,2),(2,1),(2,3)]\); for Instance 2, it returns \(count = 4\) and \(pos = [(2,3),(3,1),(3,2),(3,3)]\).

Exercise 2.4: Pseudo-code (E4)

Given a two-dimensional array \(b[1..m][1..n]\) of \(m \times n\) integer numbers, with \(m \ge 1\) and \(n \ge 1\), consider the problem of finding the minimum value of each column.

Questions

1. Write the pseudo-code of an algorithm that computes the minimum of each column of the two-dimensional array \(b\). The algorithm should:

   • take as input a two-dimensional array \(b[1..m][1..n]\) and the dimensions \(m\), \(n\);

   • return an array \(colMin[1..n]\), where the element \(colMin[j]\) is the minimum of the column \(j\);

   • iterate over the columns and the rows with two nested loops.

2. Execute the algorithm step by step on the following instances, showing each update of the array \(colMin\):

   • Instance 1: \(b = \begin{bmatrix} 4 & 9 & 2 \\ 7 & 1 & 6 \\ 3 & 5 & 8 \end{bmatrix}\), \(m=3\), \(n=3\);

   • Instance 2: \(b = \begin{bmatrix} 8 & 3 \\ 5 & 7 \\ 2 & 4 \end{bmatrix}\), \(m=3\), \(n=2\).

3. Modify the pseudo-code so that, in addition to the minimum value of each column, the algorithm also returns the first row index \(rowIdx[j]\) where the minimum of column \(j\) is located.

Solution

1. Pseudo-code for computing the column minima:

   Algorithm: ColumnMinima

   Input: A two-dimensional array \(b[1..m][1..n]\), the dimensions \(m \ge 1\) and \(n \ge 1\)

   Output: An array \(colMin[1..n]\), where \(colMin[j]\) is the minimum of column \(j\)

   1function ColumnMinima(b, m, n)

   2\(colMin := \text{new array}[1..n]\)

   3for \(j := 1\) to \(n\) do

   4\(colMin[j] \leftarrow b[1][j]\)

   5for \(i := 2\) to \(m\) do

   6if \(b[i][j] < colMin[j]\) then

   7\(colMin[j] \leftarrow b[i][j]\)

   8end

   9end

   10end

   11return \(colMin\)

   12end

   • The outer loop iterates over the columns \(j = 1, 2, \dots, n\).

   • We initialize \(colMin[j]\) to \(b[1][j]\), the first element of column \(j\).

   • The inner loop scans the rows \(i = 2, 3, \dots, m\), comparing each entry with the current minimum of the column, and updates \(colMin[j]\) when a smaller element is found.

   • Finally, we return the array \(colMin\).

2. Step-by-step execution on the instances.

   Instance 1: \(b = \begin{bmatrix} 4 & 9 & 2 \\ 7 & 1 & 6 \\ 3 & 5 & 8 \end{bmatrix}\), \(m=3\), \(n=3\)

   Column \(j=1\)

   \(i\)	\(b[i][1]\)	\(<\)?	\(colMin[1]\)
   –	–	–	\(4\)
   \(2\)	\(7\)	No	\(4\)
   \(3\)	\(3\)	Yes	\(3\)

   Column \(j=2\)

   \(i\)	\(b[i][2]\)	\(<\)?	\(colMin[2]\)
   –	–	–	\(9\)
   \(2\)	\(1\)	Yes	\(1\)
   \(3\)	\(5\)	No	\(1\)

   Column \(j=3\)

   \(i\)	\(b[i][3]\)	\(<\)?	\(colMin[3]\)
   –	–	–	\(2\)
   \(2\)	\(6\)	No	\(2\)
   \(3\)	\(8\)	No	\(2\)

   The column \(<\)? reports the outcome of the comparison \(b[i][j] < colMin[j]\).

   Return: \(colMin = [3, 1, 2]\)

   Instance 2: \(b = \begin{bmatrix} 8 & 3 \\ 5 & 7 \\ 2 & 4 \end{bmatrix}\), \(m=3\), \(n=2\)

   Column \(j=1\)

   \(i\)	\(b[i][1]\)	\(<\)?	\(colMin[1]\)
   –	–	–	\(8\)
   \(2\)	\(5\)	Yes	\(5\)
   \(3\)	\(2\)	Yes	\(2\)

   Column \(j=2\)

   \(i\)	\(b[i][2]\)	\(<\)?	\(colMin[2]\)
   –	–	–	\(3\)
   \(2\)	\(7\)	No	\(3\)
   \(3\)	\(4\)	No	\(3\)

   Return: \(colMin = [2, 3]\)

3. Pseudo-code returning also the row index of each column minimum. The update uses the strict comparison \(<\), so in case of ties the first row is kept.

   Algorithm: ColumnMinimaWithIndex

   Input: A two-dimensional array \(b[1..m][1..n]\), the dimensions \(m \ge 1\) and \(n \ge 1\)

   Output: The arrays \(colMin[1..n]\) and \(rowIdx[1..n]\)

   1function ColumnMinimaWithIndex(b, m, n)

   2\(colMin := \text{new array}[1..n]\)

   3\(rowIdx := \text{new array}[1..n]\)

   4for \(j := 1\) to \(n\) do

   5\(colMin[j] \leftarrow b[1][j]\)

   6\(rowIdx[j] \leftarrow 1\)

   7for \(i := 2\) to \(m\) do

   8if \(b[i][j] < colMin[j]\) then

   9\(colMin[j] \leftarrow b[i][j]\)

   10\(rowIdx[j] \leftarrow i\)

   11end

   12end

   13end

   14return \(colMin\), \(rowIdx\)

   15end

   For Instance 1, the algorithm returns \(colMin = [3,1,2]\) and \(rowIdx = [3,2,1]\); for Instance 2, it returns \(colMin = [2, 3]\) and \(rowIdx = [3, 1]\).

Exercise 2.5: Pseudo-code (E5)

Given a two-dimensional array \(b[1..m][1..n]\) of \(m \times n\) integer numbers, consider the problem of computing its transposed two-dimensional array, i.e., the two-dimensional array \(c[1..n][1..m]\) with \(c[j][i] = b[i][j]\).

Questions

1. Write the pseudo-code of an algorithm that computes the transpose of a two-dimensional array \(b[1..m][1..n]\). The algorithm should:

   • take as input a two-dimensional array \(b[1..m][1..n]\) and the dimensions \(m\), \(n\);

   • allocate a new two-dimensional array \(c[1..n][1..m]\) for the result;

   • return the transposed two-dimensional array \(c\), such that \(c[j][i] = b[i][j]\).

2. Execute the algorithm step by step on the following instances, showing the two-dimensional array \(c\) being filled entry by entry:

   • Instance 1: \(b = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}\), \(m=2\), \(n=3\);

   • Instance 2: \(b = \begin{bmatrix} 7 & 2 \\ 3 & 8 \\ 1 & 5 \end{bmatrix}\), \(m=3\), \(n=2\).

3. For a square two-dimensional array (\(m = n\)), write the pseudo-code of an algorithm that performs the transposition in place (without allocating a new two-dimensional array), by exchanging the elements \(b[i][j]\) and \(b[j][i]\) for all \(i < j\).

Solution

1. Pseudo-code for the transposition of a two-dimensional array:

   Algorithm: Transpose

   Input: A two-dimensional array \(b[1..m][1..n]\), the dimensions \(m\) and \(n\)

   Output: The transposed two-dimensional array \(c[1..n][1..m]\)

   1function Transpose(b, m, n)

   2\(c := \text{new array}[1..n][1..m]\)

   3for \(i := 1\) to \(m\) do

   4for \(j := 1\) to \(n\) do

   5\(c[j][i] \leftarrow b[i][j]\)

   6end

   7end

   8return \(c\)

   9end

   • We allocate \(c\) as a new \(n \times m\) two-dimensional array.

   • The outer loop iterates over the rows \(i = 1, 2, \dots, m\) of \(b\), the inner loop over the columns \(j = 1, 2, \dots, n\) of \(b\).

   • Each entry \(b[i][j]\) is copied to the position \(c[j][i]\); every entry of \(c\) is assigned exactly once.

   • Finally, we return the transposed two-dimensional array \(c\).

2. Step-by-step execution on the instances.

   Instance 1: \(b = \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{bmatrix}\), \(m=2\), \(n=3\), so \(c\) is \(3 \times 2\)

   \(i\)	\(j\)	\(b[i][j]\)	assignment
   \(1\)	\(1\)	\(1\)	\(c[1][1] \leftarrow 1\)
   \(1\)	\(2\)	\(2\)	\(c[2][1] \leftarrow 2\)
   \(1\)	\(3\)	\(3\)	\(c[3][1] \leftarrow 3\)
   \(2\)	\(1\)	\(4\)	\(c[1][2] \leftarrow 4\)
   \(2\)	\(2\)	\(5\)	\(c[2][2] \leftarrow 5\)
   \(2\)	\(3\)	\(6\)	\(c[3][2] \leftarrow 6\)

   Return: \(c = \begin{bmatrix} 1 & 4 \\ 2 & 5 \\ 3 & 6 \end{bmatrix}\)

   Instance 2: \(b = \begin{bmatrix} 7 & 2 \\ 3 & 8 \\ 1 & 5 \end{bmatrix}\), \(m=3\), \(n=2\), so \(c\) is \(2 \times 3\)

   \(i\)	\(j\)	\(b[i][j]\)	assignment
   \(1\)	\(1\)	\(7\)	\(c[1][1] \leftarrow 7\)
   \(1\)	\(2\)	\(2\)	\(c[2][1] \leftarrow 2\)
   \(2\)	\(1\)	\(3\)	\(c[1][2] \leftarrow 3\)
   \(2\)	\(2\)	\(8\)	\(c[2][2] \leftarrow 8\)
   \(3\)	\(1\)	\(1\)	\(c[1][3] \leftarrow 1\)
   \(3\)	\(2\)	\(5\)	\(c[2][3] \leftarrow 5\)

   Return: \(c = \begin{bmatrix} 7 & 3 & 1 \\ 2 & 8 & 5 \end{bmatrix}\)

3. In-place transposition of a square two-dimensional array (\(m = n\)):

   Algorithm: TransposeInPlace

   Input: A square two-dimensional array \(b[1..n][1..n]\), the dimension \(n\)

   Output: The two-dimensional array \(b\), transposed in place

   1function TransposeInPlace(b, n)

   2for \(i := 1\) to \(n-1\) do

   3for \(j := i+1\) to \(n\) do

   4\(tmp := b[i][j]\)

   5\(b[i][j] \leftarrow b[j][i]\)

   6\(b[j][i] \leftarrow tmp\)

   7end

   8end

   9return \(b\)

   10end

   The inner loop starts at \(j = i+1\), so that each pair of symmetric positions is exchanged exactly once (exchanging it twice would restore the original array) and the elements \(b[i][i]\) on the diagonal are never moved. For \(i = n\) the inner loop would be empty, so the outer loop stops at \(n-1\). For example, on \(b = \begin{bmatrix} 4 & 1 \\ 9 & 6 \end{bmatrix}\) (\(n=2\)) the only iteration exchanges \(b[1][2]=1\) and \(b[2][1]=9\), giving \(b = \begin{bmatrix} 4 & 9 \\ 1 & 6 \end{bmatrix}\).

Exercise 2.6: Pseudo-code (E6)

Given a two-dimensional array \(a[1..m][1..p]\) of \(m \times p\) integer numbers and a two-dimensional array \(b[1..p][1..n]\) of \(p \times n\) integer numbers, consider the problem of computing their product, i.e., the two-dimensional array \(c[1..m][1..n]\) with:

\[ c[i][j] = \sum_{k=1}^{p} a[i][k] \cdot b[k][j] \]

Questions

1. Write the pseudo-code of an algorithm that computes the product \(c = a \cdot b\). The algorithm should:

   • take as input the two-dimensional arrays \(a[1..m][1..p]\) and \(b[1..p][1..n]\), and the dimensions \(m\), \(p\), \(n\);

   • allocate a new two-dimensional array \(c[1..m][1..n]\), initialized to zero;

   • use three nested loops (over \(i\), \(j\), \(k\)) to compute the product with the formula above;

   • return the product two-dimensional array \(c\).

2. Execute the algorithm step by step on the following instances, showing the values of \(k\) and \(c[i][j]\) at each step of the innermost loop:

   • Instance 1: \(a = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}\), \(b = \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix}\), \(m=p=n=2\);

   • Instance 2: \(a = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 2 & 3 \end{bmatrix}\), \(b = \begin{bmatrix} 4 & 5 \\ 6 & 7 \end{bmatrix}\), \(m=3\), \(p=2\), \(n=2\).

Solution

1. Pseudo-code for the product of two two-dimensional arrays:

   Algorithm: MatrixProduct

   Input: The two-dimensional arrays \(a[1..m][1..p]\) and \(b[1..p][1..n]\), the dimensions \(m\), \(p\), \(n\)

   Output: The product two-dimensional array \(c[1..m][1..n]\)

   1function MatrixProduct(a, b, m, p, n)

   2\(c := \text{new array}[1..m][1..n]\)

   3for \(i := 1\) to \(m\) do

   4for \(j := 1\) to \(n\) do

   5\(c[i][j] \leftarrow 0\)

   6end

   7end

   8for \(i := 1\) to \(m\) do

   9for \(j := 1\) to \(n\) do

   10for \(k := 1\) to \(p\) do

   11\(c[i][j] \leftarrow c[i][j] + a[i][k] \cdot b[k][j]\)

   12end

   13end

   14end

   15return \(c\)

   16end

   • We allocate \(c\) as an \(m \times n\) two-dimensional array and initialize all its elements to zero with two nested loops.

   • The outer loop iterates over the rows of \(c\), \(i = 1, 2, \dots, m\), and the middle loop over its columns, \(j = 1, 2, \dots, n\).

   • The inner loop computes the sum \(\sum_{k=1}^{p} a[i][k] \cdot b[k][j]\), adding one product at each iteration.

   • Finally, we return \(c\).

2. Step-by-step execution on the instances.

   Instance 1: \(a = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}\), \(b = \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix}\), \(m=p=n=2\)

   \(i\)	\(j\)	\(k\)	\(a[i][k]\)	\(b[k][j]\)	product	\(c[i][j]\) (after)
   \(1\)	\(1\)	\(1\)	\(1\)	\(5\)	\(1 \cdot 5 = 5\)	\(5\)
   \(1\)	\(1\)	\(2\)	\(2\)	\(7\)	\(2 \cdot 7 = 14\)	\(19\)
   \(1\)	\(2\)	\(1\)	\(1\)	\(6\)	\(1 \cdot 6 = 6\)	\(6\)
   \(1\)	\(2\)	\(2\)	\(2\)	\(8\)	\(2 \cdot 8 = 16\)	\(22\)
   \(2\)	\(1\)	\(1\)	\(3\)	\(5\)	\(3 \cdot 5 = 15\)	\(15\)
   \(2\)	\(1\)	\(2\)	\(4\)	\(7\)	\(4 \cdot 7 = 28\)	\(43\)
   \(2\)	\(2\)	\(1\)	\(3\)	\(6\)	\(3 \cdot 6 = 18\)	\(18\)
   \(2\)	\(2\)	\(2\)	\(4\)	\(8\)	\(4 \cdot 8 = 32\)	\(50\)

   Return: \(c = \begin{bmatrix} 19 & 22 \\ 43 & 50 \end{bmatrix}\)

   Instance 2: \(a = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 2 & 3 \end{bmatrix}\), \(b = \begin{bmatrix} 4 & 5 \\ 6 & 7 \end{bmatrix}\), \(m=3\), \(p=2\), \(n=2\)

   \(i\)	\(j\)	\(k\)	\(a[i][k]\)	\(b[k][j]\)	product	\(c[i][j]\) (after)
   \(1\)	\(1\)	\(1\)	\(1\)	\(4\)	\(4\)	\(4\)
   \(1\)	\(1\)	\(2\)	\(0\)	\(6\)	\(0\)	\(4\)
   \(1\)	\(2\)	\(1\)	\(1\)	\(5\)	\(5\)	\(5\)
   \(1\)	\(2\)	\(2\)	\(0\)	\(7\)	\(0\)	\(5\)
   \(2\)	\(1\)	\(1\)	\(0\)	\(4\)	\(0\)	\(0\)
   \(2\)	\(1\)	\(2\)	\(1\)	\(6\)	\(6\)	\(6\)
   \(2\)	\(2\)	\(1\)	\(0\)	\(5\)	\(0\)	\(0\)
   \(2\)	\(2\)	\(2\)	\(1\)	\(7\)	\(7\)	\(7\)
   \(3\)	\(1\)	\(1\)	\(2\)	\(4\)	\(8\)	\(8\)
   \(3\)	\(1\)	\(2\)	\(3\)	\(6\)	\(18\)	\(26\)
   \(3\)	\(2\)	\(1\)	\(2\)	\(5\)	\(10\)	\(10\)
   \(3\)	\(2\)	\(2\)	\(3\)	\(7\)	\(21\)	\(31\)

   Return: \(c = \begin{bmatrix} 4 & 5 \\ 6 & 7 \\ 26 & 31 \end{bmatrix}\)

   The first two rows of \(a\) form the identity, so the first two rows of \(c\) are equal to the two rows of \(b\).