Contents

1 About this module

• Prerequisites: 0012, 0013, 0016
• Objectives: This module introduces the concept of arrays, as well as some simple algorithms that work on arrays.

2 Why?

Let us first explore why arrays are useful. This can be illustrated using an example.

The code that we need to find the maximum $m$ of two variables $a$ and $b$ is simple. It is represented in algorithm 1.

If we add one more variable, $c$, then the algorithm gets more complicated, as described in algorithm 2.

What if we have given 20 values? 200 values? 2000 values?

As you can see, this approach does not “scale”. In other words, the algorithm becomes more and more complicated as the number of values increases. However, if we use an array of numbers, then the algorithm is much simple, as described in algorithm 3.

Of course, the complexity of algorithm 3 doesn’t appear to be much simpler than algorithm 2. However, algorithm 3 works for 3 values, 30, values, 3000 values, and etc. The same algorithm works for any number of values!

3 What is an array?

An array can be seen as one variable. However, it is actually the composite of many elements. An array has several attributes:

• all elements in an array have the same type
• each element has an index (number)
• the index of the first element is 0
• indices of elements must be contiguous (0, 1, 2, ...)
• if $a$ is an array, $\left|a\right|$ indicates the number of elements in $a$
• the last element in an array $a$ has an index of $\left|a\right|-1$ because we count from 0.
• an element with index $i$ in array $a$ is represented as $a\left[i\right]$

Note that each element of an array can behave like a variable on its own. You can use it on either side of an assignment, you can perform mathematical operations, you can compare and etc.

4 Initialization algorithm

Let us consider an algorithm that initializes an array so that all elements become 0. This algorithm is illustrated in algorithm 4.

Let us analyze each line of code here.

• line 1: this is the initialization of variable $i$. Variable $i$ is really just an integer variable. However, the role that it serves in this algorithm is the changing index. It tells us which element in the array should be initialized for each iteration fo the loop.
• line 2 marks the beginning of a prechecking loop. The stay-in condition is $i<\left|a\right|$. This means that as soon as $i=\left|a\right|$, we exit the loop. This makes sense because the last element is $a\left[\left|a\right|-1\right]$, so when $i=\left|a\right|$, we are done.
• line 3 changes one element in array $a$ to 0. The most important part of this assignment is the use of the expression $i$ to specify the index of the element. Because $i$ changes (increments for each iteration), we can access a different element for each iteration of the loop.
• line 4 increments $i$. This move the index forward so that we will be ready for the “next” element in the next iteration. If we don’t have this line, then $i$ stays 0, and the loop won’t exit!
• line 5 marks the end of the prechecking loop.

When we trace an algorithm involving an array, each element in the array has its own column. This is hardly surprising because each element in an array is an independent variable! This fact does make the trace of an algorithm involving an array rather tedious. A table/spreadsheet should be used because the gridlines help significantly.

As an exercise, trace algorithm 4, assuming array $a$ has 3 elements.

5 Searching for a value in an array

5.1 Unsorted array

Given an unsorted array $a$ and a value $v$ to find, how do we know whether the array has an element that matches the value $v$ or not?

Algorithm 5 is the not-so-formal version.

Recall our technique of using an integer variable to control which element we want to access. We an reapply that technique here. In fact, we’ll use the same variable $i$ for this purpose.

To start with the first element means $i$ should be initialized to 0. Hence, we have $i\leftarrow 0$ as our first statement.

Next, let us consider the phrase “there are more elements.” Since we start with the first element, then as long as the index remains within the range of 0 to $\left|a\right|-1$, there is at least one more element to consider. Consequently, “there are more elements” translates to the condition $i<\left|a\right|$. Note that we cannot use $i\le \left|a\right|$ because when $i=\left|a\right|$, $a\left[i\right]$ is not defined anymore.

The next phrase to consider is “the current one does not match $v$”. The “current one” is an element controled by the indexing variable $i$. In other words, the “current one” is simply $a\left[i\right]$. To say that $a\left[i\right]$ does not match $v$ is to say $a\left[i\right]\ne v$.

As a result, the condition of the prechecking loop can be more formally written as $\left(i<\left|a\right|\right)\wedge \left(a\left[i\right]\ne v\right)$.

The only thing to do in the loop is to move on the next element. Because the current element is controled by the indexing variable $i$, to move on to the next element is to bump $i$ up by 1. This means the action “move on to the next element” is really just $i\leftarrow i+1$.

In the conditional (if-then-else) statement, how do we know we have exhausted all the elements in the array? If we have searched through the array and no element matches, $i=\left|a\right|$, and that is the reason to exit the prechecking loop. As a result, “we have exhausted all elements” should be replaced by $i=\left|a\right|$.

Algorithm 6 is the result of replacing all the not-so-formal description with formal pseudocode.

Again, it really helps to trace an algorithm. In this case, try to consider $a$ as an array of 4 elements. Let’s assume $a\left[0\right]=2$, $a\left[1\right]=0$, $a\left[2\right]=10$ and $a\left[3\right]=1$.

Perform two traces. First, assume $v=7$, trace. Then, assume $v=0$, trace.