ALGORITHM DESIGN
AND
PROBLEM SOLVING
Algorithm
is a sequence of well-defined steps that are followed when solving a particular problem.
for example finding the shortest route between Bulawayo and Mutare.
It is a step by step procedure of solving a specified problem.
An algorithm can be created to sort a list of student names in alphabetic order.
A good algorithm should be:
Well-ordered and thus easy to follow
Should have a finite number of statements
It should not tolerate any form of ambiguity (statements with more
than one meaning)
A recipe is a very good example of an algorithm.
Before writing an algorithm, one must first of all understand the problem that needs to be
solved, otherwise you solution might not solve the problem at hand.
Algorithms are not necessarily written in any programming language but can be in form of
Descriptions
Pseudocode
Flowcharts
structure diagrams
or even the actual program code.
Purpose of an algorithm
Algorithms are used to express the structure of a program before it is coded.
It is used to make a draft of a program and to present the logic of a program before coding.
150
Algorithms can be run using a trace table/dry run table in order to determine the logic of a
program.
Characteristics of an algorithm
Finiteness: the algorithm should stop at a certain point when the instructions are executed.
Input: It should also have a finite number of inputs, if they exist.
Output: the algorithm should produce some form of output.
Precise: Should be precise on what is supposed to be done and thus no ambiguity. Statements in it
must only have one meaning.
Termination point: Should have a termination point / stop point
Advantages of algorithms
It is independent of any programming language thereby flexible to write
easy to convert to a program code or flowchart
easy to determine logic errors
has finite steps which lead to a solution
Disadvantages of algorithms
time consuming to design, for example, first converting to flowchart, then to program code
most people find them difficult to learn
Control structures/Flow control/Programming Constructs
Each computer program is made up of several instructions which are executed individually by the
computer.
Control structures, also called programming constructs, define the order in which these
instructions are executed.
the basic control structures are:
Sequence,
Selection and
Iteration (looping/repetition).
In this chapter will concentrate on the sequence structure only.
151
Sequence/Linear Structure
is a control structure in which instructions are executed one after the other in the order given, without
skipping or repeating any one of them.
The general form of a linear structure is as shown below:
Sequence Structure
Statement 1 will be executed, followed, by statement 2 and lastly statement 3.
Each instruction is run only once.
For example, the following program accepts 2 numbers entered through the keyboard, adds them
and display the total on the screen
1. Total = 0
2. Enter first number, first
3. Enter second number, second
4. Total = first + second
5. Display Total
6. End
When running the above program, the computer will first execute instruction 1, followed by
instruction 2, then instruction 3, instruction 4 and lastly instruction 5, in the order given in the
program.
Like what have been said earlier, no instruction is skipped or repeated.
Each instruction is executed once and only once.
It can be realised that the program above has 4 main sections; namely
152
Initialisation stage: Line 1: Total =0
Initialising involves giving starting values to variables.
This is done to clear memory of the computer so that correct values will be calculated.
NB: Only those variables whose values are to be calculated are initialised.
Input of values: Line 2 and Line 3
This is whereby data is entered in the computer through the keyboard
Processing: Line 4: Total = first + second
This is whereby calculations are performed on data entered.
Output: Line 5: This involves displaying of calculated values on the screen
Advantages of linear structure
structure is very simple to follow
It does not have any confusion.
It is not complicated and therefore ideal for very short programs. However, real-life programs
do not always follow a linear structure.
Algorithm Tools
The basic tools that are used in writing algorithms are:
Descriptions
Pseudocodes
Flowcharts
Structure diagrams
153
DESCRIPTION
These are general statements that are followed in order to complete a specific task.
They are not governed by any programming language.
An example:
Using description, write a program that accept student marks entered through the keyboard for the
following subjects, Shona, Ndebele, Computers and English.
The program then calculates the average mark and displays the average mark on the screen.
The descrption result will be as follows:
Enter student marks, for Shona, Ndebele, Computers and English
Calculate the Average of the marks
Print the Average Mark End the program.
PSEUDOCODE
A pseudocode is a set of English-like statements, closer to programming language that indicates
steps followed in performing a specific task.
Pseudocodes are also independent of any programming language.
For example:
Write a program that accept student marks entered through the keyboard for the following
subjects, Shona, Ndebele, Computers and English.
The program then calculates the average mark and displays the average mark on the screen.
The answer will be as follows:
SUM, AVERAGE = 0 (SUM and AVERAGE have values 0. is can also be written in separate lines) eg SUM = 0
AVERAGE = 0
INPUT Student Mark obtained in Shona, S
INPUT Student Mark obtained in Ndebele, N
INPUT Student Mark obtained in Computers, C
INPUT Student Mark obtained in English, E
SUM = S + N +C + E
AVERAGE = SUM/4
PRINT AVERAGE
End
154
From the program above, INPUT tells us that the user must enter a value required in that statement.
INPUT can also be replaced by ENTER.
On the other hand, S, N, C, E, AVERAGE and SUM are called variables.
A variable is a named memory location that will store a value when the program is running.
In this instance, S will store the Shona mark, N will store the Ndebele mark, C will store the Computers
mark and E will store the English mark.
The statement SUM = S + N +C + E means that, SUM is a memory location which will store
that value obtained after adding values in memory locations S, N, C and E.
The computer will search the stated memory locations and take the values stored there for
computations.
Likewise, AVERAGE = SUM/4, means that the computer will take the value stored in memory
location SUM and then divide it by 4.
The answer will be stored in memory location called AVERAGE.
This implies that one needs to specify memory locations for values and use those memory
locations
When carrying out computations.
PRINT (or DISPLAY) allows a value or data to be displayed on the screen.
So, the statement, PRINT AVERAGE, means that the computer will look for the value in
memory location AVERAGE and display it on the screen.
If the value of AVERAGE = 20 then:
PRINT AVERAGE will display 20 on the screen.
However, PRINT “AVERAGE”, in quotes, will display the word AVERAGE on the screen.
This is so because everything in quotes is displayed as it is in the quotes, even if it has wrong
spellings.
The END statement tells the computer that the program should stop running.
Because this is a pseudocode, no one is penalised for any grammar used, as long as it is easy and
clear what needs to be done by each statement.
Advantages of pseudocode
They are not written in any programming language and therefore easy to understand.
It is easier to develop a program from pseudocode than a flowchart
155
It is very easy to convert a pseudocode into any programming language
Pseudocodes are usually very short in their codes
Disadvantages of pseudocodes
They waste programming time since they need to be converted to an actual program code
later on.
One needs to be good in writing pseudocodes so that actual programming becomes easy.
Flowcharts
A flowchart is a diagram used to show the sequence in which instructions are executed in a
program.
Flowcharts are drawn using specific symbols, each with its own meaning, as given below:
Shape Symbol Name Explanation
Terminal This is oval in shape. It indicates where the program
(Start/Stop) Starts or stops. One can also write either Start/Begin/
Stop/End as alternative words inside the symbol.
Flow lines An arrow that shows directional flow, or the next
instructions to be executed from a given point. Arrows
are used
Input /output This is a parallelogram shaped symbol, indicating
where data is being entered into the computer or
output from the computer, either as a screen display
or printout.
Process Symbol This is a rectangular shape which indicates where
some form of processing occur, for example
where there is a formula to be applied, like
addition, subtraction, etc.
Decision/ This represents where selection is to be done. It is
Condition used where a condition is, especially in repetition and
selection structures. Mostly used where comparisons
are done and it should evaluate to either true or false.
Pre-defined Indicates a module/subprogram/procedure inside a
process main program. This subprogram may also have its own
separate flowchart.
156
Connector Circular in [Link] denotes the start or end of a
subroutine/module/procedure. Nothing should be
written inside it.
Flowcharts Symbols and their Meaning
Example
Write a flowchart of a program that accept student marks entered through the keyboard for the
following subjects, Shona, Ndebele, Computers and English.
The program then calculates the average mark and displays the average mark on the screen.
The result will be as follows:
SUM= 0 (is an assignment statement so it use a process symbol)
AVERAGE = 0 (Process symbol)
INPUT Student Mark obtained in Shona, S (input statement so we use Input/output symbol)
INPUT Student Mark obtained in Ndebele, N (Input/output symbol)
INPUT Student Mark obtained in Computers, C (Input/output symbol)
INPUT Student Mark obtained in English, E (Input/output symbol)
SUM = S + N +C + E (processing statement so we use process symbol)
AVERAGE = SUM/4 (processing statement so we use process symbol)
PRINT AVERAGE (output statement so we use Input/output symbol) End
(terminal symbol) the resultant flowchart will be as follows:
157
Start
SUM = 0
AVARAGE= 0
=
Input Shona Mark, S
Input Ndebele Mark, N
Input Computer Mark, S
Input English Mark, E
SUM= S+N+C+E
AVARAGE= SUM/4
Print AVARAGE
Stop
158
Flowchart
Structure Diagram
It is a diagram that show relationships between different modules in a hierarchical order as
given below.
Structure Diagram
The structure diagram above indicates five sub-programs (modules/procedures) found in the
program called Addition Program.
The sub-programs are Initialise, Enter Values, Add Values, Display Result and Exit Program.
Can you write pseudocode for the diagram above?
Interpreting and testing algorithms
An algorithm must be tested to determine if it gives expected results before coding on the computer.
This is done by dry running the algorithm on a piece of paper.
Dry running (desk checking) is a process of manually testing the logic of a program on paper before
coding on the computer.
Dry running is done to determine the logic of a program (to check if it gives intended results.)
If the algorithm does not give expected results, debugging is then carried out.
Debugging is a process of finding and correcting errors in a program.
Errors in a program are called bugs.
Programs used to find and remove of errors in a program are called debuggers.
Dry running is done using a trace table (dry run table).
Dry running is carried out as follows:
Study the algorithm carefully and understand its task
Identify all variables in the algorithm
On paper, draw a table with each variable representing its own column
159
Go through each instruction in turn, entering values in the rows below the corresponding
variable. Each change in value must be recorded. A set of all possible test data must be used
Trace each instruction, even loops until the end of the program, recording each change.
The last row in each column is the final value of that variable.
Example of a dry run Question
Using a trace table, dry run the following program using the values 45, 78, 23, 89, 94
1. SUM=0
2. AVERAGE = 0
3. INPUT Student Mark obtained in Shona, S
4. INPUT Student Mark obtained in Ndebele, N
5. INPUT Student Mark obtained in Computers, C
6. INPUT Student Mark obtained in English, E
7. SUM = S + N +C + E
8. AVERAGE = SUM/4
9. PRINT AVERAGE
10. End
Analysis of the algorithm and data to be used
The program has 6 variables, namely: S, N, C, E, SUM and AVERAGE. Each will have its own
column.
A seventh column for output may be optional.
We are not sure of the number of rows.
S N C E SUM AVERAGE OUTPUT
0 0
45 78 23 89 235 58.75 58.75
Trace table
Read each statement line by line, inputting values in the table above under the correct column.
Thus:
Line 1: SUM is assigned the value 0, so we write 0 under SUM
Line 2: AVERAGE is also assigned to 0, so we write 0 under AVERAGE.
Line 3: Requires one to input the mark for Shona. 45 is the rst values in our data so it automatically
becomes the mark for Shona and it will be stored in memory location S. So we write 45 under column
S.
Line 4: 78 becomes the mark for Ndebele, stored in memory location N. We write it under N.
160
Line 5: 23 becomes the mark for Computers and will be stored in memory location C. We write it
under C
Line 6: 89 becomes the mark for English and will be stored in memory location E. We therefore
write it under E.
There is no more any other input statement, therefore 94 will not be entered in this program.
There is nowhere to write it so it is left out.
Line 7: SUM is obtained by adding data in memory locations S, N, C and E, that is 45 + 78
+ 23 + 89 = 235. So we write 235 under SUM
Line 8: AVERAGE is obtained by dividing SUM by 4, this becomes 235/4=58.75. So we
write 58.75 under AVERAGE
Line 9: e average is printed on the screen. us the computer displays 58.75, the output
Line 10: Ends or stops the program
Types of Test Data
Test data are all possible values that can used to test the correctness of data that will be used when
program development has been completed.
For example, if a program is to capture all student marks after tests written (which will be out of
100), then we need to test if it will only accept values from 0 to 100.
An algorithm can be tested with different types of test data, which are extreme data, standard data
and abnormal data.
i. Extreme Data (boundary data/border line data): refers to the minimum or the maximum
acceptable values in a given range.
For example, student marks to be entered on a school
report can range from 0 to 100 inclusive. In this case,
0 and 100 are extreme data and the computer must
accept these.
ii. Standard Data: refers to data that lies within (in-between) extreme data in a given range.
In our example above, the values from 1 to 99 are
standard data and must be accepted by the computer.
iii. Abnormal Data: refers to data outside a given range.
The values -1, -50 and all values from 101 and above
are abnormal data.
161
The computer system must generate an error message
and reject abnormal data if it is entered.
162