An extract from my textbook...
ü Create clear, easily understood algorithms.
ü Apply the principal of strong cohesion.
ü Create a dry run table to test an algorithm.
An algorithm is a list of steps that explain how we process data to produce useful output.
Computer programmers and systems analysts are very skilled at creating algorithms. An algorithm becomes a part of the design for a computer program.
The simplest type of algorithm is a list of steps that are processed one by one until there are no more steps left.
Example 1. This algorithm adds up the numbers 5 and 7 and output the result.
Algorithm 1
1 | A ß 5 |
2 | B ß 7 |
3 | Answer ß A + B |
4 | PRINT Answer |
The steps in an algorithm are called statements. Algorithm 1 has exactly 4 statements. Each statement has a line number.
We complete each statement one after the other. If we are sure that the algorithm is correct then we can convert the algorithm into a program that will run on a computer.
Understanding Algorithm 1.
Now we will look at each statement in the algorithm.
Statement 1 is Aß 5
This is called an assignment statement. The assignment statement “assigns” the value 5 to a memory variable called ‘A’. We say ‘A is assigned the value 5’.
Statement 2 is Bß7
This assignment statement “assigns” the value 7 to a memory variable called ‘B’. We say ‘B is assigned the value 7’
Statement 3 is Answer ß A + B
This assignment statement “assigns” the value of 5+7 to a memory variable called ‘Answer’. We say ‘Answer is assigned the value of the expression 5+7.’ This means Answer is assigned the value 12.
Statement 4 is PRINT Answer
Statement 4 is an output statement. This means that something will be displayed that we can see. We can not see the result of an assignment statement. We can only see the result of an output statement. We might say that the line 4 statement “outputs the value of answer”. In this case the output produced by this line will be the number 12.
Test yourself .Q1 Answer the questions about Algorithm 2.
Algorithm 2.
1 | A ß 2 |
2 | B ß 3 |
3 | C ß 11 |
4 | Total ß A + B + C |
5 | PRINT Total |
Q1.a. Write down the number of statements in Algorithm 2 | _________________ |
Q1.b Write down the statement on line 3 | _________________ |
Q1.c Write down the value of variable B after line 2 is completed. | _________________ |
Q1.d Write down the output produced by line 5 | _________________ |
Q2. Make your own algorithm that will add up the 4 numbers 7,3,5,8 and output the total.
1 |
2 |
3 |
4 |
5 |
6 |
A statement that starts with the name of a variable and then is followed by ß symbol is called an assignment statement. The left part of an assignment statement is called the identifier. And the right side of an assignment statement is called the expression.
Example 2. Line 23 calculates the volume of a box.
23 Volume ß width * height * length
§ The identifier is Volume.
§ The expression is width * height * length
§ The whole statement is called an assignment statement because it starts with an identifier and then the ‘ß’ follows straight afterwards. Note that * is used for multiplication.
The format of an assignment statement is identifier ß expression
Operators used for arithmetic.
Some special symbols are used for arithmetic.
v Addition +
v Subtraction -
v Multiplication *
v Division /
Test Yourself:Q2. This line calculates the area of a triangle.
12 Area ß base * height / 2 |
Q3.a What is the line number for the algorithm statement above? ___________
Q3.b What is the identifier for this statement? ___________
Q3.c If the value of base is 5 and the value of height is 4, then what value will be assigned to Area after line 12 is completed? ___________
If we want an algorithm to work for more than one set of data then we should use INPUT statements. Consider our very first algorithm.
1 | A ß 5 |
2 | B ß 7 |
3 | Answer ß A + B |
4 | PRINT Answer |
This algorithm works well if all we want to do is add up the numbers 5 and 7. Suppose we wanted to add 11 and 45. Then we would need to modify the algorithm for the new problem. The new algorithm would look like this
1 | A ß 11 |
2 | B ß 45 |
3 | Answer ß A + B |
4 | PRINT Answer |
It is time consuming and inconvenient to keep modifying the algorithm every time the data changes. We use input statements when we want an algorithm to work with more than one set of data.
Example 3. If we want to add up any two numbers then the algorithm would look like this.
1 | INPUT A |
2 | INPUT B |
3 | Answer ß A + B |
4 | PRINT Answer |
Now we can add together and output the sum of any two numbers. The values of A and B can be anything we choose.
Example 4. To make an algorithm that can be used to calculate and display the perimeter of any rectangle. The algorithm will look like this.
1 | INPUT width |
2 | INPUT Length |
3 | Perimeter ß 2 * (width + length) |
4 | PRINT Perimeter |
Test yourself: Q3. Write down an algorithm that will calculate and display the area of any rectangle.
1 |
|
2 |
|
3 |
|
4 |
|
6.3 Dry run tables
Algorithm
1 | A ß 5 |
2 | B ß 7 |
3 | Answer ß A + B |
4 | PRINT Answer |
Dry run table
Line | A | B | Answer | Output |
1 | 5 |
|
|
|
2 |
| 7 |
|
|
3 |
|
| 12 |
|
4 |
|
|
| 12 |
A dry run table is used to show whether or not an algorithm is correct. The table shows:
v The values assigned to variables
v The output produced by an algorithm.
A simple dry run table has columns for
§ A line number column
§ A column for each identifier
§ A column for output
There are some other columns that we can add to a dry run table that we shall learn about a little later.
Example 5. A dry run for an algorithm that adds up the numbers 5 and 7.
1 | A ß 5 |
2 | B ß 7 |
3 | Answer ß A + B |
4 | PRINT Answer |
Dry run table
Line | A | B | Answer | Output |
1 | 5 |
|
|
|
2 |
| 7 |
|
|
3 |
|
| 12 |
|
4 |
|
|
| 12 |
The output for this algorithm is 12. This shows that the algorithm is correct.
Test yourself: Q4. . Complete the dry run table for this algorithm. The algorithm adds together 51,72and 112.
1 | A ß 51 |
2 | B ß 72 |
3 | C ß 112 |
4 | Total ß A + B + C |
5 | PRINT Total |
Fill in the shaded spaces in the dry run table.
Line | A | B |
| Total | Output |
1 | 51 |
|
|
|
|
2 |
|
|
|
|
|
3 |
|
| 112 |
|
|
4 |
|
|
|
|
|
|
|
|
|
| 235 |
Test yourself: Q5. Make a dry run table for this algorithm that multiplies two numbers and shows the result. This algorithm calculates the pay for someone who works for 5 hours and has pay rate $7 per hour.
1 | Hours ß 5 |
2 | Rate ß 7 |
3 | Pay ß Hours * Rate |
4 | PRINT Pay |
Dry run table
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Note: Note that we have made identifiers Hours, Rate and Pay in this algorithm. We have chosen these names for our variables because as it helps us to understand what the algorithm is supposed to do. We should always choose sensible names for variables.
We use data sets to test algorithms that contain INPUT statements. Whenever we reach an INPUT statement we use the next available value in our dataset. Once a value from the dataset is used it can not be used again.
Example 6. An algorithm to calculate the perimeter of any rectangle.
1 | INPUT Width |
2 | INPUT Length |
3 | Perimeter ß 2 * (Width + Length) |
4 | PRINT Perimeter |
Dry Run Table: Data set {6, 11}
Line | Width | Length | Perimeter | Output |
1 | 6 |
|
|
|
2 |
| 11 |
|
|
3 |
|
| 34 |
|
4 |
|
|
| 34 |
After line 1 of the algorithm is completed the value of Width will be 6. This is because 6 is the first value in our data set. After line 2 of the algorithm is completed the value of Length will be 11. This is because 11 is the next available value in our data set.
This dry run table shows that our algorithm works for the data set {6,11}
Example 7. What if the dataset contains abnormal values?
1 | INPUT Width |
2 | INPUT Length |
3 | Perimeter ß 2 * (Width + Length) |
4 | PRINT Perimeter |
Dry Run Table: Data set {9, -4}
Line | Width | Length | Perimeter | Output |
1 | 9 |
|
|
|
2 |
| -4 |
|
|
3 |
|
| 10 |
|
4 |
|
|
| 10 |
This dry run table has produced an output value that can not be true. We can not compute the perimeter when the value of length is -4.
The best we can say is that our algorithm works sometimes. It works correctly when the data is ‘normal’. If the data is ‘abnormal’ then the algorithm produces an answer that does not make sense.
We can change the algorithm so that it works all the time, but that is a more complicated matter that we shall leave until later in the chapter.
Note: One of the major challenges for people who design algorithms is to make algorithms that will work for all data sets. This can be difficult to do and even harder to prove. Even simple algorithms will produce unreliable output if the INPUT data is abnormal.
Example 8. This algorithm is designed to calculate the average of 3 numbers.
1 | INPUT N |
2 | INPUT First |
3 | INPUT Second |
4 | INPUT Third |
5 | Total ß First + Second + Third |
6 | Average ß Total / N |
7 | Display Average |
If we make a dry run table for {3, 23, 41, 20} then we can say.
ü Algorithm works. The output is 28.
(You can try this for yourself by making a dry run table using {3, 23, 41, 20} )
If we make a dry run table for {2, 12} then we can say
r Error, the algorithm will not work because we can not complete line 3. There is not enough data in the data set.
Test yourself: Q6 Say whether or not each data set will produce accurate results. It is best if you can make your own dry run table on a piece of paper. Then it will become clear whether or not the algorithm will process the data set correctly.
Q7.a If we make a dry run table for {3, 12, 14, 18} then we can say
……………………………………………………………………………….
……………………………………………………………………………….
Q7.b If we make a dry run table for {4, 12, 14, 18} then we can say
……………………………………………………………………………….
……………………………………………………………………………….
Q7.c If we make a dry run table for {3, -12, 0, 18} then we can say
……………………………………………………………………………….
……………………………………………………………………………….
Q7.d If we make a dry run table for {3, 0, 0, 0} then we can say
……………………………………………………………………………….
……………………………………………………………………………….
Algorithms should make output that is easy for human beings to understand. Which of the two lines below is easier to understand?
Clearly the second line is easier to understand. Producing output that is easy to understand is quite simple to do.
Example 9. The output line for the example 8 algorithm is
7 | PRINT Average |
It will generate output like
We can modify line 7 so that it looks like this.
7 | PRINT ‘The average of the 3 number is’, Average |
The output will now be
‘The average of the 3 number is’ is called a literal.
When literals are printed the output will be exactly what is contained inside the quotation marks. Literals are used to make output statements easier to understand.
It is good to use literals in output statements. However, we need to be careful to make sure that we enter quotation marks and commas in the right places.
Some good examples of the use of literals! There are no mistakes in these statements.
ü 6 PRINT ‘The area of the circle is ’ , CircleArea
ü 11 PRINT ‘The date will be ’ , DateOfWedding
ü 9 PRINT ‘The product is ’ , first * second
ü 23 PRINT ‘Her wage will be ’, Wage, ‘ dollars’
ü 31 PRINT X, ‘+’, Y, ‘=’, X+Y
Some bad examples of the use of literals! See if you can work out why each line is incorrect…
r 7 PRINT ‘The area of the circle is , CircleArea
r 13 PRINT “The product is ’ , first * second
r 45 PRINT ‘Her wage will be ’, ‘Wage’, dollars’
Here are the reasons why the lines above are incorrect.
7 PRINT ‘The area of the circle is , CircleArea Q
A quotation mark is missing before the comma. The line should say
7 PRINT ‘The area of the circle is ’, CircleArea R
13 PRINT “The product is ’ , first * second Q
The quotation marks do not match up. We can use “ all the time or else we should use ‘ all the time.
13 PRINT ‘The product is ’ , first * second R
45 PRINT ‘Her wage will be ’, ‘Wage’, dollars’ Q
There should not be quotation marks around the variable called Wage. Also the word dollars does not have two quotation marks around it.
45 PRINT ‘Her wage will be ’, Wage, ‘ dollars’ R
So far we know about three types of algorithm statement. These are
v INPUT statements
v Assignment statements
v Output statements
We are now going to consider a new type called Selection Statements. Selection statements make an algorithm complete some statements some of the time and other statements at other times. The best way to understand these statements is to have a look at some examples…
The simplest selection statement is the IF/THEN statement.
Example 10. Here is an algorithm that will input a temperature and then say ‘It is Hot’ if the temperature is greater than 31 degrees.
1 | INPUT Temperature |
2 | IF Temperature > 31 THEN |
3 | PRINT ‘It is Hot’ |
4 | END IF |
Understanding the algorithm…
§ If the INPUT is 33 then the output will be ‘It is Hot’.
§ If the INPUT is 12 then there will be no output.
Look at the dry run tables below. These examples show how the algorithm works. Pay attention to which line numbers are completed and which line numbers are missed out.
Data set {33}
Line | Temperature | Temperature > 31 | Output |
1 | 33 |
|
|
2 |
| Yes |
|
3 |
|
| It is Hot |
4 |
|
|
|
Data set {13}
Line | Temperature | Temperature > 31 | Output |
1 | 13 |
|
|
2 |
| No |
|
4 |
|
|
|
We only complete line three of the algorithm if the condition Temperature > 31 is true.
If the condition Temperature > 31 is false then the next statement to complete will be 4 END IF. The END IF statement does not actually do anything. Its only purpose is to show where the end of the IF/THEN statement is.
Example 11. In this algorithm we want the output to say ‘It is Cold!!!’ if the temperature is less than 10 degrees.
1 | INPUT Temperature |
2 | IF Temperature <10 THEN |
3 | PRINT ‘It is Cold!!!’ |
4 | END IF |
Data set {5}
Line | Temperature | Temperature < 10 | Output |
1 | 5 |
|
|
2 |
| Yes |
|
3 |
|
| It is Cold!!! |
4 |
|
|
|
Data {13}
Line | Temperature | Temperature < 10 | Output |
1 | 13 |
|
|
2 |
| No |
|
4 |
|
|
|
Test yourself: Q7. : Make an algorithm that will output ‘Your grade is ‘Pass’ if a mark value greater than 49 is INPUT. Test your algorithm with the following data sets.
Your Algorithm
1 |
|
2 |
|
3 |
|
4 |
|
Your Dry Run tables
(i) Data Set {89}
Line |
|
|
|
1 | 89 |
|
|
|
|
|
|
|
|
|
|
(ii) Data Set {45}
Line |
|
|
|
1 | 45 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(iii) Data Set {49}
Line |
|
|
|
1 | 49 |
|
|
|
|
|
|
|
|
|
|
Notes:
IF…THEN…ELSE
Sometimes we would like to be able to do two alternative things, depending on the value of some condition. For this purpose we can use an IF … THEN… ELSE statement.
Example 12. The purpose of this algorithm is to input a mark for a test and say ‘Pass’ if the mark is bigger than 49. The algorithm will say ‘Fail’ if the mark is less than 50.
1 | INPUT TestMark |
2 | IF TestMark >49 THEN |
3 | Grade ß ‘Pass’ |
4 | ELSE |
5 | Grade ß ‘Fail’ |
6 | END IF |
7 | PRINT ‘Your grade is ’, Grade |
Dry run table Data set {36}
Line | TestMark | TestMark >49 | Grade | Output |
1 | 36 |
|
|
|
2 |
| No |
|
|
5 |
|
| Fail |
|
7 |
|
|
| Your grade is Fail |
Dry run table Data set {92}
Line | TestMark | TestMark >49 | Grade | Output |
1 | 92 |
|
|
|
2 |
| Yes |
|
|
3 |
|
| Pass |
|
7 |
|
|
| Your grade is Pass |
Test yourself. Q8. Complete this dry run table using the data set {67}.
Dry run table Data set {67}.
Line | TestMark | TestMark >49 | Grade | Output |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Test yourself: Q9. Complete this dry run table using the data set {22}.
Line | TestMark | TestMark >49 | Grade | Output |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
We use a CASE statement if there are more than two alternative lines to go to.
Example13. An algorithm to display ‘Distinction’, ‘Credit’, ‘Pass’ or ‘Fail’ depending on the value of an input mark.
In this example there are 4 different alternative outputs. If there were only two possibilities then we would make an algorithm that uses an IF … THEN statement. However, since there are more than two alternative statements we choose to use a CASE statement.
1 | INPUT mark |
2 | CASE mark OF |
3 | 0 TO 49: grade ß ‘Fail’ |
4 | 50 TO 65: grade ß ‘Pass’ |
5 | 66 TO 74: grade ß ‘Credit’ |
6 | OTHERWISE grade = ‘Distinction’ |
7 | END CASE |
8 | PRINT ‘Your grade is’, grade |
Look closely at the way the CASE statement is organized. Here are some observations that you can keep in mind when you are using CASE statements.
Here are some Example 13 dry run tables. Step through these dry run tables your self. Pay attention to which line numbers get completed.
Dry run table Data set {45}
Line | Mark | grade | Output |
1 | 45 |
|
|
3 |
| Fail |
|
8 |
|
| Your grade is Fail |
Dry run table Data set {85}
Line | Mark | grade | Output |
1 | 85 |
|
|
6 |
| Distinction |
|
8 |
|
| Your grade is Distinction |
Dry run table Data set {62}
Line | Mark | grade | Output |
1 | 62 |
|
|
4 |
| Pass |
|
8 |
|
| Your grade is Pass |
Test yourself: Q10. Complete this dry run table for this algorithm.
1 | INPUT mark |
2 | CASE mark OF |
3 | 0 TO 49: grade ß ‘Fail’ |
4 | 50 TO 65: grade ß ‘Pass’ |
5 | 66 TO 74: grade ß ‘Credit’ |
6 | OTHERWISE grade = ‘Distinction’ |
7 | END CASE |
8 | PRINT ‘Your grade is’, grade |
Dry run table Data set {56}
Line | Mark | grade | Output |
|
|
|
|
|
|
|
|
|
|
|
|
Test yourself: Q11. Complete this dry run table
Dry run table dataset {123}
Line | Mark | grade | Output |
|
|
|
|
|
|
|
|
|
|
|
|
Note: This last dry run table should tell you that there is something wrong with our algorithm. When we enter 123 for the mark the output column will say ‘Your grade is Distinction’. This is nonsense since we can not score marks greater than 100. Our algorithm would work better if it displayed an error message, like this.
Example 14. This algorithm handles abnormal data. As you will see, adding error control features to an algorithm makes it more complex.
1 | INPUT mark |
2 | CASE mark OF |
3 | 0 TO 49: grade ß ‘Fail’ |
4 | 50 TO 65: grade ß ‘Pass’ |
5 | 66 TO 74: grade ß ‘Credit’ |
6 | 75 TO 100: grade ß ‘Distinction’ |
7 | OTHERWISE grade ß ‘Mark Entry Error’ |
8 | END CASE |
9 | IF mark < 101 AND mark > -1 THEN |
10 | PRINT ‘Your grade is ‘, grade |
11 | ELSE |
12 | PRINT grade |
13 | END IF |
Line 9 uses the AND operator. The condition for the IF/THEN statement will only be true if the mark is less than 101 AND the mark is greater than -1
Test yourself: Q12. Complete this dry run table using the dataset {123}. It should output ‘Mark Entry Error’
Line | Mark | Grade | mark<101 | mark>-1 | Output |
1 | 123 |
|
|
|
|
7 |
|
|
|
|
|
9 |
|
| No | Yes |
|
12 |
|
|
|
|
|
Test yourself: Q13. Complete this dry run table using the data set {58}. It should output ‘Your grade is Pass’
Line | Mark | Grade | mark<101 | mark>-1 | Output |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A list of values is often stored using an array. If we wanted to sort a list of 100 club member names into alphabetical order it would be sensible to put the names into an array first. We would input the first name into Name(1), the second name into variable Name(2), the third name into Name(3) and so on until the last name is assigned to Name(100). The Name array can then be sorted and then printed.
Here are some examples where we would choose to create an array to store a list of values.
Example 15. Suppose we want to create an algorithm that stores 5 test scores in an array called TEST. The algorithm would look like this.
1 | INPUT TEST(1) |
2 | INPUT TEST(2) |
3 | INPUT TEST(3) |
4 | INPUT TEST(4) |
5 | INPUT TEST(5) |
How the algorithm works.
In our earlier algorithms we had statements like INPUT width, INPUT A, INPUT C and so on. Putting values into an array is very similar. When this statement is completed the first item in the TEST array will have a value. The number in brackets is called the index. The index identifies the position of an item in an array. For instance TEST(3) refers to the value that is third in the list called TEST
1 | INPUT TEST(1) |
After this line is completed the first item in the list called TEST will have a value.
2 | INPUT TEST(2) |
After this line is completed the second item in the list called TEST will have a value.
3 | INPUT TEST(3) |
After this line is completed the third item in the list called TEST will have a value.
Test yourself: Q14. What will happen after line 4 is completed?
……………………………………………………………………………………….
Example 16. Here is a dry run table for this algorithm using the dataset {45,64,74,89,90}
1 | INPUT TEST(1) |
2 | INPUT TEST(2) |
3 | INPUT TEST(3) |
4 | INPUT TEST(4) |
5 | INPUT TEST(5) |
Dry run table. Data set {45,64,74,89,90}
Line | TEST(1) | TEST(2) | TEST(3) | TEST(4) | TEST(5) |
1 | 45 |
|
|
|
|
2 |
| 64 |
|
|
|
3 |
|
| 74 |
|
|
4 |
|
|
| 89 |
|
5 |
|
|
|
| 90 |
Test yourself: Q15. How many columns would there be in the dry run table if input 30 test scores into array TEST? ……………
Test yourself: Q16. How many rows would there be in the dry run table if the array called TEST was to contain 50 test scores? ……………….
Test yourself: Q17. To create a phone book we might need to sort 30000 names into order. To solve this problem we would first store the names in an array. How many lines would there be in an algorithm to input the 30000 names? ………………
If you answered 30,000 for the last question then you are correct! However, fortunately, we do not have to create a 30,000 line because we can write algorithms using loops. The next section will show how we can make small algorithms that process thousands of statements!
Note
It is hard to make dry run tables for a large array. To show that our algorithm works we complete the following three steps.
1 Prove that an algorithm works for a small amount of data by creating a dry run table with for a small array.
2 Prove that a modified algorithm still works when the array has one more item added to the array.
3 Assume then that a similar algorithm will work for any number of items in the array.
In the last section we saw how we could fill up an array called TEST with values using INPUT statements. If we had 50 scores to enter into the TEST array then the algorithm would look like this.
1 | INPUT TEST(1) |
2 | INPUT TEST(2) |
3 | INPUT TEST(4) |
… |
|
… |
|
50 | INPUT TEST(50) |
This algorithm has 50 lines. It is time consuming to create a dry run table for this. Each line is nearly the same as the line before it. Only the index is different.
We can use a LOOP in our algorithm instead of a long list of statements that are nearly the same. The algorithm to input 50 numbers will now be only 5 lines long. An algorithm to input 30,000 names would also only be 5 lines long.
Test yourself. Q18. How many lines will there be in an algorithm to input 300,000 IC numbers into an array? ………………..
Here is the algorithm to put 50 scores into an array called TEST.
1 | Index ß 1 |
2 | DO WHILE Index ≠ 51 |
3 | INPUT TEST( Index ) |
4 | Index ß Index + 1 |
5 | END WHILE |
How the algorithm works.
1 | Index ß 1 |
This line is a simple assignment statement. The variable called Index is assigned the value 1. Index is a variable for the position of a value in our TEST array. We could of course use any variable name we wanted. It is easier to understand our algorithm if we think of identifiers that mean something to us.
2 | DO WHILE Index ≠ 51 |
This line is the start of our DO WHILE loop. Everything below this line and above the END WHILE line is “inside the loop.” Line 3 and Line 4 are inside the loop. Statements inside the loop are repeated many times. The part of line 2 that says Index ≠ 51 is the condition used to see if the loop is finished or not. In this example, if the condition Index ≠ 51 is true then loop statements have to be completed again. If the condition is not true then the loop statement is not carried out and the next line to be carried out will be the line immediately after the END WHILE statement.
3 | INPUT TEST( Index ) |
This line allows us to enter a new value into the TEST array. If Index =1 then the value we INPUT will be stored at position 1 in our list of test scores. If Index = 2 then the value we input will be stored at position 2 in our list of test scores.
4 | Index ß Index + 1 |
This is a very common type of assignment statement. It is a way of incrementing a value. After this statement is completed the value of Index would have been increased by 1. For example, if the value of Index is 23 before the line is completed, then the value of Index will be 24 after the line is completed.
5 | END WHILE |
The END WHILE statement is an end marker for the loop. It says where the end of the loop is located in the algorithm. The next statement carried out after an END WHILE is always the DO WHILE statement.
Suppose we have to make an algorithm to put only 5 numbers into an array called TEST. The algorithm could look like this.
1 | Index ß 1 |
2 | DO WHILE Index ≠ 6 |
3 | INPUT TEST( Index ) |
4 | Index ß Index + 1 |
5 | END WHILE |
Here is a dry run table for this algorithm using the data set {45,64,74,89,90}
Line | Index | Index ≠ 6 | TEST(1) | TEST(2) | TEST(3) | TEST(4) | TEST(5) |
1 | 1 |
|
|
|
|
|
|
2 |
| TRUE |
|
|
|
|
|
3 |
|
| 45 |
|
|
|
|
4 | 2 |
|
|
|
|
|
|
2 |
| TRUE |
|
|
|
|
|
3 |
|
|
| 64 |
|
|
|
4 | 3 |
|
|
|
|
|
|
2 |
| TRUE |
|
|
|
|
|
3 |
|
|
|
| 74 |
|
|
4 | 4 |
|
|
|
|
|
|
2 |
| TRUE |
|
|
|
|
|
3 |
|
|
|
|
| 89 |
|
4 | 5 |
|
|
|
|
|
|
2 |
| TRUE |
|
|
|
|
|
3 |
|
|
|
|
|
| 90 |
4 | 6 |
|
|
|
|
|
|
2 |
| FALSE |
|
|
|
|
|
Test yourself: Q19. Complete this dry run table using the dataset {34, 78, 87, 90, 67 }
Line | Index | Index ≠ 6 | TEST(1) | TEST(2) | TEST(3) | TEST(4) | TEST(5) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
We can easily change this algorithm so that it can fill the array called TEST no matter how many scores are to be entered. We could modify the algorithm to input 400 test scores by changing line 2 to DO WHILE Index ≠ 401
The complete algorithm will look like this.
1 | Index ß 1 |
2 | DO WHILE Index ≠ 401 |
3 | INPUT TEST( Index ) |
4 | Index ß Index + 1 |
5 | END WHILE |
Test yourself: Q20. Write down a new version of line 2 that modifies the algorithm so that it will add 123 values to array TEST
2 |
|
Test yourself: Q21. Make an algorithm that can be used to input three words into an array called COLOURS. Make a dry run of your algorithm using the data set {‘Blue’, ‘Green’,’Yellow’}
Algorithm
|
|
|
|
|
|
|
|
|
|
Dry run table with data set {‘Blue’, ‘Green’, ‘Yellow’}
Line | Index |
|
| COLOUR(2) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Important Note: Words with quotes around them are called literals. Literals are used in the expression part of assignment statements.
A statement like COLOUR(3) ß ‘Yellow’ is good R
This statement says assign the word Yellow to the list of words called COLOUR. The word is assigned to position 3 in the list.
A statement like COLOUR(3) ß Yellow is bad – it does not assign Yellow to COLOUR (3) as we might have intended. Q
In this statement Yellow must be an identifier – since it is not an alphanumeric literal. COLOUR(3) will be given the value of the variable Yellow – whatever that is!!!.
Example 17:
What is the output for this algorithm?
1 | Index ß 3 |
2 | Yellow ß ‘Purple’ |
3 | COLOUR(Index) ß Yellow |
4 | PRINT COLOUR(Index) |
This is a confusing algorithm. But it is useful because it shows how we must be careful when using literals and careful when naming identifiers. Let us work through this algorithm one line at a time to see what it does.
1 | Index ß 3 |
This is a simple assignment statement. A memory variable called Index receives the numeric literal value 3. If we were to PRINT Index after this line is completed then the output would be 3. The dry run table will look like this.
Line | Index | Yellow | COLOUR(Index) | Output |
1 | 3 |
|
|
|
2 |
|
|
|
|
3 |
|
|
|
|
4 |
|
|
|
|
2 | Yellow ß ‘Purple’ |
This is also a simple assignment statement. A memory variable called Yellow receives the alphanumeric literal value ‘Purple’. If we were to PRINT Yellow after this line is completed then the output would be Purple. This is an example of how NOT to write
algorithms – it is confusing! Yellow is a poor choice for an identifier. The dry run table will now look like this.
Line | Index | Yellow | COLOUR(Index) | Output |
1 | 3 |
|
|
|
2 |
| Purple |
|
|
3 |
|
|
|
|
4 |
|
|
|
|
3 | COLOUR(Index) ß Yellow |
We process line 3 by firstly replacing any variables in it with the values of the variables.
We replace Index with its value 3 and Yellow with its value ‘Purple’.
The line then becomes the simple assignment statement COLOUR(3) ß ‘Purple’.
Remember. To complete a line that contains variables we must replace any identifiers in the expression with values.
COLOUR(Index) ß Yellow becomes COLOUR(3) ß ‘Purple’
COLOUR(3) ß ‘Purple’ is easy for us to understand and easy to put into a dry run table.
Line | Index | Yellow | COLOUR(Index) | Output |
1 | 3 |
|
|
|
2 |
| Purple |
|
|
3 |
|
| Purple |
|
4 |
|
|
|
|
4 | PRINT COLOUR(Index) |
This line contains a variable called Index. We must replace the identifier Index with its value. The line then becomes PRINT COLOUR(3). This is easy to put into a line of a dry run table. We simply look at what is in the COLOUR(3) table and copy the value we find into the OUTPUT column.
Line | Index | Yellow | COLOUR(Index) | Output |
1 | 3 |
|
|
|
2 |
| Purple |
|
|
3 |
|
| Purple |
|
4 |
|
|
| Purple |
There are two more ways we can create loops in an algorithm.
Example 18 Using a REPEAT loop.
This algorithm will input 50 scores into an array called TEST.
1 | Index ß 1 |
2 | REPEAT |
3 | INPUT TEST( Index ) |
4 | Index ß Index + 1 |
5 | UNTIL Index = 51 |
Example 19. Suppose we have to make an algorithm that will test an ATM card PIN until the entered number is correct. The user is allowed to have no more than three attempts at the entering the PIN. If the correct PIN is entered the algorithm will output the message “Welcome to HSBK”. If the user does not enter the correct password after three tries then the algorithm will output “Sorry, your card has been withheld”.
1 | PIN ß 34576 |
2 | Attempt ß 0 |
3 | AccessOK ß FALSE |
4 | REPEAT |
5 | Attempt ß Attempt + 1 |
6 | INPUT CustomerPIN |
7 | IF PIN = CustomerPIN THEN |
8 | OUTPUT ‘Welcome to HSBK’ |
9 | AccessOK ß TRUE |
10 | Attempt ß 3 |
11 | END IF |
12 | UNTIL Attempt = 3 |
13 | IF AccessOK = FALSE THEN |
14 | DISPLAY ‘Sorry, your card has been withheld’ |
15 | END IF |
|
|
We use REPEAT … UNTIL loops when we are sure that the loop is going to be completed at least once. In the PIN algorithm we get customer input inside the loop. It will always be the case that the customer enters his PIN at least once.
In this algorithm we have used a Boolean variable called AccessOK. Boolean variables can only have values TRUE or FALSE.
Here is the dry run table for this algorithm using the dataset {12345, 34576, 43212}.
line | PIN | Attempt | AccessOK | CustomerPIN | PIN = CustomerPIN | AccessOK = FALSE | Attempt = 3 | OUTPUT |
1 | 34576 |
|
|
|
|
|
|
|
2 |
| 0 |
|
|
|
|
|
|
3 |
|
| FALSE |
|
|
|
|
|
5 |
| 1 |
|
|
|
|
|
|
6 |
|
|
| 34576 |
|
|
|
|
7 |
|
|
|
| FALSE |
|
|
|
12 |
|
|
|
|
|
| FALSE |
|
5 |
| 2 |
|
|
|
|
|
|
6 |
|
|
| 34576 |
|
|
|
|
7 |
|
|
|
| TRUE |
|
|
|
8 |
|
|
|
|
|
|
| Welcome to HSBK |
9 |
|
| TRUE |
|
|
|
|
|
10 |
| 3 |
|
|
|
|
|
|
12 |
|
|
|
|
|
| TRUE |
|
13 |
|
|
|
|
| FALSE |
|
|
Test yourself. Q22 Make a dry run table using the dataset {3523, 3, 897, 3434}.
line | PIN | Attempt | AccessOK | CustomerPIN | PIN = CustomerPIN | AccessOK = FALSE | Attempt = 3 | OUTPUT |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
FOR … NEXT loops
These loops are used if the number of times a loop will be completed is clearly known. FOR … NEXT loops are useful because they are easier to understand than the equivalent REPEAT or DO WHILE loops.
Here is an algorithm from earlier in this book. This algorithm uses a DO WHILE loop.
1 | Index ß 1 |
2 | DO WHILE Index ≠ 401 |
3 | INPUT TEST( Index ) |
4 | Index ß Index + 1 |
5 | END WHILE |
Here is the equivalent algorithm using a FOR NEXT loop.
1 | FOR Index 1 (1) 400 |
3 | INPUT TEST( Index ) |
4 | NEXT Index |
How the algorithm works.
1 | FOR Index 1 (1) 400 |
3 | INPUT TEST( Index ) |
4 | NEXT Index |
The first line says
“Do the loop statements starting with Index = 1 and continuing until Index = 400. Each time the loop is carried out increase Index by (1).”
1 | FOR Index 1 (1) 400 |
3 | INPUT TEST( Index ) |
4 | NEXT Index |
This is the only step inside the loop. A value is input into the Array called TEST. For instance, if Index = 89 then a value for TEST(89) created after this statement is completed.
1 | FOR Index (1) 400 |
3 | INPUT TEST( Index ) |
4 | NEXT Index |
This last line defines where the end of the FOR … NEXT loop. It increments the value of Index. The next line to be completed after this line would be line 1.
So far we have been able to create some pretty difficult sort of algorithms that can each do one single thing. In reality it is likely that we will need to make algorithms that can do a number of things.
Example 20
Suppose we must INPUT 5 scores into an array and then display the highest score. The algorithm could look like this.
1 | FOR Index = 1 (1) 5 |
2 | INPUT TEST( Index ) |
3 | NEXT Index |
4 | Biggest ß TEST(1) |
5 | FOR Index = 2 (1) 5 |
6 | IF TEST(Index) > Biggest THEN |
7 | Biggest ß TEST(Index) |
8 | END IF |
9 | NEXT Index |
10 | OUTPUT ‘The highest score is ‘, Biggest |
The algorithm has been colour coded so that it is easy to see the different parts of it.
Test yourself. Q23. Complete the dry run table for this algorithm using the dataset {77, 45, 67, 59, 58}
Line | Index | Test(1) | Test(2) | Test(3) | Test(4) | Test(5) | Test(Index) >Biggest | Output |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Notice that the algorithm has three separate parts.
1 | FOR Index 1 (1) 5 |
3 | INPUT TEST( Index ) |
4 | NEXT Index |
5 | Biggest ß TEST(1) |
6 | FOR Index 2 (1) 5 |
7 | IF TEST(Index) < Biggest THEN |
8 | Biggest ß TEST(Index) |
9 | END IF |
10 | NEXT Index |
11 | OUTPUT ‘The highest score is ‘, Biggest |
Well, that is it! You now have the skills you need to build algorithms. What you need to do now is practice.
This section provides some examples of algorithms that are very common in Computer Studies.
Example 21
Display the total of 10 numbers.
1 | Nß10 |
2 | FOR J = 1 (1) N |
3 | INPUT Number( J ) |
4 | NEXT J |
5 | Total = Number(1) |
6 | FOR P = 2 (1) N |
7 | Total ß Total + Number(P) |
8 | Next P |
9 | Display ‘The total is’ , Total |
Example 22
Display the total of 1000 numbers
1 | N=1000 |
2 | FOR Index 1 (1) N |
3 | INPUT Number( Index ) |
4 | NEXT Index |
5 | Total = Number(1) |
6 | FOR Index 2 (1) N |
7 | Total ß Total + Number(Index) |
8 | Next Index |
9 | Display ‘The total is’ , Total |
Example 23
Display the total of 13 items on a receipt produced by an EPOS terminal
1 | Nß13 |
2 | FOR Ctr = 1 (1) N |
3 | INPUT Receipt(Ctr ) |
4 | NEXT Ctr |
5 | Total = Receipt(1) |
6 | FOR Ctr 2 (1) N |
7 | Total ß Total + Receipt(Ctr) |
8 | Next Ctr |
9 | Display ‘The receipt total is’ , Total |
Example 24
Display the maximum of 5 numbers
1 | Nß5 |
2 | FOR Index 1 (1) N |
3 | INPUT Number( Index ) |
4 | NEXT Index |
5 | MaxNumber = Number(1) |
6 | FOR Index 2 (1) N |
7 | IF Number(Index) > MaxNumber THEN |
8 | MaxNumber ß Number(Index) |
9 | End IF |
8 | Next Index |
9 | Display ‘The maximum value is ’ , MaxNumber |
Example 25
Display the minimum of 5 numbers
1 | Nß5 |
2 | FOR Index 1 (1) N |
3 | INPUT Number( Index ) |
4 | NEXT Index |
5 | MinNumber = Number(1) |
6 | FOR Index 2 (1) N |
7 | IF Number(Index) < MinNumber THEN |
8 | MinNumber ß Number(Index) |
9 | End IF |
8 | Next Index |
9 | Display ‘The minimum value is ’ , MinNumber |
Example 26
Display the maximum, minimum, total and the average of 4 numbers.
1 | Nß4 |
2 | FOR Index 1 (1) N |
3 | INPUT Number( Index ) |
4 | NEXT Index |
5 | MaxNumber = Number(1) |
6 | FOR Index 2 (1) N |
7 | IF Number(Index) > MaxNumber THEN |
8 | MaxNumber ß Number(Index) |
9 | End IF |
10 | Next Index |
11 | MinNumber ß Number(1) |
12 | FOR Index 2 (1) N |
13 | IF Number(Index) < MinNumber THEN |
14 | MinNumber ß Number(Index) |
15 | End IF |
16 | Next Index |
17 | Total = Number(1) |
18 | FOR Index 2 (1) N |
19 | Total ß Total + Number(Index) |
20 | Next Index |
21 | Average ß Total / N |
22 | Display ‘The maximum value is ’ , MaxNumber |
23 | Display ‘The minimum value is ’ , MinNumber |
24 | Display ‘The total is’ , Total |
25 | Display ‘The average is ’ , Average |
How Example 26 works…
This algorithm is made up of 6 separate parts. Each part of the algorithm performs one task . The tasks performed by the algorithm are:
· Input the 4 numbers
· Calculate the Maximum value
· Calculate the Minimum value
· Calculate the Total
· Calculate the Average
· Display Maximum, Minimum, Total and Average
If an algorithm does one thing only then we say the algorithm has strong cohesion. This is a good thing. We want to make sure that our algorithms do only one thing at a time as this makes them easier to understand.
Example 27
Display the maximum, minimum, total and the average of 4 numbers.
1 | Nß4 |
2 | INPUT Number(1) |
3 | MaxNumber ß Number(1) |
4 | MinNumber ß Number(1) |
5 | Total ß Number(1) |
6 | FOR Index 2 (1) N |
7 | INPUT Number( Index ) |
8 | IF Number(Index) > MaxNumber THEN |
9 | MaxNumber ß Number(Index) |
10 | End IF |
11 | IF Number(Index) < MinNumber THEN |
12 | MinNumber ß Number(Index) |
13 | End IF |
14 | Total ß Total + Number(Index) |
15 | Next Index |
16 | Average ßTotal / N |
17 | Display ‘The maximum value is ’ , MaxNumber |
18 | Display ‘The minimum value is ’ , MinNumber |
19 | Display ‘The total is’ , Total |
20 | Display ‘The average is ’ , Average |
Example 27 has poor cohesion. The algorithm is shorter than Example 26, but it is more difficult to understand. Finding errors in this algorithm is more difficult than necessary because of the poor cohesion.
Example 26 and Example 27 solve the same problem. Both algorithms work. However, Example 26 is “better” since the single large problem has been nicely divided into 6 smaller parts, each of which is easy to understand.