Home Up


Chapter 6:  Algorithms

 An extract from my textbook...

Objectives of this chapter

ü    Create clear, easily understood algorithms.

ü    Apply the principal of strong cohesion.

ü    Create a dry run table to test an algorithm.

 

 

What is 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. 

6.1 A sequence of steps

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 statementsAlgorithm 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

 

Assignment statements

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?    ___________

6.2 INPUT statements

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 yourselfQ3.  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 yourselfQ4.  .  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 yourselfQ5.    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.

 

Dry Run tables for algorithms that use INPUT statements

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

……………………………………………………………………………….
……………………………………………………………………………….

 

6.4 Formatting output

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

6.5 Selection Statements

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 yourselfQ7.  :  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 yourselfQ9.    Complete this dry run table using the data set {22}.

 

Line

TestMark

TestMark >49

Grade

Output

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Case Statements

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 yourselfQ10.    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 yourselfQ11.    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 yourselfQ12.  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 yourselfQ13Complete this dry run table using the data set {58}.  It should output ‘Your grade is Pass’

 

Line

Mark

Grade

mark<101

mark>-1

Output

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6.6  Arrays

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 15Suppose 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 yourselfQ14.   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 yourselfQ15.  How many columns would there be in the dry run table if input 30 test scores into array TEST?  ……………

Test yourselfQ16How many rows would there be in the dry run table if the array called TEST was to contain 50 test scores?  ……………….

Test yourselfQ17. 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.

 

6.7 Making Loops

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 yourselfQ19.  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 yourselfQ20.  Write down a new version of line 2 that modifies the algorithm so that it will add 123 values to array TEST

 

2

 

 

 

Test yourselfQ21. 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

 

More ways to loop.

There are two more ways we can create loops in an algorithm. 

  1. REPEAT .. UNTIL <condition>
  2. FOR  j(k)m .. NEXT  j

 

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.

 

Combination problems

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. The first part of the algorithm inputs numbers into an array

1

FOR Index 1 (1) 5

3

     INPUT TEST( Index )

4

NEXT Index 

 

  1. The second part gets the value of the highest score

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

 

  1. The third part outputs the answer

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. 

 


 Dictionary Acronyms News Search Links