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:
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.
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 Buy a ticket 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 buy a ticket 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,
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 ) { buy a ticket; 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.
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
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.
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:
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 { read next Value; 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:
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.
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:
for ( I = 10; I < 10; I = I + 1 ) { write("I is now ", I); }
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
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.
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.
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 + 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.
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.
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.
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.
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.