PHY2027 Lecture 0

Would you drive into a river if your satnav told you to?

A taxi driver following his satellite navigating instructions ended up stranded in a river after taking a wrong turning at a ford in the road. The red-faced driver - working for a taxi company called Streamline - drove 200 yards up the River Nar in Norfolk before his eight-seater minibus ground to a halt on the muddy river bed.

[ Daily Mail, photo Albanpix.com ]

A woman wrote off her £96,000 Mercedes-Benz and nearly drowned when she followed the instructions of her onboard satellite navigation device into a river... The woman, who identified herself as Hayley, 28, from London, drove her SL500 into the river where it was swept 200m downstream, bouncing from bank to bank.

[ The Times, photo Tony Swift published in The Evening Standard ]

Algorithms and data

Computer programs are about algorithms and data.

An algorithm is unambiguous specification of a set of instructions that can be followed in a mechanical, unthinking, manner to achieve the desired result.

Unlike the instructions we give to human beings algorithms do not require, or even allow for, the use of common sense or intelligence. The agent executing the algorithm has absolutely no choice in what steps to take. All the intelligence is in the algorithm.

The instructions we discussed at the beginning of this lecture are an example of an algorithm as they do not allow the application of individual intelligence or judgement when executing them.

Another example of an algorithm

We are unlikely to ever need to tell a computer to walk to St Davd's station!  A simple but more realistic example might be that we are asked to write a computer program to calculate the wages due to an hourly-paid employee given their hourly pay and a set of time-sheets saying how many hours they had worked each day. The specification might be:

Specification: an employee's pay is the total number of hours they have worked multiplied by their hourly wage, with Sundays paying double time and Saturdays time and a half.

Such a specification is not in itself an algorithm as it is not a sequence of instructions, but it is not hard to come up with one. A typical example might be:

• For each employee:
  1. Initially set the running-total (of the employee's pay) to zero.
  2. For each day in the time period under consideration:
     1. Multiply the employee's hourly-wage by the number of hours they worked that day to obtain that day's pay.
     2. If the day is a Sunday multiply that day's pay by two.
     3. Otherwise, if the day is a Saturday multiply that day's pay by one-and-a-half.
     4. Add that day's pay to the running-total.
  3. At the end of this the running-total is now the final total of pay owing to that employee.

Given such a set of instructions a person of average intelligence could calculate the pay due to each employee.

Our algorithm above has several of the features and issues found in just about every computer program. All of these are important and all of which are simple to understand and deal with in a problem of this size. As our program grows in size some of these issues will remain simple and manageable. Others will not. Let's look at a few of these concepts in turn, as they illustrate the major issues we will be covering over the next few weeks.

Features of this algorithm

Data

The algorithm has terms such as"day-of-the-week " and "hourly-wage" which serve as "place holders", to be replaced by the actual value of that quantity when the algorithm is run, as well as others such as "running-total" which are calculated at the time. Furthermore the value of "running-total" is not a fixed quantity but is updated as the algorithm progresses. Quantities such as running-total, hourly-wage and day-of-the-week are referred to as variables.

At the supermarket the till keeps track of the running total of the bill, which changes as items are swiped through. When they ask us for 16.82 at the end it's no use complaining that after they had swiped through the first item the bill was only 50p!

Some quantities, such as running-total change their values as the algorithm is executed.

In fact, if we look at the description of what we were trying to achieve we will see that it is defined in terms of data: what we are trying to calculate and how that is related to what we already know.

Growability factor: large.

The key to writing or understanding an algorithm is to understand the data it operates on, and the results it is meant to produce.

Sequences of instructions which are performed several times (loops)

Almost every program we ever write will contain a number of repeated actions, and the C programming language contains several convenient ways of defining them. The one illustrated here is a common type where a particular variable, in this case the day, has a different value every time the loop is run ("Monday", then "Tuesday", etc).

Growability factor: small.

If ... otherwise

(To save typing, programming languages tend to use the word "else" instead of "otherwise".)

These steps, often called as conditionals refer to steps ("multiply that day's pay by two.") which are only performed if a certain condition is met ("If the day is a Sunday").

Algorithms have subsets of instructions that may be executed several times or only if a certain condition true.

You may have noticed that our two criteria ("It's Saturday" and "it's Sunday") are mutually exclusive so we could have missed out the word "otherwise" and simply written:

2. If the day is a Sunday multiply that day's pay by two.
3. If the day is a Saturday multiply that day's pay by one-and-a-half.

However, the two are not always equivalent, for example a menu application might say "If the diner is lactose-intolerant substitute non-dairy ice-cream, if the diner is gluten-intolerant substitute rice noodles...", in which case adding "otherwise" to the second and subsequent conditions would be a mistake.(In our actual Sunday/Saturday case having the word "otherwise" is clearer which is why we prefer it.)

Notice too that the criterion depends on the values of one of our variables, in this case the day. As the condition is inside a loop ("for each day") it follows that the day variable will sometimes be "Sunday", sometimes "Monday", etc. So our variables are not just used for "obvious" mathematical calculations they also control the behaviour of the algorithm.

The criteria that decide whether an instruction is executed or how often a loop is run depend on the values of our variables.

Growability factor: medium.

Issues with algorithms

Requirements change

We can illustrate this by noticing that our specification does not account for Bank Holidays (also known as public holidays). This could easily change, either because somebody realised they had forgotten about them, or because of a genuine change in pay agreements after the original specification. Both of these are very common and should be borne in mind when writing our computer program. The revised specification might be:

Specification (v1.1): An employee's pay is the total number of hours they have worked multiplied by their hourly wage, with Sundays and Bank Holidays paying double time and non-Bank-Holiday Saturdays time and a half.

Note the careful definition: had we said "Sundays and Bank Holidays paying double time and Saturdays time and a half" the question would have arisen: "Do Bank Holiday Saturdays pay time and a half, double time or triple time?". Look out for ambiguities in specifications, they make lawyers rich and programmers make mistakes.

The relevant part of our algorithm is now:

2. If the day is a Bank Holiday or a Sunday multiply that day's pay by two.
3. Otherwise, if the day is a Saturday multiply that day's pay by one-and-a-half.

Notice that missing out the "otherwise" would now cause an error.

We will always need to manually "walk though" our algorithm to check for errors. (See below.)

A walk through will catch an error if it's a simple oversight. But suppose we implicitly assumed that all Bank Holidays are Mondays (as they tend to be in the UK), forgetting about Christmas and New Year's days. The walk-through wouldn't catch that as we would think it was correct.

Be even more careful about implicit assumptions than you are about ambiguities.

Growability factor: medium.

Our simple task is  part of a larger whole

Growability factor: large.

It requires us to think about more than one thing at a time

Growability factor: "Look out, I think it's coming this way!!".

This is the single biggest issue we will face and we shall be thinking about strategies to deal with this over the next few weeks.

Other issues with algorithms

"Canned" instructions that can be used several times

Our initial example, going from the Physics Building to St David's station, was fine as a one-off. But as mentioned above, iIn real life we  have a mental list of places we know how to get to ("the High Street", "the M5", "Crediton") to act as common first stages (the directions from Exeter to a lot of places start "take the M5 north..."). Without this collection, or library, of "sub-routes" we would find it very hard to remember how to get anywhere.

This also fits in with our "testing" idea: it's relatively easy to check a short route is correct and once that's done we can use it again and again. Less obviously, but very importantly, routes can change due to new road layouts and we instinctively think of this in changes to canges to one route ("getting to the M5") rather than a large number of routes which all start the same ("getting to Bristol", "getting to Birmingham", "getting to my brother's house").

In practice all algorithms of any complexity can only be made manageable by this process of divide and rule.

Long sequences of instructions will need to be broken down into independent chunks each with their own tests to check they are correct.

Handling Errors

Finally, one major aspect of programming this example does not illustrate is the handing of errors ("I can't find Fred Smith's time sheets!"). We will start to address this at the start of the next lecture.

Layout and "white space"

One factor that's so obvious that you probably didn't notice it is that when we displayed the algorithm we automatically indented the levels of bullet points to reflect the structure of the algorithm. Bullet points are always displayed this way of course, and so are computer programs and for the same reason: it makes them much easier to understand.

The "rules" for using so-called "white space" to enhance readability go back to the beginning of print (and maybe before?) and also include using blank lines to indicate divisions and subdivisions. White space has no effect on the meaning of the algorithm but when used correctly makes it easier for us to understand (and when used incorrectly, harder to understand!).

Walking through our algorithms

To execute our initial "getting to St David's" example we would simply travel down the route. Of course we didn't actually have to do this to work out where it led to: mentally we (almost literally) walked through the algorithm and kept track of our location and direction of travel. These two pieces of information, together with the next instruction to be executed, told us all we needed to know and enabled us to work out what the algorithm did. If we wished to visualise this to somebody else we might have a map with a little arrow showing were we were and watch the little arrow moving as we follow the instructions.

For our our more-realistic "wages" example what we need to keep track of is not our physical position but the current value of the hourly rate, the running total etc, ie the values of our variables. These are the equivalent of our "location and direction of travel" in the previous example and to visualise the current state of our algorithm and to see what effect it has we just need to show the value of its variables.

The main question we need to ask about a short section of our code is "what happens to the values of our variables?".

Stepping through our algorithms

Everything the computer does is incredibly simple and understand a piece of code we must be able to work out what we would do if we were to be executing it ourselves.

A bit of an aside: the original, human, computers

Amazing as it may seem today the original "computers" were actually human beings equipped with a set of instructions (the algorithm), a mechanical calculating machine and some cards for recording the results. Usually, of course, there would be a large number of intermediate results which the computer would write on a card and s/he would then read the number off the card later on in the calculation.

A room of computers from around the 1920s.
Note the woman in the fourth row reading instructions and/or data from a card.
Image: United States Library of Congress.

These computers would easily be capable of running the small pieces of computer program we will be dealing with in the next few lessons. The computer isn't doing anything they couldn't do, it's just doing it really, really fast and with an enormous amount of memory.

The human computer

When evaluating an algorithm such as our "wages" example we can imagine ourselves as a "human computer" equipped with:

• A pack of index cards, each with its own unique ID number and a space to write a single numerical value.
• A pencil and an eraser
• A calculator

Unique card ID number 240 x (double) (Not written on the card) Value: write in pencil only! 12345.6

The equipment issued to us in our role as the human computer

We execute the program steps by performing the calculations and and writing the resulting variable values on small yellow index cards, writing in pencil (so the value can be changed) with one variable value one per card.  We might decide to use card 200 to store the hourly wage, card 208 to store the hours worked,  etc.

When a variable's value changes we rub out the old value on the index card and use the pencil to write in the new one. When we need to know the value of a variable we just read it off the card. (Of course, this requires that we can remember which variable value is written on each card - we will deal with this a little later.)

It may seem extremely strange that we can model such as complicated thing as a computer so simply. But the complexity of modern computers is mainly dedicated to running programs extremely quickly and ironically much of that complexity is dedicated to complicated actions whose sole job is to produce exactly the same result as the simple system but faster or allowing several separate programs to run at the same time without interfering with each other. .

For reasons that will become very important in the latter half of this course we will assume that the cards are individually numbered and arranged in numerical order, to help us find the one we want, and that we say to ourselves something like "I will store the value of variable x on card 12". This is actually a remarkably accurate model of how the computer actually works and we shall use it for the next few lessons. (NB: it is the fact that the cards are numbered that makes this a good model of how the computer behaves. If you are wondering why ask yourself "how does an actual computer specify where it is storing the value of a variable?")

We will see this simple model "in action" on very short computer programs in the next few lessons.

By analogy with a house number, the variable's index-card number is called the "address" of that variable as it not only identifies it but also tells us where to find it.

To think about after the lecture

• Whether our instructions are right or wrong, the computer will follow them with a level of mindless obedience that makes people who drive into rivers because their sat-nav told them to look like geniuses in comparison. We can't assume the computer will know what we mean!
• We can't rely on being able to write a large number of instructions without making a mistake. Instead we write a small amount at a time and test, test, test.
• The data our algorithm operates on is actually the most important part of our thinking.
• If the exercises we give we were to be part of a larger whole, how would that change the way we answer them?
• Plan for the specification of our program to change.
• We check the logic of our program by "walking through" the algorithm, keeping a conceptual track of the values of its variables.
• We can only think about a few things at a time.