Section 7.1 One-Dimensional Arrays
As a reminder, an array is a structure for storing several data values, as long as those values all share the same data type. It is common to refer to one-dimensional arrays as vectors, though the term "vector" has a special meaning in physics and engineering.
Subsection 7.1.1 Addition and Scalar Multiplication
A one-dimensional array looks a lot like a list of values. For example,
myFirstArray = [1, 5, 9, -11] is a one-dimensional array with four elements while mySecondArray = [1.5, -2.8, 3] is a one-dimensional array with three elements. In the two examples, myFirstArray is an array of integer values, while mySecondArray is an array of floats. Perhaps you remember from our first chapter that there are different memory requirements for integers versus floats, and that can sometimes make a big difference in our programs.Addition and subtraction between arrays is done elementwise. For example, we can add the two arrays
[1, 6, 3] and [5, 11, 2] as follows.
\begin{align*}
\left[\begin{array}{c} 1\\ 6\\ 3\end{array}\right] + \left[\begin{array}{c} 5\\ 11\\ 2\end{array}\right] \amp = \left[\begin{array}{c} \left(1 + 5\right)\\ \left(6 + 11\right)\\ \left(3 + 2\right)\end{array}\right]\\
\amp = \left[\begin{array}{c} 6\\ 17\\ 5\end{array}\right]
\end{align*}
Subtraction between those two arrays is done similarly.
\begin{align*}
\left[\begin{array}{c} 1\\ 6\\ 3\end{array}\right] - \left[\begin{array}{c} 5\\ 11\\ 2\end{array}\right] \amp = \left[\begin{array}{c} \left(1 - 5\right)\\ \left(6 - 11\right)\\ \left(3 - 2\right)\end{array}\right]\\
\amp = \left[\begin{array}{c} -4\\ -5\\ 1\end{array}\right]
\end{align*}
A scalar is a quantity which has only a magnitude. For example, the value \(8\) is considered a scalar, while \([8]\) may be considered a one-dimensional array containing a single element. We can multiply arrays by a scalar value. To do this, each element of the array is multiplied by the scalar. For example, let’s multiply the array
[2, 12, -64, 32, 18] by the scalar \(\frac{1}{2}\text{.}\)
\begin{align*}
\frac{1}{2}\cdot \left[\begin{array}{c} 2\\ 12\\ -64\\ 32\\ 18\end{array}\right] \amp = \left[\begin{array}{c} \left(\frac{1}{2}\cdot 2\right)\\ \left(\frac{1}{2}\cdot 12\right)\\ \left(\frac{1}{2}\cdot \left(-64\right)\right)\\ \left(\frac{1}{2}\cdot 32\right)\\ \left(\frac{1}{2}\cdot 18\right)\end{array}\right]\\
\amp = \left[\begin{array}{c} 1\\ 6\\ -32\\ 16\\ 9\end{array}\right]
\end{align*}
Use what you’ve learned to verify your grasp of addition, subtraction, and scalar multiplication for one-dimensional arrays.
Checkpoint 7.1.2. Scalar Multiplication.
At the end of our chapter on counting, we encountered big-O notation and its use in describing the run-time complexity of a routine, algorithm, or program. Answer the following questions about the run-time complexity of array addition and scalar multiplication.
Checkpoint 7.1.3. Array Addition Complexity.
Checkpoint 7.1.4. Scalar Multiplication Complexity.
Subsection 7.1.2 Inner-products
In addition to adding/subtracting arrays or multiplying arrays by scalars, there’s lots of interesting and meaningful operations that can be done with arrays. We’ll take a look at one of them, called the inner-product in this section. Our section will end by mentioning the outer-product, but we’ll need to wait until we see two-dimensional arrays before we can compute that.
Given two arrays of equal length, we can calculate the inner-product between them. We’ll introduce the inner-product algorithmically using the pseudocode below.
def inner_product(myArray1, myArray2):
n = length(myArray1)
if length(myArray2) not equal n:
print("Arrays must be the same length")
return NULL
inner_prod = 0
for i in [0, 1, ..., n - 1]:
inner_prod = inner_prod + (myArray1[i] * myArray2[i])
return inner_prod
Answer the following regarding the run-time complexity of the following implementation to compute the inner product between two arrays.
Checkpoint 7.1.5. Inner Product Complexity.
Now try the following examples for computing the inner product between two arrays on your own.
Checkpoint 7.1.6. Compute Inner Product 1.
Checkpoint 7.1.7. Compute Inner Product 1.
Checkpoint 7.1.8. Compute Inner Product 1.
Another type of array product is the outer-product. Given two one-dimensional arrays, we can define the outer product between them. The outer-product, however, results in a two-dimensional array. If
array1 and array2 are arrays of length \(m\) and \(n\) respectively, then the outer product between array1 and array2 is an \(m\times n\) array. Note that this also means that inner_product(array1, array2) is generally not the same as inner_product(array2, array1). We’ll see how to compute the inner product in our next section.
