Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Chapter 2
Arrays, Iteration, Invariants
Data is stored in computers as patterns of bits, but most programming languages
deal with higher level objects such as characters, integers, and floating point
numbers
...

2
...
Array items are typically stored in a sequence of computer memory locations,
but to discuss them, we need a convenient way to write them down on paper
...
Thus,
[1, 4, 17, 3, 90, 79, 4, 6, 81]
is an example of an array of integers
...
In everyday life, we
usually start counting from 1
...
Thus, for our array a, its
positions are 0, 1, 2,
...
The element in the 8th position is 81, and we use the
notation a[8] to denote this element
...
This position i is
called an index (and the plural is indices)
...
It is worth noting at this point that the symbol = is quite
overloaded
...
In most modern programming
languages, = denotes assignment, while equality is expressed by ==
...

The individual items in an array a[i] are accessed using their index i, and can be
moved sequentially by incrementing or decrementing that index
...

2
...
In pseudocode, this would
typically take the general form
For i = 1,
...
For example, we could compute
the sum of all 20 items in an array a using
for( i = 0, sum = 0 ; i < 20 ; i++ )
{
sum += a[i];
}
We say that there is iteration over the index i
...
One way to write this out explicitly is
INITIALIZATION
if ( not CONDITION ) go to LOOP FINISHED
LOOP START
REPEATED PROCESS
UPDATE
if ( CONDITION ) go to LOOP START
LOOP FINISHED

In these notes, we will regularly make use of this basic loop structure when
operating on data stored in arrays, but it is important to remember that different
programming languages use different syntax, and there are numerous variations
that check the condition to terminate the repetition at different points
...
3 Invariants
An invariant, as the name suggests, is a condition that does not change during
execution of a given program or algorithm
...

Invariants are important for data structures and algorithms because they enable
correctness proofs and verification
...
Consider the
standard simple example of a procedure that finds the minimum of n numbers
stored in an array a:
minimum (int n, float a[n])
{
float min = a[0];
// min equals the minimum item in a[0],
...
,a[i-1] if (a[i] < min) min = a[i];
}
// min equals the minimum item in a[0],
...
, a[i − 1]” is true – it starts off true, and the
repeated process and update clearly maintain its truth
...
, a[n −
1]” and hence we can be sure that min can be returned as the required minimum
value
...

As we noted earlier, formal proofs of correctness are beyond the scope of these
notes, but identifying suitable loop invariants and their implications for algorithm
correctness as we go along will certainly be a useful exercise
...




---