## 2   Simple algorithm design

An algorithm is a set of rules that can be obeyed to solve a problem, and computer scientists tend to talk of executing an algorithm or a program to effect that solution. In elementary computing, these rules have some important restrictions placed on them:

• the set of rules must be finite;
• the rules must be followed in some definite sequence, until a satisfactory result is achieved;
• the rules must cover any awkward situations that arise;
• only one rule may be obeyed (that is, only one operation may be performed) at a time.

Achieving self-consistency in this respect is sometimes fairly tricky!

In fairness it should be pointed out that algorithms - as with so much else in science - are designed to operate within a model of reality which is often restricted and simplified. In other words, an algorithm designer must build a model from which extraneous or irrelevant detail has been discarded. By way of example, an algorithm for solving the problem of choosing which university to attend cannot reasonably be expected also to handle the unrelated problem of booking a bus trip to reach the university. Similarly, while an algorithm for ensuring that all employees are correctly paid before the end of every month will probably have to come to terms with such properties of employees as their salary, tax brackets and bank account numbers, it is far less likely to have to deal with properties of employees such as their hair colour, or whether they are left- or right-handed.

This chapter aims to expose you to a semi-formal way of developing algorithms in a way that leads slowly but naturally towards computer coding in a language like Java. If some of our initial examples look contrived or irrelevant, it is because we are trying to use simple models to start off our studies. Knowing how much detail has to be built into either the description of data, or the rules for processing it, is something that comes only with experience.

### 2.1 Sequential algorithms

Although many computer algorithms are concerned with manipulating numerical and/or alphabetic data, it may help in coming to terms with the sequential aspects of design to consider a few problems which do not appear to be of that sort, but which fall within the realms of everyday life.

As a first example, let us try to answer the question:

'How does one get to see the film "Quantum of Solace"?'

Possible answers to this are fairly straightforward, and could be expressed in many ways. Specifically, aiming at an algorithmic solution, we write down a set of rules, which at a first attempt might be expressed something like

Algorithm 2.1.1

Go to the cinema
Watch the film
Go home again

This algorithm consists of four basic components, each of which demands that some activity be completed before the next is begun. In computer terms each of these components will ultimately be coded into a statement, or a group of statements (often called a block, procedure, subroutine, function or method), which performs a particular task in a definite relation to the rest of the algorithm.

What we have described is surely very simple. That is as it should be. The technique of stepwise refinement, a favourite with computer scientists, demands that one always starts very simply, and leaves matters of detail until later. As we hinted earlier, exactly what is meant by "simply" may be harder to decide. For example, a tribesman who has spent all his life in a dense jungle would have difficulty understanding nearly all of the concepts introduced into the above solution. Closer to our own culture, a two year old child might have little trouble with knowing how to "watch the film" but would have little idea of exactly how to "buy a ticket". A component of an algorithm is simple only when it has been reduced it to a state where it can be completely understood by the reader, whether this be a human or a computer. This implies that "simple" steps must be slowly refined into even simpler (yet, paradoxically, more detailed) components.

As was stressed earlier, a feature of any real algorithm is that its rules should be able to handle awkward situations. This often means that we have to step back from the ideal situation that first comes to mind, so as to anticipate what might go wrong. Taken to extremes this might seem to lead to a never-ending and gloomy scenario, but in practice it is not as bad as all that. By way of illustration, in our present example there are two fairly obvious situations which could prove awkward. Firstly, "Quantum of Solace" might not be showing and, secondly, the cinema might be overbooked. A slightly more complete and more formal algorithm, which takes these possibilities into account, is:

Algorithm 2.1.2

begin  // Algorithm for going to see the film "Quantum of Solace"
if "Quantum of Solace" is not showing
then
find something else to do
else
go to the cinema
if there is a queue
then
join it at the back
repeat
shuffle forward
until everyone in front of you has been served
if seats are still available
then
find the corresponding seat and sit down in it
repeat
gaze at the screen and listen to the soundtrack
until the film is over
else
mutter quietly
leave the cinema
go home again
end.

You should note several points about the algorithm expressed in this way. Firstly, we have used certain keywords to define the fundamental control structures and decision making processes in the algorithm. These include the important ones of selection (expressed by if ... then ... else) and repetition or iteration (expressed by repeat ... until), used in nearly all algorithms, especially data processing ones. Secondly, the physical layout of the algorithm is intended to make it easy for the eye to distinguish the alternative paths which might need to be taken as the execution of the algorithm progresses. The informal approach adopted here has used indentation to serve the role of punctuation. It is often as important to read programs as it is to write them. A neat layout contributes greatly to the ease with which this can be done.

The algorithm still has plenty of scope for further refinement. How, for example, does one find one's seat? If we can assume that the seat numbers are printed on the tickets, a solution to this subproblem is given by

Algorithm 2.1.3

begin // Algorithm for finding the correct seat to match a ticket
repeat
move down the aisle to the next row of seats
until the row number agrees with the one printed on the ticket
repeat
move across this row to the next seat
until the seat number agrees with the one printed on the ticket
end.

In this algorithm we have two examples of iterative structures. We have also assumed that a seat matching the details on the ticket can be found, but this is true of most cinemas.

Although the use of indentation helps to show the ways in which some steps are combined to form other larger steps, this is rarely adequate when it comes to actual computer programs. Computer languages usually pay little heed to physical layout, but make use of some other kind of punctuation and bracketing to make the structures perfectly clear. For example, while we shall continue to use indentation to assist the human reader,

• semicolons will appear at the end of all simple "statements";
• curly brackets (or "braces", as they are called by type-setters) will be used to group statements;
• round brackets (technically called "parentheses") will be used to demarcate the tests used in making decisions, allowing us to omit the keyword then.

If we adopt these conventions, the above algorithms take the form shown below:

Algorithm 2.1.4

{ // Formalized algorithm for going to see the film "Quantum of Solace"
if ( "Quantum of Solace" is not showing ) {
find something else to do;  // studying these notes, perhaps
} else {
go to the cinema;
if ( there is a queue ) {
join it at the back;
repeat {
shuffle forward;
} until ( everyone in front of you has been served );
}
if ( seats are still available ) {
find the corresponding seat and sit down in it;
repeat {
gaze at the screen and listen to the soundtrack;
} until ( the film is over );
else {
mutter quietly;
}
leave the cinema;
go home again;
}
}

Algorithm 2.1.5

{ // Formalized algorithm for finding the correct seat to match a ticket
repeat {
move down the aisle to the next row of seats;
} until ( the row number agrees with the one printed on the ticket );
repeat {
move across this row to the next seat;
} until ( the seat number agrees with the one printed on the ticket );
}

Any formal notation rapidly becomes cryptic. To alleviate this, notice the so-called commentary which has been introduced with a pair of slashes // and which is deemed to extend from the // to the end of the line. Another notation for commentary uses a disdinctive form of bracketing:

/*  This is a comment */

Commentary is extremely useful to explain what is being done when this is not clear from the algorithm itself.

### Exercises

Before going on to examine algorithms which have more of the appearance of data processing, try to develop algorithms in the spirit of this section to

1. Go to the cinema.
2. Buy a cinema ticket.
3. Lay the table for breakfast.
4. Boil an egg.
5. Make a cup of tea.
6. Wash up the breakfast dishes.
7. Decide on a partner for a social function.
8. Look up the partner's telephone number.
9. Make a phone call to the partner.
10. Change a flat tyre on a motor car.
11. Repair a puncture on a bicycle.
12. Travel through a busy intersection controlled by traffic lights.
13. Pay a traffic fine.
14. Find out when Elvis Presley was born (assuming you can make use of Google or Wikipedia).
15. Find out when Elvis Presley was born (assuming you are forbidden from using Google or Wikipedia).
16. Develop an algorithm to solve problems.
17. Find your way out of a rectangular maze.

### 2.2 Properties of data

We have stressed that most programs are a combination of descriptions of data, and the rules for manipulating that data. The role of the "data" in the examples considered in the last section was downplayed. Indeed, it might not have been obvious that there was any data at all. But such is not the case. The algorithm is very much concerned with manipulating real world objects, and in particular tickets, queues and seats, which assume the role of being data items. The popular modern paradigm of object-oriented programming (OOP) lays great stress on the programmer recognizing that objects like this exist, and must be modelled as part of the programming process.

What do we mean by "modelled"?

Well, objects like these have various properties, some at least of which will be important for the application being developed. In the case of a ticket, for example, there is a monetary price, and it will contain details about a row and seat number. It may also be printed in a particular colour, or have a time stamped on it, but these properties do not seem to be mentioned in the algorithm we have described, and are probably of lesser importance (so that they probably do not have to come into the model).

Objects also have operations associated with them, effectively limiting what can be done with them, while at the same time describing how the allowed operations must be carried out (in the form of further small algorithms). In the case of a ticket, for example, operations relating to reserving, purchasing, reading and cancelling come to mind.

In the case of a queue, the properties we might need to record would include its length, while the operations would describe how a person joins it at one end and leaves it at the other end.

The operations that can be applied to objects are likely to alter their properties - for example, when you join a queue it becomes longer. Manipulating one object is likely to alter the properties of other objects in the system. As another example, a box-office at a cinema will have a map of the available tickets, and a till. When a customer purchases a ticket, the map of the available tickets will need to be updated, as will the money, both in the customer's wallet and in the cinema's till.

### Exercises

The world around us is full of interesting objects. Without delving too deeply into finer details, see if you can identify some properties and operations that come to mind if you wish to describe and work with:

1. Mobile phones
2. Digital cameras
3. DVD players
4. Wallets
5. Identity books
6. Times of events
7. Members of a pop group
8. Bank accounts
9. University lectures
10. University lecturers

### 2.3 A simple data processing algorithm

It does not take much imagination to realize that keeping track of all of the considerations introduced into the discussion thus far rapidly leads to situations that become quite complicated. Controversy rages in educational circles as to whether beginners should be taught programming by focussing firstly on the objects (usually known as object-oriented programming) or on the algorithmic constructs (usually known as procedural programming). However, you cannot manipulate objects without some knowledge of algorithmic ideas, or experience and confidence in applying them. Furthermore, the formal notations for describing objects turn out to be quite long- winded and mysterious in themselves. It thus seems to make good sense to concentrate first on acquiring algorithmic skills by solving some problems where the data has limited properties only - simple numbers and words.

While the sorts of problems that can be handled in this way may not always seem particularly exciting, they can, nevertheless, become quite intriguing and quite challenging. We urge you to engage with them as a precursor to more exciting applications later on.

With this in mind, let us consider a simple data processing problem, proceeding as before by starting simply, and then refining the solution until we are content with it, both as a whole, and with respect to its constituent parts. The question we shall answer is:

"How do we find the arithmetic average of a long list of positive numbers?"

The essence of a solution is surely

Algorithm 2.3.1

First add up all the numbers to give a total;
Then count to see how many numbers there are;
Finally, divide the total by the number of numbers to give the average;

On reflection, this might not be the best way to do it. We could add up all the numbers first and then go back to count to see how many there are, as is implied by the sequential rules above. But in practice, at almost the same time as we add up the numbers, we could be keeping a count of how many there are. This might suggest:

Algorithm 2.3.2

Add up all the numbers, also counting to see how many numbers there are;
Divide the total by the number of numbers to give the average;

There is a point of some subtlety here. We have stressed that a feature of our algorithms is that they may do only one thing at a time, and here we already seem to want to do two things at one time!

The way out of this dilemma is simple. We can achieve the effect we require by repeating a simple sequence of two operations many times over:

Algorithm 2.3.3

repeat {
Add the next number to a running total;
Increase the number of numbers;
} until ( all numbers have been processed );
Divide the total by the number of numbers to give the average;

Before we take this refinement further we need to introduce another idea, taken this time from simple algebra. Concepts like "total and "number" clearly fall into the realm of "data", and need to be described in an abstract way. But the rules for manipulating such data are essentially independent of the exact values of the data. The rules would apply to the list 1 2 3 4 (of four numbers) just as they would apply to the list 100 200 350 580 720 912 (of six numbers). The numbers would be different, the answers would be different, but we could use the same algorithm in each case.

To build on this idea we shall denote an (as yet unknown) "value", which is to be processed within the algorithm, by a symbolic name (say Value), and do the same for the "total" and the "number of numbers" (calling these Total and Numbers respectively). These variables are given alphabetic names, even though the quantities they represent may (as in this case) ultimately have arithmetic values.

So now our model supposes that we have a long list of actual numbers - often called a data file in computer jargon - which can be "read" number by number, using a repetitive algorithm. The next step in refining the algorithm might be to find a way to decide when all the numbers in the data file have been handled. This calls for a bit of a trick. One way of doing this is to ask that the user attach a non-positive number (say zero) to the end of the data, to act as a so-called end-of-file sentinel. (There might be other, better, ways of doing this; for the moment forgive the fact that the "solution" is making strange demands of the user!) A refined algorithm then reads:

Algorithm 2.3.4

{ // Algorithm for determining the average of an indefinite list of
// positive numbers, terminated with a non-positive number
set Total to zero;
set Numbers to zero;
repeat {
if ( Value is positive ) {
add Value to Total;
add 1 to Numbers;
}
} until ( we have read a non-positive Value );
set Average to Total / Numbers;
write value of Average;
}

As already mentioned, an important part of algorithm design is concerned with checking correctness. Algorithm 2.3.4 looks deceptively correct, but it would fail if (accidentally or deliberately) the very first Value were to be supplied as a non-positive number, for then it would foolishly try to compute the Average by dividing zero by zero. (You are urged to work through the algorithm carefully to see why this is the case.)

The algorithm may be improved, and at the same time a little more use made of our symbolic notation, as follows:

Algorithm 2.3.5

{ // Algorithm for determining the average of an indefinite list of
// positive numbers, terminated with a non-positive number
Total = 0;
Numbers = 0;
repeat {
Value = read("Supply a positive number, or one <= 0 to terminate");
if ( Value > 0 ) {
Total = Total + Value;
Numbers = Numbers + 1;
}
} until ( Value <= 0 );
if ( Numbers == 0) {
write("Error - no data processed");
} else {
Average = Total / Numbers;
write("Average is ", Average);
}
}

Note that the variable names - which start with a capital letter here so as to distinguish them from keywords -have names chosen to bear some relation to the quantities which the variables represent. This is a sensible idea, not usually used in algebra, where it is normal practice to give single letter names to unknowns and to variables.

Three operations fundamental to data processing often cause some conceptual problems when beginners first encounter them, these being the input, output and assignment of data values - in a sense the "Three R's" of programming.

The symbol = means "calculate the value of the expression specified on the right of the = and take the value so computed as a new value to be attributed or assigned to the variable whose name appears on the left of the = sign, destroying any previous value which that variable may have had." An operation like

Numbers = 4;

thus assigns to the variable named Numbers a value of 4. A subsequent operation of the form

Numbers = Numbers + 1;

is quite legitimate - in this case it would have the effect of assigning 4+1 = 5 as the value to be associated with Numbers from then on (until changed again). One sometimes speaks of storing a value "in" a variable, and it may help to think of variables as containers, identifiable by names like Numbers or Total painted on their lids, and with pieces of paper inside them on which are recorded data values. On the left of the = operator a name like Numbers refers to the name of one of the containers; while on the right it actually refers to the value stored in the container with that name. The name of the variable is not changed by making an assignment; it is the associated value that changes. The value, as in this example, is often a single number; later it will be seen that a variable can be more complex, referring, for example, to the sort of complex object hinted at in the last section.

A few other notational points should be stressed:

• A statement like the above does not mean "solve an equation", as it might have done in a more mathematical context. The use of = to denote "store" or "replace" or "assign" rather than "solve" is, perhaps, unfortunate, but one just has to live with one of the decisions of some early language designers.

• A comparison between two quantities to test whether they are equal is denoted by using the symbol == and a comparison for testing whether they are unequal is denoted by the symbol !=. Once again, the use of these particular symbols has come down through a long tradition.

The read operation is also expressed as a form of assignment. Here the value to be assigned is marked by the keyword read, followed by a parenthesized string that can define a prompt to the user as to what is expected when the new data item is to be absorbed by the program from an external source. This might be a file stored on disk, or its value might simply be typed on a the keyboard, or it might be supplied by filling in a pop-up window or selecting a button on a screen. Regardless of the actual mechanism used, the value so read is then assigned as the new value of the variable named on the left of the = assignment operator.

We shall assume that once a value has been read in this way it will not be "read" again. Unlike the human ability to read and re-read a piece of text, our computer model for the moment requires that we read our data values only once, in sequence, from start to finish. (Later we shall see that other models are possible as well.)

Conversely, the write operation (formally written as the keyword write followed by a parenthesized list) allows for the transmission of results from the program to an external medium (such as a printer, or screen, or some other file). Without altering their values in any way, the effect is to copy the current values of the variables named in the list to this medium. These values may be interspersed with so-called character strings, which appear in the algorithm between double quotes, so as to distinguish them from variable names and keywords.

Algorithm 2.3.5 is refined enough for the present, and will work correctly for any data which consists of a list of numbers. It would not work if it were given data which consisted of "words" (like Thabo or Anne) instead of "numbers" (like 123 or 456), although this complication may be ignored for the moment. The point has been reached at which the basic control structures of algorithms must be examined in a little more detail, so that you can be confident of writing semi-formal programs with some degree of consistency in approach and notation.

### 2.4 Basic building blocks of algorithms

In the design of algorithms use is commonly made of some important structures to specify sequential, selective and repetitive features. It is useful to examine the properties of each of these structures in turn. Taken out of context each is very simple; it is when they are combined into rather more complicated structures that they really start to become useful and, perhaps, slightly harder to understand.

2.4.1 Simple sequence

Perhaps the most fundamental structure is that of straightforward sequencing

Sub-sequence 1 ;
Sub-sequence 2 ;
Sub-sequence 3 ;

Here the action is performed in one sub-sequence after another. In practice, after refinement of the algorithm, a sub-sequence might become anything from a single line of code (often called a statement) to several hundred lines. No particular distinction will be drawn in what follows between a long sequence and a sub-sequence, and the generic term sequence will be used to mean either.

2.4.2 Simple selection - the "if ... then ... else" construct

The "flow" of an algorithm rarely gets very far before it has to make decisions of some sort. The simplest of these require a choice to be made between two clear alternatives:

if some condition is met then sequence 1 else sequence 2 ;

Here we continue to execute either sequence 1 or sequence 2 (but not both), depending on the outcome of some logical test or condition. Sometimes one of the alternatives is null, or empty, that is to say, must "do nothing". This can be expressed

if some condition is met then sequence 1 else do nothing ;

or, more usually, simply

if some condition is met then sequence 1 ;

Note that the "sequences" here may themselves be complicated structures, possibly incorporating further if ... then ... else constructs.

In terms of our more formalized notation the "some condition" is parenthesized, the word then is omitted, and the "sequences" are enclosed in curly braces, as we have already seen.

2.4.3 Repetition - the "repeat ... until" and "do ... while" constructs

Many algorithms will need to repeat a sequence of operations many times in succession. There are four constructs usually employed to describe such repetition. Perhaps the most obvious, though not, as it happens, the most frequently used, is the one we have been using, the construct known to many programmers as the repeat ... until loop:

repeat sequence until some condition is met ;

Here the sequence or loop body is executed one or more times, until some condition becomes true. Note that this "condition" is checked only after the "sequence" has been fully completed. For this reason, this form of loop is often called a post-test loop. We speak of each completion of the loop body as a cycle or an iteration.

Other programmers - in particular those who use languages like Java and C++ - express the post-test loop slightly differently:

do sequence while some condition is met ;

Here the loop body is executed one or more times, as long as the condition remains true. As before, the condition is checked only after each cycle or iteration has been fully completed.

To illustrate a do-while form of a loop, consider how we might add the numbers 1 through 10. As before, we enclose the "sequence" in braces, and parenthesize the "condition":

Algorithm 2.4.1

{ // Add the numbers 1 through 10 with a do-while loop
Sum = 0;
CurrentNumber = 1;
do {
Sum = Sum + CurrentNumber;
CurrentNumber = CurrentNumber + 1;
} while ( CurrentNumber <= 10 );
write("The total is " , Sum);
}

Here the sequence to be repeated consists of two simple assignments. Note that it is critically important that we execute these in the order shown and not in the order

CurrentNumber = CurrentNumber + 1;
Sum = Sum + CurrentNumber;

because of the way chosen to express the condition for terminating the loop. Alternatively, and perhaps more sensibly, we could have written

Algorithm 2.4.2

{ // Add the numbers 1 through 10 with a do-while loop
Sum = 0;
CurrentNumber = 0;
do {
CurrentNumber = CurrentNumber + 1;
Sum = Sum + CurrentNumber;
} while ( CurrentNumber != 10 );
write("The total is " , Sum);
}

This example is somewhat trivial, but it serves to illustrate two important points. Firstly, when constructing loops, particular attention must be given to deciding exactly when the loop is to terminate - it is easy to make the sort of mistake that results in the loop being "out by one", that is, where the loop body is executed once too often or once too seldom. Secondly, the operations in a given cycle or iteration of the loop must afford the opportunity of altering some quantity which is later tested at the end of the cycle as part of the condition for termination - if this were not so, the loop would never come to an end.

2.4.4 Repetition - the "while ... do" construct

Repetition in algorithms may also be expressed in terms of the so-called while ... do construct or while loop. This is sometimes written informally as

while some condition is met do sequence ;

Here the whole of the sequence that forms the loop body is repeated only so long as some condition remains true. Since the condition is now tested each time before starting a new cycle, and not after completing one, the possibility exists that the sequence is never executed at all. For this reason, this form of loop is often called a pre-test loop, and it is this property, strangely, which often makes a while - do loop preferable to a do - while or repeat - until loop (where the loop body must always be executed at least once). Of course, in most cases the sequence is executed several times, and eventually brings about a change in some quantity which is tested at the start of each possible iteration as part of the condition for termination.

To illustrate the while-do loop we shall look at the example of adding the numbers 1 through 10 in a slightly different light. As before, in our more formalized notation we shall omit the word do, parenthesize the condition and enclose the loop body sequence in braces:

Algorithm 2.4.3

{ // Add the numbers 1 through 10 with a while loop
Sum = 0;
CurrentNumber = 0;
while ( CurrentNumber != 10 ) {
CurrentNumber = CurrentNumber + 1;
Sum = Sum + CurrentNumber;
}
write("The total is " , Sum);
}

There is often only a slight difference between a program coded to use a while - do loop and a similar one using a repeat - until or do - while loop, as comparison of Algorithms 2.4.2 and 2.4.3 will reveal. However, it is frequently the case that one form of loop makes for a far clearer expression of an algorithm than the other, and consequently, and more importantly, makes for less error prone development. To illustrate this, reconsider the algorithm for determining the average of a list of positive numbers. Algorithm 2.3.5 used the repeat - until loop construct. An alternative formulation using a while - do loop is

Algorithm 2.4.4

{ // Determine the average of an indefinite list of positive numbers,
// terminated with a non-positive number after the last valid number
Total = 0;
Numbers = 0;
Value = read("Supply first number or one <= 0 to terminate");
while ( Value > 0 ) {
Total = Total + Value;
Numbers = Numbers + 1;
Value = read("supply next number, or one <= 0 to terminate");
}
if ( Numbers == 0 ) {
write("Error - no valid data processed");
} else {
Average = Total / Numbers;
write("Average is " , Average);
}
}

Even though the algorithm has been expressed using two read statements, the loop body is simpler than in Algorithm 2.3.4. Since there is a (remote) chance that the list will be empty, the possibility must be considered that the loop body need not be executed at all. The while loop is ideal for the purpose.

It may be of interest to "unfold" the loops of this algorithm, for the special case where three data numbers only are processed, to show how the two loop constructs actually lead to the same sequence of operations:

Total = 0;
Numbers = 0;

.-   Value = read(...);
|    Total = Total + Value;        -.
`-   Numbers = Numbers + 1;         |
.-   Value = read(...);            -'
repeat-until     |    Total = Total + Value;        -.   while-do form
or            `-   Numbers = Numbers + 1;         |
do-while form    .-   Value = read(...);            -'
|    Total = Total + Value;        -.
`-   Numbers = Numbers + 1;         |
Value = read(...); /* zero */ -'

Average = Total / Numbers;

In passing, is unfortunate that the designers of the C family of languages chose to use the single keyword while in two different ways. It is easy to confuse them when reading somebody else's code.

2.4.5 Fixed repetition - the "for" loop construct

Some of the examples discussed previously have demonstrated something typical of many situations - a repetitive loop controlled by a variable (CurrentNumber) whose value steps in equal increments from a known starting or initial value to a known final or terminal value. Because this is so common, a special loop construct is often introduced to express it, usually known as the for loop. This is sometimes expressed informally using a notation like

for Control from First by Step to Last do sequence ;

and may be illustrated with the same summation example:

Algorithm 2.4.5

{ // Add the numbers 1 through 10 with a for loop
Sum = 0;
for CurrentNumber from 1 by 1 to 10 do {
Sum = Sum + CurrentNumber;
}
write("The total is " , Sum);
}

Here it would be assumed that the for loop automatically does the incrementing (or decrementing if it goes by negative steps) of the so-called Control variable (CurrentNumber).

While the notation above has been very successfully adopted in several computer languages, others (including Java, C# and C++) use a rather different convention, in which the incrementing or decrementing are left explicit. In these languages a typical for loop fits the pattern

for ( Control = Initial; Condition; Change ) {
Sequence
}

where Condition expresses the condition that must be satisfied before another iteration can be performed, and where Change defines the change that is made to the Control variable at the end of each iteration. In this notation, which is the one we shall use from now on, we would have:

Algorithm 2.4.6

{ // Add the numbers 1 through 10 with a for loop
Sum = 0;
for ( CurrentNumber = 1; CurrentNumber <= 10; CurrentNumber = CurrentNumber + 1 ) {
Sum = Sum + CurrentNumber;
}
write("The total is " , Sum);
}

There are a few points worth making about this very useful construct:

• It would be wrong to try to alter the Control variable in any way within the loop body - the alteration is defined within the parenthesized controlling header of the loop.

• The for loop, like the closely related while loop is also a pre-test loop - the Condition might be such that the loop body sequence is never executed at all. As a rather silly example, consider

for ( I = 10; I < 10; I = I + 1 ) {
write("I is now ", I);
}

• In practice, a great many for loops are controlled by variables whose values change by +1 or -1 only. To handle these succinctly, inspired by notations found in the C family of languages, our notation is extended to allow the Change to be expressed as Control++ or Control-- respectively. Thus we might rewrite Algorithm 2.4.6 as

Algorithm 2.4.7

{ // Add the numbers 1 through 10 with a for loop
Sum = 0;
for ( CurrentNumber = 1; CurrentNumber <= 10; CurrentNumber++ ) {
Sum = Sum + CurrentNumber;
}
write("The total is " , Sum);
}

2.4.6 Repetition - "middle-exit" loops and the "break" construct

In the examples discussed earlier the test for deciding whether the body of a loop should be executed again (or at all) was placed either at the start (as in the while- do and for loops) or at the end (as in the repeat - until or do - while loop) of the construction. Occasionally this is a little awkward, and a less restrictive form of looping structure may be preferable. This is sometimes expressed as

loop
sequence 1 ;
if some condition is met then break ;
sequence 2 ;
end

Here the possibility exists for executing the cycle comprised of sequence 1 and sequence 2 "n and a bit" times, leading to what is sometimes called a middle-exit loop. An example where this construction might be considered preferable to the use of the other constructs is afforded by the averaging problem discussed earlier. This could be developed as follows:

Algorithm 2.4.8

{ // Determine the average of an indefinite list of positive numbers,
// terminated with a non-positive number after the last valid number
Total = 0;
Numbers = 0;
while ( true ) {
Value = read("Supply next number, or one <= 0 to terminate");

if ( Value <= 0 ) {
break;
}

Total = Total + Value;
Numbers = Numbers + 1;
}
if ( Numbers == 0 ) {
write("Error - no valid data processed");
} else {
Average = Total / Numbers;
write("Average is " , Average);
}
}

Note that

• Our formal notation uses the construction while (true) rather than a new keyword loop to introduce such a loop.

• We can have several break points within a single middle-exit loop. The more of them there are, the more difficult it becomes to comprehend the algorithm, unfortunately, and so such looping constructions are rather less popular with the proponents of structured programming than are the other three.

• Although the middle-exit is the most general looping construct, many programmers tend to reserve it for situations like the one exemplified above, where "sequence 1" is something like a simple read operation.

### 2.5 Some suggestions for designing repetitive algorithms

There are several areas in algorithm design where a beginner is apt to get confused. In particular, the repetition which forms a fundamental part of so many algorithms seems to cause a great deal of trouble, and it may be helpful to make some comments on this.

Paradoxically, after realizing that repetition is needed, the next step is often to establish under what conditions the loop will have to terminate - in other words, before you start, worry about how to stop!

In a do-while (repeat-until) loop, the loop body will be executed at least once, while in a while-do loop it need not necessarily be executed at all. In practical computer algorithms the while-do loop is more often used than the do- while (repeat-until) one, and should probably be considered first in cases of doubt.

Beginners sometimes confuse the if-then construct (which has no explicit connotation of repetition) with the while- do construct (which indicates explicit repetition), perhaps because many algorithms have structures which involve a loop within which a secondary decision is made. An example of this appears in the algorithm below, which aims to form the total of the positive numbers in a list which is terminated with a zero, although it might contain numbers of either sign.

Algorithm 2.5.1

{ // Sum list of non-negative numbers
Total = 0;
Value = read("Supply first number");
while ( Value != 0 ) { // continuation condition
if ( Value > 0 ) {   // summation criterion
Total = Total + Value;
}
Value = read("Supply next number");
}
}

Some beginners may be tempted to write this (incorrectly) as

{ // Sum list of non-negative numbers
Total = 0;
Value = read("Supply first number");
while ( Value != 0 ) {  // continuation condition
while ( Value > 0 ) { // summation criterion
Total = Total + Value;
}
Value = read("Supply next number");
}
}

This is an example of an algorithm where one loop has been nested within another. There is a strong possibility that the inner loop will simply run for ever, because nothing in the Total = Total + Value assignment can alter the value of Value.

Sometimes a single loop has a compound termination condition. As an example, consider the following, which adds numbers to a Total only so long as the data values lie outside the range -10 £ Value £ 10.

Algorithm 2.5.2

{ // Form sum of numbers in limited range
Total = 0;
Value = read("Supply first number");
while ( /*either*/ Value < -10 || /*or*/ Value > 10 ) { // continuation condition
Total = Total + Value;
Value = read("Supply next number");
}
}

Some beginners may be tempted to write this (incorrectly) as

{ // Form sum of numbers in limited range
Total = 0;
Value = read("Supply first number");
while ( Value < -10 )  { // only part of the condition
while ( Value > 10 ) { // other part of the condition
Total = Total + Value;
Value = read("Supply next number");
}
}
}

Both of these incorrect algorithms display examples of nested loops - having an outer loop whose body itself contains a further loop. Sometimes nested loops are necessary in algorithms, but care must be taken not to write them when they are not needed.

The for loop should be reserved for situations where the number of repetitions can be easily predicted and enumerated before the loop commences. In such situations it is usually to be preferred over the other constructions.

When it is not known beforehand how many times a loop is to be executed, the use of the while-do or do-while constructs is to be preferred, even when the loop is controlled by a simple increment or decrement of an integer counter.

Different people see the solutions to different problems in different ways, of course. Sometimes one may discern the solution to an intrinsically repetitive problem in a way where repetition seems more implicit than explicit.

As a non-numerical example of this approach, consider the demand made by many a frustrated parent:

Eat up the rest of your first course or I won't serve you any pudding!

How do you comply with this command? Perhaps like this:

Algorithm 2.5.3a

{ // Eat the remainder of your first course so as to qualify for pudding
Take a mouthful;
Chew well and swallow;
if ( there is still some of the first course left ) {
Eat the remainder of your first course;
}
}

or perhaps like this, since you might already have finished immediately before the parental command was issued:

Algorithm 2.5.3b

{ // Eat the remainder of your first course so as to qualify for pudding
if ( there is still some of the first course left ) {
Take a mouthful;
Chew well and swallow;
Eat the remainder of your first course;
}
}

Although there is no explicit repetition here - no do-while or while-do loops - there is implicit repetition, since eating a smaller portion on one's plate involves the same activity - which is needed only if food still remains.

As a more numerically oriented example, consider the problem of deciding whether a number is divisible by three. Many readers will have come across the trick:

"Add up the digits. If the sum is divisible by three, then so was the original number".

For example, the sum of the digits of the number 101124 is 9, which is divisible by 3, as is 101124. But what if the sum so formed is not obviously divisible by 3? For example, the sum of the digits of 1094567325423 is 51. How should 51 be tested for divisibility by 3? Well, the sum of the digits of 51 is 6, which is divisible by 3, so that 51 is divisible by 3, as is 1094567325423. One way of expressing this algorithm, following on from this discussion, is as follows:

Algorithm 2.5.4

{ // Test N for divisibility by 3
Form the Sum of the digits of N;
if ( Sum is 3 or 6 or 9 ) {
write("The number is divisible by 3");
} else {
if ( Sum < 10 ) {
write("The number is not divisible by 3");
} else {
N = Sum;   // Sum will be smaller than the original N
Test /* reduced */ N for divisibility by 3;
}
}
}

Although there is no explicit repetition here - no do-while or while-do loops - there is implicit repetition, since testing the reduced N may be done in the same way as for the original N. This may require testing a still further reduced N, and so on.

These are all examples of a perfectly valid and legal approach to algorithm design, which has led in each case to a so-called recursive algorithm. Such algorithms often occur quite naturally when one is trying to solve problems which amount to taking one step, and then being required to solve essentially a smaller version of the original problem. The idea may seem strange, or it may seem natural, depending on the problem, and on the problem solver, and will be exploited in several places in what follows.

### 2.6 Stepwise refinement

After some familiarity has been gained with the basic control structures to be used in designing algorithms, one can proceed to consider quite a wide variety of problems. The beginner is apt to be baffled at first, or not to know where to begin, and so this section aims to demonstrate a little more of stepwise refinement (or top-down programming, as it is often called). This technique could almost be described by the maxim "Don't do today what you can put off till tomorrow". Essentially the aim is to describe a solution in the broadest terms possible to start with, seizing onto the (hopefully) obvious features first, and then systematically tackling all the smaller problems which these raise - in the same way. (The astute reader will see in this a recursive solution to the problem of finding a solution to a problem!)

To illustrate, consider a simple example from Number Theory:

List all the prime numbers between 2 and 1000 inclusive.

You should be able to recognize that an essential feature of a solution to this problem is repetition, even if you do not remember what is meant by "prime number", and that an algorithm for solving the problem may have to examine all numbers between 2 and 1000. Another essential feature is decision - to each of the numbers which are examined we must apply some test to distinguish the prime ones from the non-prime ones. This leads to a first attempt at an algorithm on the lines of

Algorithm 2.6.1a

{ // List all prime numbers from 2 through 1000
for ( N = 2; N <= 1000; N++ ) {
if ( N is prime ) {
write(N);
}
}
}

A for loop has been chosen because it is known at the outset exactly how many numbers must be examined, even though it is not known at the outset how many will be listed. The algorithm does not yet tell us how to decide whether a number N is prime. But much the same algorithm could have appeared as a first draft for solutions to problems such as "write all numbers between 2 and 1000 which are perfect squares" - or which are multiples of 7, or have binary representations which are palindromes. (It doesn't matter at this stage if you do not know what "binary representation" or "palindromes" mean; indeed, it even strengthens the point we are trying to make.)

We now have to solve the subproblem Is the number N prime? Since a prime number is one having no factors other than itself and 1, a solution can presumably be formulated along the lines of "try dividing N by all numbers between 2 and N inclusive". Again there is a repetitive process, coupled with decision, and after a little thought you should see that this can be expressed as

Algorithm 2.6.1b

{ // Decide whether a number N is prime, given that N > 1
TrialFactor = 2;                  // First attempt at a factor
while ( N is not divisible by TrialFactor ) {
TrialFactor = TrialFactor + 1;  // Move on to next potential factor
}
if ( N == TrialFactor ) ...       // N must have been a prime number
}

Perhaps this is a bit subtle. A while loop has been chosen because it is not known how many possibilities will have to be considered before finding the first exact factor of N (thus ruling out the for loop). Ultimately, of course, were N to have no factors smaller than itself, TrialFactor would become equal to N, and the loop would then terminate satisfactorily, and we could conclude that N was, indeed, a prime number.

There is still a problem to be solved. How do we answer the question Is N not divisible by TrialFactor? This one is quite easy. If dividing N by TrialFactor yields a non-zero remainder, it will follow that N was not divisible by TrialFactor. This concept is best expressed in terms of the mathematical function mod. By A mod B is meant "the remainder when A is divided by B (both assumed to be positive integers)". In languages like Java and C++ the symbol % is used in place of the word mod, and so "N is not divisible by TrialFactor" can be expressed in our notation rather cryptically as

N % TrialFactor != 0

With all these contributions put together, a completely refined algorithm is

Algorithm 2.6.1c

{ // List all prime numbers from 2 through 1000
for ( N = 2; N <= 1000; N++ ) {
TrialFactor = 2; // first trial factor for each N
while ( N % TrialFactor != 0 ) {
TrialFactor = TrialFactor + 1;
}
if ( N == TrialFactor ) {
write(N, " is a prime number");
}
}
}

You may have seen the prime number problem before, as it is widely used in introductory computing texts. We hasten to add that the solution above is far from being the best that could be devised. What we have been trying to illustrate here is how a basic idea is refined into a finished product, and not how the best idea is produced immediately. This is a theme to which we shall continually return.

### Exercises

What has been done so far concentrates only on the control of flow (decisions and repetitions) within an algorithm. Later it will be seen that the exact form of data can have a profound influence on the way an algorithm is designed, but for the moment you are urged to attempt several of the problems in this section so as to consolidate the principles of this chapter.

1. Show that any repeat ... until or do ... while loop can be rephrased using the while ... do and if ... then ... else constructs. Similarly, show how a while ... do loop can be rephrased using the repeat ... until or do ... while and if ... then ... else constructs. Show also how to express a general for loop in terms of the repeat ... until, do-while and while ... do loop constructs, and how each of the while ... do, repeat ... until, do ... while or for loops may be expressed in terms of the loop ... break construct.

2. Develop an algorithm that will read a list of numbers, and add the positive and negative numbers into two different totals, as well as count how many of each kind there are. Once a zero number is read the list can be assumed to be complete.

3. Develop an algorithm that will find the largest and smallest in a list of non-zero numbers. Assume that the end of the list is marked by a zero.

4. Develop an algorithm that will read a list of numbers, terminated with a zero, and write those numbers found in it which form an increasing sequence. For example, given the list 1 6 3 7 8 2 3 9 6 0 the output should be the embedded sequence 1 6 7 8 9.

5. Develop an algorithm that will read in a set of year dates, and write each one with a message saying whether it is a leap year or not.

6. Develop an algorithm that will list all perfect squares which are less than 10000.

7. A "perfect number" is a number equal to the sum of its "proper divisors". The proper divisors of an integer N are those integers less than N which divide into N exactly (6 is a perfect number, as 6 = 1 + 2 + 3). Develop an algorithm that will find and write all perfect numbers less than 100.

8. Euclid's Algorithm for determining the HCF (highest common factor) of two positive integers A and B goes like this: Divide B into A, giving a quotient Q and remainder R. Treat B and R as new values of A and B, and carry on in this way until R becomes zero. The last value of B is the HCF required. Express this in our semi-formal notation, and check that it works. Does it depend on A being larger than B at the start?

9. Another method for finding the HCF of two positive numbers is as follows. Repeatedly take away whichever is currently the smaller from the larger, until the two become equal. The number so reached is the HCF. Assure yourself that this works, and express it in our semi-formal notation.

10. Develop an algorithm that will read a number as the value of a variable Limit, and then tell you how many terms of the sequence

1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 ...

must be added together before the sum of these terms reaches a number in excess of Limit.

### 2.7 Interlude - towards computer coding

Armed with the structures of Section 2.4 you are in a position to describe the flow of control of almost all algorithms. It should, however, be emphasized again that programs consist not only of control structures, but are designed to manipulate data, and as yet only very simple data structures have been mentioned (constants and simple variables). As we shall see later, a good programmer must often give as much thought to the design of data structures as to the control structures which manipulate them.

You still have to learn to code algorithms correctly and completely in Java. Once an algorithm has been designed this is usually straightforward, and in the next chapter we shall start to discuss how this is done.

The human mind is capable of the most amazing tasks, but very few minds are able to assimilate new concepts at anything like the rate which one might like, and so the author of a text such as this one, which purports to introduce a highly technical skill to a reader with little or no background in the subject, is faced with several conflicting and rather daunting constraints. For example, there should be a desire to develop the treatment in a systematic way, in a simple way, in a precise way, and yet in a complete way. There is the need to explain one's method for doing something, while at the same time justifying the rationale for doing it in one way rather than in another, for coding it on one computer language rather than another, or, indeed, for doing it at all. There is the desire to provide clear explanations of past history (as revealed in the already completed programs chosen for illustration), while still providing readers with a measure of confidence for the future (so as to allow them to tackle new problems on their own).

It may be helpful to you to mention some interesting sidelights on this process, at least as this author perceives them.

### 2.8 The issues of scale

Almost all introductory books on programming develop their themes through the use of small examples. This is natural, and unavoidable, but the reader may be deceived into thinking that the effort needed in the development of programs is simply proportional to their length. Unfortunately this is rarely, if ever, true. It has been found, however, that large programs become more manageable if they are developed using the technique known as stepwise refinement, and an example of this approach was given in the last section. Sadly, this technique is often rather unconvincing when applied to small introductory problems.

There is a strong case for leaving programs in a highly modular form, and not merging their components if one can avoid it. To show how this might be done, consider the following variation on Algorithm 2.6.1c, in which we have two "modules", one concerned with the simple problem of determining only whether a number is prime (this module is not concerned with where the number comes from, or what will be done with the result of its investigation), and a second one concerned with the simple problem of merely generating a list of numbers and using the other module to help decide whether they are interesting enough to display:

Algorithm 2.8.1

{ // List all prime numbers from 2 through 1000
for ( N = 2; N <= 1000; N++ ) {
if ( isPrime(N) ) {
write(N, " is a prime number");
}
}
}

function isPrime ( Number ) {
// Given Number > 1, returns "true" if Number is prime, "false" otherwise
TrialFactor = 2; // first trial factor for each Number
while ( Number % TrialFactor != 0 ) {
TrialFactor = TrialFactor + 1;
}
return /* truth value of */ Number == TrialFactor;
}

It is often hard to persuade the beginner to avoid developing so-called monolithic programs, because the first problems set as exercises are often so simple that their solutions can be refined into a single algorithm immediately. It was even harder in years gone by when one was learning to code in old languages like COBOL or BASIC which encourage this approach or even deny any alternative. However, one of the strengths of the more modern languages is that they do encourage (and perhaps even subtly enforce) modularity. Languages like Pascal, Modula-2, C++, Java and C# are particularly rich in such features, but before these can be properly utilized a significant amount of effort may be needed to grasp their simpler aspects, and so the significance of the modular features may not at first be apparent.

### 2.9 The benefits of abstraction

In making progress towards scientific and technological maturity, humans have depended to a great extent on being able to abstract from observations of their surroundings those essential details which allow the development of theories and models which can, temporarily or even permanently, ignore non-essential details. The abstractions in programming apply in several key areas - to the machine itself, to the data it manipulates, and to the operations it can readily perform on that data. To a great extent a programming language reflects assumptions about each of these. Different languages do so to different degrees and in different areas, with the result, for example, that one spoke of the older language Fortran as a "scientific" language and of COBOL as a "commercial language". What one was really doing was stating that the types of problem which Fortran seemed best suited to handle were those found in the natural sciences, where data is almost always numeric in nature, where mathematics is crucial for manipulating that data, and where the concept of computer as calculator par excellence is both necessary and sufficient. Fortran was less successful in areas such as Artificial Intelligence, where data is likely to represent knowledge rather than physical measurements, and where the operations on it are likely to reflect inference, rather than calculation to many figures of significance.

The experienced programmer builds on underlying abstractions of machine and data almost without thinking, but the ground rules are seldom explicitly stated in introductory texts - readers are left to infer a model of the machine and its capabilities for themselves. It may therefore be of interest to look at this model in a little more detail.

At one end of the spectrum a computer can be thought of as many billions of fundamental particles conforming to the theories of wave mechanics. Neither this model, nor an electronic engineer's one of innumerable integrated circuits are usually of much interest to the kind of programmer we have in mind, although they are, of course, of great importance to the designers of the computers themselves. At the other end of the spectrum, a computer might appear to be nothing more than a special purpose toy, tool, or gadget - for example, a video game, a word processor, or the controller of a dish-washer. Somewhere in between these extremes can be placed the concept of a computer which we shall need for our mission of describing the algorithmic approach, namely that it is a fairly general-purpose device, possessing distinctly anthropomorphic (human-like) capabilities of somewhat variable quality. For example, it has an extraordinary patience for carrying out instructions, provided these are set out in the rather stereotyped format hinted at in this chapter, and an excellent memory for storing facts.

You might be curious to know what model you should have in mind when understanding what is meant by computer memory. Once again, the fundamental particle interactions and the electronic components constituting the physical model of semi-conductor memory commonly found in modern computers will be of little or no interest. The lowest conceptual level to which a programmer may need to descend is usually that where memory is though of as retaining information described by a long stream of "bits". The word bit is an acronym for BInary digiT, and reflects the concept of an arithmetic quantity which can have the value 0 or 1, but no others. The connection between this and electronic concepts like "off" and "on" is probably fairly obvious, but, again, is almost irrelevant, as indeed is the limitation to two values. Groups of bits may be arranged into sequences of larger cells or entities (commonly termed machine words), which the programmer can think of abstractly as representing the values of whole numbers, fractions, characters, names, addresses, colours, shopping lists, parking tickets, value judgements, or almost anything else; indeed, the kind of programmer at which this book is directed rarely needs to be aware of bits at all.

Most programming languages - certainly the ones you may first encounter - will entertain the abstract concepts of integral and fractional numbers, literal characters, and simple lists of these. Some languages go little further than that; anything more complicated or complex must be modelled by the programmer in terms of these primitive types, sometimes with considerable difficulty.

Nevertheless, although the list of higher level data abstractions which a programming language directly supports will vary a great deal from one language to another, well-designed algorithms and programs are invariably organized in terms of differing "levels" of abstraction. That is to say, components of programs are designed to reflect the desire to work at as high a level of abstraction as possible for as long as possible. This is something which is closely akin to the idea of stepwise refinement, of course.

In respects other than being blessed with a good memory and infinite patience, where it scores handsomely over the average human being, a computer must often be regarded as a simpleton. It will be able to do very simple arithmetic on the values stored in its memory, such as addition, subtraction, multiplication and division, be able to recognize characters making up a text, be able to communicate with humans by reading and writing characters with some legibility or displaying graphs and pictures, be able to make simple comparisons as regards relative ordering of numbers or letters, and to decide what action to follow as a result, provided clear-cut alternatives have been specified. Many programming languages reflect these capabilities, and have suitable notations for taking advantage of them. Of course, modern specialist hardware goes somewhat further than that - interfaces to sophisticated graphic devices, audio devices, networks and telecommunications have become commonplace in recent times, as has the development of specialized notations or languages to ease the programming problems associated with using them.

But where greater perception or "intelligence" is demanded, machines still seem to differ more radically from their human counterparts, and this is reflected by computer languages becoming correspondingly and irritatingly more restrictive. The basic elements of a modern language like Java are still quite a long way from the vocabulary needed for proving theorems, performing music or analyzing poetry. Even at a lower level, although notations for describing simple arithmetic are common, some programming languages do not reflect the ability to extract square roots, factors, or even remainders (for many applications that is of no consequence, of course). Although the machine can be expected to recognize and distinguish letters, the concept of arranging these into words may be foreign, and the ability to to attach any meaning to a word almost certainly will be beyond it, at least without extra effort on the part of the programmer. Then again, it will be found that the machines have effectively no flair for innovation, or for reacting to the unexpected. If left to themselves they will plod along one step at a time until any job assigned to them is done, unwilling and unable to make use of external help, even if any is forthcoming. Again, this is of little consequence in many applications, but it is a limitation which has the effect of placing rather artificial constraints on the learner programmer, whose life up till that point has probably been largely influenced by interactions with other living creatures, and one of whose achievements is, almost certainly, the ability seemingly to handle more than one activity at a time (for example "boiling potatoes and roasting the meat" or "marching down the road and playing the bagpipes and keeping in step and keeping in line and waving at one's friends").

It may help to place this into better perspective by returning to the algorithm for going to the cinema. Part of Algorithm 2.1.2 reads

if there is a queue then
join it at the back
repeat
shuffle forward
until everyone in front of you has been served

If this is to be refined further, several awkward things must be considered. What exactly is a "queue", how does one detect its existence, and how does one "join it"? It is more than merely a collection of people; in well- behaved society, at any rate, it is a row with a distinct property reflecting order, and joining it involves subscribing to a convention that it fills at one end and empties from the other (well, not always, for some individuals are entitled to "jump" queues, or do so regardless). These properties are rather unnaturally specified in purely numerical terms. Then again, the earlier discussion of a while loop was given under the assumption that a single individual was in complete control of the situation - after making a decision whether to proceed or not, she might carry out a sequence of instructions, one or other of which affected the outcome of essentially the same decision when she came to make it again. In a cinema queue (in well-behaved society, at any rate) it is the interaction of other "processors" in the system - in particular the box-office manager and the person at the head of the queue - which affects the outcome of whether one continues to shuffle forward, not the action of shuffling itself. These interactions are difficult, if not impossible, to specify completely in terms of the actions of a single sequential automaton.

It should be noted, however, that an important part of modern computing does concern itself with parallel processing, where there is more than one process going on simultaneously (perhaps with two or more computers working together). Discussion of this is usually thought to be outside the scope of elementary texts in Computer Science, and, anyway, few of the computer languages used for teaching introductory sequential programming can handle parallel programming effectively.

### 2.10 The problems of syntax

When using languages like English or German, authors have to be aware of the conventions of grammar governed by so-called Syntax Rules (such as the requirement that sentences should contain a verb, and be terminated with a full stop or other appropriate punctuation mark). In the same way, one finds strict rules for the syntax of the "sentences" of programming languages.

A great many books adopt an approach in which they simply take fully coded programs, and explain in great detail the meaning of each statement, concentrating on the many rules of syntax which must be obeyed when a partially solved problem reaches the coding stage. There is a distinct danger here that you may never see the wood for the trees, for all too often the elements of the programming language are taught in almost complete isolation from a motivated discussion of program design and problem solving. Learning, in effect, proceeds in a "bottom up" rather than in a "top-down" manner. One might draw the analogy of teaching a spoken language by first requiring that the student learn rules of grammar, and memorize lists of irregular verbs, prepositions, synonyms and so on, without any real idea of the context in which the words themselves should be used.

Unfortunately, the syntax of nearly all programming languages - certainly of ones like C#, C++ and Java - is far stricter than that of written natural languages like English. The difference is akin to that which exists between written and spoken natural languages. Any course which does not stress the role and importance of correct syntax is bound to cause heartache for those who take it. Descriptions of syntax can become very dull to read, difficult to understand, and still more awkward to digest. Perhaps for these reasons, beginners in programming often perceive all the problems which they have as emanating from syntactic faults, and spend a disproportionate effort in eliminating these, rather than on concentrating on the more fundamental aspects of the problem being handled. The present text makes quite an effort to concentrate on algorithm design, of course, in an attempt to bring these areas into the correct perspective.

Home  © P.D. Terry