Reading: Identify algorithm structures
Identify algorithm structures
Inside this resource
What is an algorithm?
Features of a good algorithm
Expressing algorithms
Typical computer operations
Accepting inputs
Producing outputs
Assigning values to variables
Performing arithmetic
Perform alternative actions
Repeating operations
Sequence, selection and iteration
Structured programming
Nesting IF constructs
Designing algorithms
Algorithm pre-conditions
Summary
What is an algorithm?
Let’s begin by thinking of an algorithm as a recipe. A recipe defines how to take a set of ingredients, apply a variety of processes to those ingredients (in a prescribed order) to produce a finished product.
A recipe will include instructions on how to prepare the ingredients, which ingredients to mix together into which containers, how to cook the ingredients, at what temperature to cook them, how long to cook them and what to do once they are cooked.
Features of a good algorithm
Algorithms must be precise and unambiguous
This will enable the programmer to code the algorithm into instructions for a computer without having to guess what should be done by the program. An algorithm should describe all of the essential features of the solution.
An algorithm is a correct description of the solution to a problem
This statement essentially tells us two things. Firstly, we have a problem. It is vital that we understand the problem before we start describing a solution with our algorithm. There is little value to writing an algorithm that is based on a poorly understood problem. Any program written from that algorithm will fail to solve the problem. Secondly, we must describe the solution correctly with our algorithm. We may be able to arrive at the best possible solution to a problem, but if we fail to represent that solution correctly in our algorithm, any programs written from it will not work as we had planned. There is little point writing code from an algorithm that does not represent the solution correctly.
Programs should deal gracefully with errors
A program should not ‘die’ or ‘hang’ because of errors such as not finding a file, or the user entering the letter ‘A’ rather than the number ‘1’. Your program should include a course of action for all possible situations. For example, if the user tries to open a file which does not exist, a good program might give an error message, and then offer to create a new file.
An algorithm might only specify the essential features of a solution, and not the details of error handling. It will then be up to the programmer to enhance the algorithm accordingly.
Useful algorithms are guaranteed to end
Some algorithms may give a solution to a problem in theory, but in practice will fail to produce a solution in a reasonable time. In extreme cases, the algorithm may take an infinite amount of time to produce a result. If we write a program that cannot end (because it was based on an algorithm that did not end) and run that program on our computer, the only way to stop the program would be to terminate the program.
The most common cause of a program not ending is an error (a ‘bug’) in either the algorithm or the program that produces an infinite loop.
There are some special cases where a program is purposely designed not to end, typically where the program is controlling an external device or system (for example a mobile phone, or an aircraft flight-control system).
Algorithms should be efficient
Efficiency can be measured in terms of amount of memory used, the number of operations performed, the frequency of input/output operations and so on. An efficient algorithm will consume less of the computer’s resources than an inefficient algorithm.
Computer programs should be user friendly
Programs should offer some information and feedback to the operator and should be written with the user in mind. A computer program that is not user friendly will not find many users, and may greatly aggravate those required to use it. Issues include what prompts should be used, window layout, menu design, how information is presented and so on.
Expressing algorithms
Described below are three common ways to express the structure of an algorithm:
1Pseudocode
2Flowcharts
3Nassi-Schneidermann diagrams.
Pseudocode
Pseudocode is structured English used for describing algorithms. The purpose of pseudocode is to provide a means of specifying algorithms that is independent of any particular programming language. It allows the program designer to focus on the logic of the algorithm without the distraction of programming language rules.
Pseudocode should be:
- Precise — the writer and all subsequent readers will understand exactly what is required to be done.
- Concise — pseudocode removes the necessity for verbose, essay-like instructions containing vague or ambiguous language.
- language independent — the programmer is free to implement an algorithm in the syntax of any chosen procedural programming language (the ‘target’ language).
There is a wide variation in pseudocode syntax, but the main thing is that the meaning is readily understood and unambiguous. Organisations that use pseudocode often develop an in-house standard which defines the structure, constructs and keywords that may be used by their designers.
Here are some keywords commonly used in pseudocode to indicate input, output, and processing operations:
Pseudocode key word / IndicatesInput / GET, READ, OBTAIN, ACCEPT
Output / PRINT, DISPLAY, SHOW
Initialise / SET, ASSIGN, INIT
Add one / INCREMENT
Misc / FIND, SEARCH, SELECT, SORT
Here is a simple example of pseudocode that represents what we might do on Saturday morning:
Wake Up
Perform morning things
IF it is raining THEN
Watch TV
ELSE
Play golf
ENDIF
Get ready for lunch
Flowcharts
Flowcharts are a diagrammatic method used to represent processes. The basic symbols used in flowcharts will be introduced as we explore how to represent the three basic algorithmic constructs of sequence, selection and iteration.
Figure 1: Flowchart example: Saturday morning
Nassi-Schneiderman diagrams
These diagrams are similar to flowcharts, but have the advantage of enforcing a particular structure in the program. They can become difficult to draw when the algorithm includes a lot of nested constructs. We will not be using Nassi-Schneidermann diagrams.
Figure 2: Nassi-Schneidermann diagram example—Saturday Morning
Typical computer operations
One way to think about what computers do is the ‘Input-Process-Output’ model. This simple model says that computers perform three basic types of operations:
1They take inputs from a variety of different sources.
2They process these inputs in a variety of ways.
3They output the results of the processing to a variety of different devices.
Accepting inputs
Inputs may come from a variety of sources, such as, keystrokes from a keyboard, a mouse action, a file stored in the computer, sounds from a microphone and numerous others. An example is shown below, where the user is prompted for their surname, and the computer reads it into a variable.
English-like statements / Example programming instructionsPrompt user for surname
Input surname / surname = raw_input('Enter your Surname')
Producing outputs
Outputs may be a file to be stored on disk, information to display on a screen, information to be printed, sounds to be sent to speakers etc. In the example below, the text ‘Hello World’ will be sent to the output device (eg a computer screen).
English-like statements / Example programming instructionsPrint the message Hello World / print 'Hello World'
Assigning values to variables
A computer is able to store data values like numbers and text in memory. Programming languages allow you to access memory using named variables.
For example, the statement:
x = 6
places the number 6 into a variable called x. The variable x will (when the program executes) be a location in the computer’s memory. Thankfully, you don’t need to worry about where the number is stored, or how it is represented — you only need to perform processing with the variable. As the name suggests, the actual data stored in a variable may change during the execution of a program or script.
Variables can store numbers or text. The basic data types are numbers and text.
- Numbers can be whole numbers (called integers) such as 2, 27 and 139 or real numbers (numbers that contain an integer and a fraction shown as one or more decimal places) for example 12.3 and 0.0027.
- Text can be single characters such as ‘A’, ‘g’, ‘Y’ or a string of characters such as ‘Hello World’.
In the example below, the variable called ‘total’ is set to zero; this is a way of telling the computer to store the value 0 in the memory location or variable called total.
English-like statements / Example programming instructionsSet the total to 0 / total = 0
The name you give to a variable may refer to a storage location that is only one byte in size or a location that is many bytes in size. You should always use meaningful names for variables in algorithms to improve the readability of the algorithm and its resulting program. This is particularly important in large and complex programs.
Performing arithmetic
Computers can perform the arithmetic operations of adding, multiplying, dividing, subtracting and exponentiation. An example is the following statement which is a way of telling the computer to multiply the number of items and the price, placing the result into the variable called total.
English-like statements / Example programming instructionsset total to items times price / total = items * price
Perform alternative actions
Computers can compare the values stored in memory and execute different instructions depending on the result of the comparison. This action is referred to as selection — that is, selecting different courses of action depending upon some condition. An example is the following statement which is a way of telling the computer to make the decision to print either the word Pass or the word Fail depending on whether the value stored in the variable called mark is greater than 49.
English-like statements / Example programming instructionsIF mark is greater than 49 THEN
print Pass
ELSE
print Fail / if mark > 49:
print 'Pass'
else:
print 'Fail'
Repeating operations
Computers can execute the same set of instructions over and over again. This is commonly referred to as iteration, repetition or looping. There are several types of iteration that can be used depending on what you want the computer to do. A loop can be constructed to execute the same set of instructions for a certain number of times or to execute the set of instructions while a condition is true. For example, while the total stays above 0 the computer is to continuously subtract the new purchase amount from the total.
English-like statements / Example programming instructionsWHILE total greater than 0
subtract new purchase from total
ENDWHILE / while(total > 0):
total = total – new_purchase
Sequence, selection and iteration
These constructs are used to control the flow of program execution and provide a means for precisely specifying which instruction will be performed at any given time during the execution of the program. Let’s look at how these constructs are used to create pseudocode and flowcharts.
Sequence
Sequence is where one task is performed sequentially after another.
In pseudocode, each task is on a separate line and has the same indentation as the other tasks in the sequence. The tasks are executed one after the other beginning with the task at the top of the sequence and ending with the task at the bottom of the sequence.
In a flowchart, the symbol representing a task in the sequence is a rectangle. Typically, tasks are executed from the top task to bottom task. To ensure that the correct order of tasks is followed in a sequence of tasks, a line with an arrow at one end indicates the flow of tasks through a sequence. An oval is often used to indicate the start and end of the flowchart.
Here are some examples of sequences written in pseudocode and drawn in a flowchart.
Sequence example 1: Feeding the cat
Pseudocode: / Flowchart:Get cat food out of cupboard
Get cat food bowl
Put cat food into bowl
Place bowl on ground
Call cat /
Sequence example 2: Adding two numbers
The following example is a simple problem that a computer can solve, rather than a general process from everyday life.
Pseudocode: / Flowchart:PROMPT 'Enter value for x:'
READ x
PROMPT 'Enter value for y:'
READ y
SET result = x + y
DISPLAY result /
Selection
This is where a choice is made between alternative courses of action. Selection is also known as ‘branching’. In pseudocode, selection is represented by the IF-THEN-ELSE construct. The simplest form is shown below.
Pseudocode: / Flowchart:IF condition THEN
<block>
ENDIF /
Selection example 1: Feeding the cat
Pseudocode: / Flowchart:IF cat bowl empty THEN
Feed cat
ENDIF /
The condition is an expression that will either be true or false. This expression is usually the result of a comparison operation.
For example, the condition:
hoursWorked > 40
compares the value of the variable hoursWorked to the constant value 40. If hoursWorked has a value of, say, 70 then this condition will be TRUE, because 70 is indeed greater than 40. If hoursWorked contains the value 30 then of course the condition will be FALSE. If hoursWorked contains the value 40 then the condition is also FALSE.
Here are some more examples of conditions using each of the comparison operators:
Condition / Meaningx == 3 / x is equal to 3
y != 0 / y is not equal to 0
cashEarned > cashSpent / cashEarned is greater than cashSpent
temperature < 100 / temperature is less than 100
count <= 10 / count is less than or equal to 10
pressure >= 1500 / pressure is greater than or equal to 1500
IF condition THEN
(sequence 1)
ELSE
(sequence 2)
ENDIF /
If the condition is true, sequence 1 is performed; otherwise, sequence 2 is performed.
Note 1: You do not need the ELSE part. The ELSE keyword and ‘sequence 2’ are optional.
Note 2: Notice that the sequences for the IF and the ELSE part are indented the same amount. As mentioned earlier, this ‘style’ is very common and allows you to see the logic of the algorithm more easily. A very good programming habit to adopt is to decide upon a standard style and stick to it when writing algorithms.
Selection is represented in flowcharts using the diamond symbol as shown below:
Selection example 2: Overtime due?
Pseudocode: / Flowchart:IF hours > 40 THEN
Calculate Overtime
ENDIF /
Pseudocode: / Flowchart:
IF condition THEN
(Block 1)
ELSE
(Block 2)
ENDIF /
Selection example 3: Feeding the cat
Pseudocode: / Flowchart:IF cat bowl empty THEN
Feed cat
ELSE
Point cat at bowl
ENDIF /
Selection example 4: Pass or fail?
Pseudocode: / Flowchart:IF test mark > 50 THEN
DISPLAY 'pass'
ELSE
DISPLAY 'fail'
ENDIF /
In the example above, note that ‘fail’ is displayed if the test mark equals 50.
In Selection example 1 and Selection example 2, at least one action is performed. In example 2, it doesn’t matter what the actual test mark is a message will be displayed. The test mark simply determines which alternative message is displayed.
There may be times we want something done when a condition is met but don’t want anything done if the condition is not met. This action is performed by the following construct:
IF condition THEN
<block>
ENDIF
Iteration
Iteration is the process of repetition, also known as ‘looping’. Iteration allows a program to do something again and again, or perform similar operations on multiple items. Here is a simple loop that ‘counts’ from one to ten:
SET count = 1
WHILE count <= 10 DO
DISPLAY count
count = count + 1
ENDWHILE
DISPLAY 'bang!'
The important things to note are:
- This code will display 1 2 3 4 5 6 7 8 9 10 bang!
- When the end of the loop is reached, the algorithm jumps back to the start again.
- There is a loop variable, (called ‘count’ in this case) that changes with each cycle of the loop. For this example, the count variable is simply incremented (increased by 1) at the end of the loop.
- The loop condition determines when the loop will end (or alternatively, when it will keep going!). In this case, the condition is 'count <= 10', and the loop will be entered (or continue) when this condition is true.
- When count reaches 11, this condition becomes false, and so the loop is exited. The next statement to be executed will be the one immediately after the loop.
Here’s another example. Suppose you have developed an algorithm to compute the pay of an individual worker, taking into account the hours worked, and the hourly rate of pay. The calculation might look like this:
SET pay = hoursWorked * hourlyRate
WRITE pay
But now, what if you want to compute the pays of all workers in the company? You can do this by wrapping a loop around the original algorithm, something like this:
FOR EACH worker DO
SET worker.pay = worker.hoursWorked * hourlyRate
WRITE pay
ENDFOR
Now the same calculation is repeated for each worker. The notation ‘worker.pay’ means the pay for that particular worker.
Types of loops
Most computer languages provide three types of looping statement, which are the:
1Pre-test loop — also known as the WHILE loop
2Post-test loop — eg the REPEAT/UNTIL or DO/WHILE loops
3Counting loop — also known as the FOR loop.
In fact, we can get by with only the WHILE loop, but these other loops help to make our code simpler and our intentions clearer.
There are several things you need to consider when deciding upon the best way to construct loops. What conditions should exist for entry into a loop? Do you want to execute the loop instructions for a particular number of times? If you control a loop based upon some condition being true, how will you modify the condition so that it becomes false (so the loop can stop)? Answering these questions will assist in selecting the most appropriate loop for the problem you are solving.
There are a few different types of loops, however, all loops can be described using the WHILE loop. The WHILE loop executes the instructions inside the loop if some condition(s) is true and continues executing the instructions whilst the condition(s) remain true.
The REPEAT/DO loops will execute a block of instructions at least once before testing the condition(s) to see if it executes the same block of instructions again.