Chapter 7 : Algorithm design

and Problem Solving

Algorithm design and Problem Solving
You should be able to
1. Understand the program development life cycle, limited to: analysis, design, coding and testing
2. (a) Understand that every computer system is made up of sub-systems, which are made up of further

sub-systems
(b) Understand how a problem can be decomposed into its component parts
(c) Use different methods to design and construct a solution to a problem
3. Explain the purpose of a given algorithm
4. Understand standard methods of solution
5. (a) Understand the need for validation checks to be made on input data and the different types of
validation check
(b) Understand the need for verification checks to be made on input data and the different types of
verification check
6. Suggest and apply suitable test data
7. Complete a trace table to document a dry-run of an algorithm
8. Identify errors in given algorithms and suggest ways of correcting these errors
9. Write and amend algorithms for given problems or scenarios, using: flowcharts
The program development life cycle
The program development life cycle is divided into five stages, we will discuss only

the four stages listed below:

• analysis

• design

• coding

• testing
The program development life cycle
1. Analysis phase :
Analysis is the first phase of software development. a systems analyst will meet with the client to determine:
• the purpose of the software : is often expressed as a description of what the software will be used for
• the functional requirements of the software : will specify inputs, processes and outputs.
analysis tools are used to identify exactly what is required from the program. :
• abstraction keeps the key elements required for the solution to the problem focus on important properties while ignoring
non-essential details
• Decomposition :breaks down a complex problem into smaller parts, which can then be subdivided into
even smaller parts, that can be solved easily.

2. Design The program specification from the analysis stage is used to show to how the program should be developed. This
can be formally documented using structure charts, flowcharts and pseudocode

3. Coding Each module of the program is written using a suitable programming language and then tested to see if it works.

4. Testing The completed program or set of programs is run many times with different sets of test data. This ensures that all
the tasks completed work together as specified in the program design
Decomposing
Decomposing a problem Any problem that uses a computer system for its solution needs to
be decomposed into its component parts.
The component parts of any computer system are:
• inputs – the data used by the system that needs to be entered while the system is active
• processes – the tasks that need to be performed using the input data and any other
previously stored data
• outputs – information that needs to be displayed or printed for the users of the system »
storage – data that needs to be stored in files on an appropriate medium for use in the
future
Design stages
Top-down design is the decomposition of a computer system into a set of sub-systems, then breaking each sub-
system down into a set of smaller sub-systems, until each sub-system just performs a single action.

Benefits of Top-Down Design

• Breaking a problem down into smaller parts/tasks makes it far easier to understand, solve and manage
• Top down design allows several programmers or teams to work on the same project, without getting in each
other’s way
• Each sub-system code is tested separately
A computer system is made up of : software, data, hardware, communications and people
each computer system can be divided up into a set of sub-systems.
Subsystems
The sub-systems are sometimes referred to as:
• Modules
• Sub-routines , library routine
• Procedures

A Subroutine is a piece of code which is written within given program. The Subroutine can be called from the
same program but can not be called from other programs. In other words subroutines are local to program.
There are two different types of subroutines that we mainly use:
• Functions : return values back to the main program
• Procedures : do not return a value back to the main program.
Library routine : is a set of pre-written programming instructions for a given task ( fixed instructions) that is
already available for use. It is pre-tested and usually performs a task that is frequently required.

Module : is a piece of code which can be independently created and maintained to be used in different programs .
Methods used to design and construct a solution to a problem
Algorithm : Is a set of instructions designed to perform a specific task.

The following methods need to be used for the algorithm :

• Structure diagram
• flowcharts
• Pseudocode

Structure diagrams can be used to show top-down design in a diagrammatic form. Structure diagrams are
hierarchical, showing how a computer system solution can be divided into sub-systems with each level giving
a more detailed breakdown. If necessary, each sub-system can be further divided.
Example 2: Alarm app for a smart phone
A flowchart :
• A FLOWCHART shows diagrammatically the steps required for a task (sub-system) and the order that they are to
be performed. These steps together with the order are called an ALGORITHM
A flow chart shows the key points in an algorithm:
• the start and end
• the order in which the sequences of instructions are performed
• the points where inputs and outputs occur
• the points where decisions are made about what to do next

Standard flowchart symbols :

1. Flow lines are used to show the direction of flow which is usually, but not always, top to bottom and
left to right.

1. Begin/End Terminator symbols are used at the beginning and end of each flowchart.
Flowlines ( start OUT, End IN)
3. Process symbols are used to show when values are assigned to an item/variable.
Flow lines ( one IN , and one OUT)

4. Input/Output/Read/Get/Print symbols are used show input of data and output of

information .Flow lines ( one IN , and one OUT)

5. Decision symbols are used to decide which action is to be taken next. These can be used for
selection and repetition/iteration. Flow lines ( one IN , and two OUT (YES/NO)
Producing algorithms
Stages in producing an algorithm :
1. Make sure that the problem is clearly specified.
2. Break the problem down into sub-problems; if it is complex
3. Most problems, even the simplest ones can be divided :
• input
• processing
• output of results.
4. Decide on :
• how any data is to be obtained and stored (read/ input variables )
• what is going to happen to the data (processing )
• how any results are going to be displayed.(format and the order of the outputs)
5. Decide on how you are going to construct your algorithm, using a flowchart or pseudocode.
6. Construct your algorithm, making sure that it can be easily read and understood by someone else This involves setting it
out clearly and using meaningful names for any data stores.
7. Use several sets of test data (normal, abnormal and boundary) and trace tables to find any errors.
8. If any errors are found, repeat the process until you think that your algorithm works perfectly.
Flowchart examples
Example 1: Determine and Output Whether Number N is Even or Odd
Example 2: Determine Whether a Temperature is Below or Above the Freezing Point
Step 1: Input temperature.
Step 2: If it is less than 32, then print "below freezing point", otherwise print "above freezing point".

Example 3: Determine Whether A Student Passed the Exam or Not

Step 1: Input grades of 4 courses M1, M2, M3 and M4.
Step 2: Calculate the average grade with the formula "Grade=(M1+M2+M3+M4)/4".
Step 3: If the average grade is less than 60, print "FAIL", else print "PASS".

Example 4: Find the Sum of Two Numbers Entered

Step 1: Read the Integer A.
Step 2: Read Integer B.
Step 3: Perform the addition by using the formula: C= A + B.
Step 4: Print the Integer C.

Example 5: Arrange the numbers X, Y, Z in descending order

Step 1: Input the value for variables X, Y, Z.
Step 2: Read the integers X, Y, Z.
Step 3: Check if x>y, x>z, y>z
Step 4: Print the possible order.
Flowchart examples
Example 6: Calculate the Sum of 50 Numbers
Step 1: Declare number N= 0 and sum= 0
Step 2: Determine N by N= N+1
Step 3: Calculate the sum by the formula: Sum= N + Sum.
Step 4: Add a loop between steps 2 and 3 until N= 50.
Step 5: Print Sum.
Example 7 : Draw a flowchart to read 10 numbers and print the largest , and smallest.

Example 8: Find the largest price among 100 given values and reduce it by 10%
Step 1: Read the 100 prices.
Step 2: Compare the first price with the next and let the greater of the two be 'max' in the 'max index.
Step 3: Loop it until the largest price has been found.
Step 4: Reduce the 'max' value by 10% using the formula: prices [max index] = prices [max index] x 0.9.
Step 5: Print.

Example 9 : Write an algorithm using either pseudocode or a flowchart, to:

• input a positive integer
• use this value to set up how many other numbers are to be input
• input these numbers
• calculate and output the total and the average of these numbers.
Counting and totaling
Totaling

Is adding together a set of values to write a program to total you need to :

• Initialize the total to 0
• Add the value together

Ex. Total  Total + Number

Calculating the average of all the values in a list is an extension of the totalling method, for example, calculating
the average mark for a class of students

Counting
Counting is used to find how many numbers or items there are in a list.
Counting can keep track of how many iterations( repetition ) your program has performed in a loop.

• Initialize the counter to 0

• increase the value by 1

Counter  Counter +1
Counting and totaling
Example : The flowchart shows an algorithm that should:
• allow 100 numbers to be entered into the variable Number
• total the numbers as they are entered
• output the total and average of the numbers after they have all been entered.
Variables :
• Counter to count 100 numbers must be initialized to 0
• Number : saves the input values
• Total : saves the total : initialize it to 0 and use the formula : Total  total + Number
• Average  Total / 100 OR Total /counter
Process :
1) counter 0 , Total  0
2) Input the number
3) Add it to the total
4) Increase the Counter
5) Check the counter : two options
a) If counter <= 99/ Counter<100 If yes return to step 2 and if
no go to step 6
OR
b) If counter = 100 / Counter >99 / Counter >= 100
• If Yes go to step 6
• If No go to step 2
6) Average  Total /100
7) Print Total , Average
Finding Maximum and Minimum
Finding minimum and maximum of 10 numbers
Variable :
• Counter to count 10 numbers must be initialized to 0
• Number : saves the input values
• Highest : saves maximum number , saves the first number as an initial value
• Lowest : saves minimum number , saves the first number as an initial value

1. Counter 0
2. Input the number
3. Compare the number with the Highest
if Highest < Number ---Yes---- Highest  Number
---No---- go to step 5
4. Compare the number with the Lowest
if Lowest > Number ---Yes---- Lowest  Number
---No---- go to step 5
5. Increase the Counter
6. Check the counter : two options
a) If counter <= 8 / Counter<9 If yes return to step 2 and if
If no go to step 6
OR
b) If counter = 9 / Counter > 8 / Counter >= 9
• If Yes go to step 6
• If No go to step 2
6) Print Highest , Lowest
2) a) Draw a flowchart for an algorithm to input numbers. Reject any numbers that are
negative and count how many numbers are positive. When the number zero is input, the
process ends and the count of positive numbers is output.

0478/22/M/J/
Validation and Verification
In order for computer systems to only accept data inputs that are reasonable and
accurate,
Two different checking methods: Validation and Verification

VALIDATION :
• Validation is the automated checking by a program that data is reasonable and sensible before it
is accepted into a computer system.
• When data is validated by a computer system, if the data is rejected a message should be output
explaining why the data was rejected and another opportunity given to enter the data
• By adding validation to your code, it prevents the program from crashing when incorrect data is entered.
• Is the automated checking by a program that data is reasonable before it is accepted into a computer system.
• It does not check the accuracy of data.
VALIDATION’s types :
Validation type How it works Example usage
checks that the value of a number is between an For example, checking that percentage marks are
Range check
upper value and a lower value. between 0 and 100 inclusive

checks either that data contains an exact number

a password must be exactly eight characters in length
of characters
Length check
or that the data entered is a reasonable number a family name could be between two and thirty
of characters characters inclusive
EX. The subject mark should be number not text or
Type Check Checks the data entered is of a given data type
string

checks that the characters entered conform to a Ex. Date in British English is : dd/mm/yyyy
Format check
pre-defined pattern, Date in American English: Mm/dd/yyyy
The last digit in a code are used to check the
Check digit other digits are correct, it is calculated from all Barcode readers in supermarkets use check digits
the other digits

k checks to ensure that some data has been

Presence check In most databases a key field cannot be left blank
entered and the value has not been left blank,
VALIDATION’s types :
Similarities between the check digit and checksum methods.
• They both calculate a value from the data
• They both append the calculated value to the data
• They both recalculate the value
• They both report an error if they don’t match

how a check digit can be used to make sure the data entered is correct.
• Data is input with check digit
• A calculation is performed on the (inputted) data
• The calculated digit is compared to a stored value
• If it matches, the data entered is correct
• If it does not match, the data entered is incorrect
Verification
• Verification is checking that data has been accurately copied onto the computer or transferred from
one part of a computer system to another.
• Verification does not check if data makes sense or is within acceptable boundaries, it only checks that
the data entered is identical to the original source.
Verification methods include:
• double entry
• screen/visual check
• parity check
• checksum.
1. DOUBLE ENTRY : the data is entered twice, the computer system compares both entries and outputs an
error message requesting that the data is entered again if they are different.

2. A SCREEN/VISUAL CHECK
• is a manual check completed by the user who is entering the data.
• When the data entry is complete the data is displayed on the screen and the user is asked to confirm
that it is correct before continuing.
• The user either checks the data on the screen against a paper document that is being used as an input
form or confirms from their own knowledge if the data is about them.
Test data
• In order to check whether a solution (flowchart or Pseudocode ) is working (under a range of conditions )
as it should, it needs to be tested.
• This includes testing any validation you have created to ensure it performs as expected.
• Usually before a whole system is tested each sub-system is tested separately.
• Algorithms can be tested :
- by a person working through them using any data that is required and seeing what is the result.
- computer programs can be tested by running them on a computer.
When creating a testing plan, the test data that you use shouldn’t be random values.

A SET OF TEST DATA is all the items of data required to work through a solution. In order to prove that
program or algorithm solutions do what they are supposed to do, a set of test data should be used that the
program would normally be expected to work with, together with the result(s) that are expected from that
data.
Test data
Types of Set of Data :
1. Normal data : is test data that is typical (expected) and should be accepted by the
system.
In Example1 Normal Data :
- Number not text or string or any other character .
- Range 0-100

Normal test : 70,85,50,60,77 should be accepted

Expected result : average = 68.4.

2. Abnormal data (erroneous data). : is test data that falls outside of what is acceptable
and should be rejected by the system.
In Example1 abnormal Data : -12, eleven , 105 should be rejected
Test data
3. Extreme data : is test data at the upper or lower limits of expectations that should
be accepted by the system.
In Example1 Extreme Data :
Lower limit : 0 and upper 100 the largest and smallest marks that should be
accepted

4. Boundary Data: data that is on the edge of being accepted and being rejected
at each boundary two values are required,
one value is accepted and the other value is rejected
In Example1 boundary Data : 0-100
0 and -1 : 0 is accepted and -1 is rejected
100, 101 : 100 is accepted and 101 is rejected
Trace table

A trace table :

• Is a technique used to test algorithms in order to make sure that no logical errors

occur while the calculations are being processed.

• This will require the use of test data (normal ) to check if the expected results is generated by

the algorithm (flowchart or pseudocode).

• Test data is then used to dry run(manually) the flowchart/pseudocode and record the results

on the trace table.

• Dry run means : to go through each line of the code ( run it on papers ) before running it on the

machine
The algorithm, shown by this flowchart, allows the input of examination marks for a class of students. A mark of 999 ends
the process. If a mark is 40 or over then a pass grade is awarded. The number of pass grades is calculated for the whole class.
If this is under 50% of the class, the class is offered extra help.

Complete a trace table for the algorithm using this input data:
88, 24, 60, 30, 44, 17, 25, 22, 54, 6, 999, −1
4. This flowchart inputs a whole number. The function INT returns the integer value of a number. For example, INT (7.5) is
7 An input of -1 ends the routine. (a) Complete the trace table for the given algorithm using this
input data: 7, 6, 5, 4, –1, 12, 34
0478/22/F/M/22
This algorithm checks the temperature of hot food being served to customers.
Complete the trace table for the algorithm using this input
data: 75, 78, 84, 87, 91, 80, 75, 70, 65, 62, –1, 20
The effectiveness of a solution

the effectiveness of a given solution (flowchart or pseudocode ) ask the following

questions :

1. Does the solution work for all sets of data?

2. Does the solution have any unnecessary processes that are never used?

3. Are any actions repeated more often than necessary?

4. Can the solution be simplified and still work as well?