Algorithm design and

7
CHAPTER

problem solving
At the end of this chapter, you will be able to:
• Understand the program development life cycle, limited to: analysis, design, coding and testing
• Understand that every computer system is made up of sub-systems, which are made up of further sub-systems
• Understand how a problem can be decomposed into its component parts
• Use different methods to design and construct a solution to a problem
• Explain the purpose of a given algorithm
• Understand standard methods of solution
• Understand the need for validation checks to be made on input data and the different types of validation check
• Understand the need for verification checks to be made on input data and the different types of verification check
• Suggest and apply suitable test data
• Complete a trace table to document a dry-run of an algorithm
• Identify errors in given algorithms and suggest ways of correcting these errors
• Write and amend algorithms for given problems or scenarios, using: pseudocode, program code and flowcharts

7.1 Algorithm design and problem solving

An algorithm is a set of instructions that are to be followed to solve a problem or achieve an outcome. You will use many
algorithms on a daily basis that you don’t even know you are following, to complete everyday tasks. For example, you use an
algorithm when crossing the road, look both ways, can you see any cars coming? Cross only when there are no cars coming
or the cars have stopped. You use algorithms all the time in subjects like maths and science to get the correct answer to an
equation, or the perform an experiment successfully.

Computer programs are just algorithms, sometimes very complex algorithms. When a new computer program is created, or an
existing computer program is developed, a process called the program development life cycle is often used. This is a series are
stages that are performed to make sure that all aspects of a program are properly and thoroughly thought out and created.

Exercise 1 The program development cycle

1 Analysis and design are two stages of the program development cycle. Can you name the other two stages?

2 Can you name two tasks that are performed at the analysis stage of the program development cycle?

66 Algorithm design and problem solving

IGCSE_CS_WB_Ch [Link] 66 28/01/21 9:31 AM

 Chapter 7

There are three main methods that can be used to design an algorithm, these are structured diagrams, flowcharts and pseudocode.

A structured diagram is a hierarchical diagram that shows how a program can be decomposed into different subprograms.

Exercise 2 Algorithm design

1 A game allows a user to move up, down, left or right around the screen. The aim of the game is to eat the different fruits
that appear. An orange scores 1 point, an apple scores 2 points and a banana scores 3 points. The user has 60 seconds to
score as many points as they can before the game is over and the users score is output onto the screen.

Complete the structured diagram for the game.

Game

Input Process Output

Player Navigation Update timer Update score

Timer
Up Reset timer Reset score

Fruit

Algorithm design and problem solving 67

IGCSE_CS_WB_Ch [Link] 67 28/01/21 9:31 AM

 Chapter 7

2 A security system on a door allows a user to type a code into a keypad to enter the room. If an incorrect code is input, an
error message is shown and a short alarm sound is played.

Draw a structured diagram for the security system

68 Algorithm design and problem solving

IGCSE_CS_WB_Ch [Link] 68 28/01/21 9:31 AM

 Chapter 7

3 A vending machine allows a user to choose a product to purchase, input money for a product and receive any monetary
change that is not used when purchasing a product.

Draw a structured diagram for the vending machine system.

Algorithm design and problem solving 69

IGCSE_CS_WB_Ch [Link] 69 28/01/21 9:31 AM

 Chapter 7

A flowchart is a diagram that shows the input, processes, output and storage of data, in the order in which they occur to
solve a problem. It is a diagram that represents an algorithm.

Exercise 3 Algorithm flowcharts

1 Write the name of each flowchart symbol in the symbol shape.

2 A computer program allows a user to input two numbers. It multiplies the numbers together and if the answer is larger than
100 it outputs the message “Greater than 100”. The program loops until the user does not want to input any more numbers.

Complete the flowchart that represents an algorithm for the computer program.

Start

Input num2

Is answer >100

Input

70 Algorithm design and problem solving

IGCSE_CS_WB_Ch [Link] 70 28/01/21 9:31 AM

 Chapter 7

3 A tennis club has a computer program that allows a user to input a players age. The program will then tell the user if they
should be out into the Junior, Senior or Veterans category for a tennis competition. Junior players are age 16 and under.
Senior players are between 17 and 35. Veteran players are over 35 years old. The program loops until no more players need to
be input.

Draw a flowchart to represent an algorithm for the tennis club computer program.

Algorithm design and problem solving 71

IGCSE_CS_WB_Ch [Link] 71 28/01/21 9:31 AM

 Chapter 7

4 A computer program allows a user to enter the weight in Kgs for a parcel. The program outputs whether the parcel is a
small parcel, a medium parcel or a large parcel.
A small parcel weighs less than 1kg
A medium parcel weighs between 1kg and 2.5 kgs
A large parcel weighs more than 2.5kgs

The cost to send a small parcel is $1.5, a medium parcel is $2.75 and a large parcel is $4. The program has 3 1D arrays. These
are a small parcels array, a medium parcels array and a large parcels array. Each time a parcel is input, the weight of the
parcel is added to the correct array.

The program loops until no more parcels need to be input. When all parcels have been input, a total cost for all the parcels
is displayed. The contents of each array are also output.

Draw a flowchart to represent an algorithm for the parcel computer program.

72 Algorithm design and problem solving

IGCSE_CS_WB_Ch [Link] 72 28/01/21 9:31 AM

 Chapter 7

Pseudocode is a term that is used for any code that is not written in a particular programming language. There isn’t a set
standard for pseudocode, but Cambridge provide a standard that they use to write their exam questions. You should make
yourself familiar with this standard. Pseudocode can also be used to present an algorithm, but in written form rather than as
a diagram.

Algorithm design and problem solving 73

IGCSE_CS_WB_Ch [Link] 73 28/01/21 9:31 AM

 Chapter 7

Exercise 4 Pseudocode

1 Look at the earlier description given in question 2 of exercise 3. This is a reminder of the program description:

A computer program allows a user to input two numbers. It multiplies the numbers together and if the answer is larger than
100 it outputs the message “Greater than 100”. The program loops until the user does not want to input any more numbers.

Complete the pseudocode to represent the algorithm

REPEAT

INPUT

INPUT num2

answer

IF answer > 100

THEN

ENDIF

OUTPUT “Do you have any more numbers to enter?”

INPUT moreNumbers

IF

THEN

flag TRUE

ELSE

flag

ENDIF

UNTIL flag = FALSE

2 Look at the earlier description given in question 3 of exercise 3. This is a reminder of the program description:

A tennis club has a computer program that allows a user to input a players age. The program will then tell the user if they
should be out into the Junior, Senior or Veterans category for a tennis competition. Junior players are age 16 and under.
Senior players are between 17 and 35. Veteran players are over 35 years old. The program loops until no more players need to
be input.

Write an algorithm in pseudocode to represent the computer program.

74 Algorithm design and problem solving

IGCSE_CS_WB_Ch [Link] 74 28/01/21 9:31 AM

 Chapter 7

Algorithm design and problem solving 75

IGCSE_CS_WB_Ch [Link] 75 28/01/21 9:31 AM

 Chapter 7

3 Look at the earlier description given in question 4 of exercise 3. This is a reminder of the program description:

A computer program allows a user to enter the weight in Kgs for a parcel. The program outputs whether the parcel is a
small parcel, a medium parcel or a large parcel.
A small parcel weighs less than 1kg
A medium parcel weighs between 1kg and 2.5 kgs
A large parcel weighs more than 2.5kgs

The cost to send a small parcel is $1.5, a medium parcel is $2.75 and a large parcel is $4. The program has 3 1D arrays. These
are a small parcels array, a medium parcels array and a large parcels array. Each time a parcel is input, the weight of the
parcel is added to the correct array.

The program loops until no more parcels need to be input. When all parcels have been input, a total cost for all the parcels
is displayed. The contents of each array are also output.

Write an algorithm in pseudocode to represent the computer program.

76 Algorithm design and problem solving

IGCSE_CS_WB_Ch [Link] 76 28/01/21 9:31 AM

 Chapter 7

Once you have decomposed a problem and designed an algorithm to solve it, you will need to code your algorithm. This
is what happens in the coding stage of the program development cycle. This is where you will start writing the computer
program for the algorithm in a high-level programming language.

4 Which high level programming language will you use to code your program?

You will complete a range of programming activities in chapter 8 of this workbook.

Once you have created a computer program you need to test it to make sure that is works correctly, that it does not have
any errors in the syntax or the logic of the program. You will also need to check that is meets all the requirements need in
solving the problem. This is what happens in the testing phase of the program development cycle.

Once you have written down your program in the space given in this workbook, you should use a programming
IDE to test each of your programs to see if they work. It is good practice for you to be able to write program code
as you will have to do this in the exam. It is also good practice for you to create the program in an IDE as the skill of
programming is one of the fundamental skills you will learn in this IGCSE.

Algorithm design and problem solving 77

IGCSE_CS_WB_Ch [Link] 77 28/01/21 9:31 AM

 Chapter 7

Exercise 5 Testing

1 What is the difference between a syntax error and a logic error?

2 There are four different types of test data that can be used to test a computer program.

Consider a program that will only allow numbers between 1 and 50 (inclusive) to be input.

Complete the table with a description for each type of test data, along with example test data for the program.

Type of test data Description of test data Example test data

Normal

Abnormal

Extreme

Boundary

One tool that can be used as a dry-run to test an algorithm is called a trace table. A dry-run of an algorithm is where
the inputs, processes, outputs and storage of an algorithm are tested on paper, rather than used an electronic
computer program.

78 Algorithm design and problem solving

IGCSE_CS_WB_Ch [Link] 78 28/01/21 9:31 AM

 Chapter 7

3 Consider the following algorithm represented as a flowchart:

Start

count 0
total 0

INPUT studentAge

total total + studentAge

count count + 1

No
Is count = 10?

Yes

avg = total / count

OUTPUT
“Average age is “ avg

Stop

Algorithm design and problem solving 79

IGCSE_CS_WB_Ch [Link] 79 28/01/21 9:31 AM

 Chapter 7

a. Can you describe the purpose of the algorithm?

b. Complete the trace table for the algorithm, using the data set of students ages given.

12, 14, 16, 9, 5, 17, 13, 12, 15, 8

count total studentAge avg OUPUT

80 Algorithm design and problem solving

IGCSE_CS_WB_Ch [Link] 80 28/01/21 9:31 AM

 Chapter 7

4 Consider the following algorithm represented as pseudocode:

guessCorrect FALSE

INPUT player1Num

WHILE guessCorrect <> TRUE

INPUT player2Guess

IF player1Num = player2Guess

THEN

OUTPUT “Your guess is correct”

guessCorrect TRUE

ELSE

IF player1Num > player2Guess

THEN

OUTPUT “Too high”

ELSE

OUTPUT “Too low”

ENDIF

ENDIF

ENDWHILE

a. Can you describe the purpose of the algorithm?

Algorithm design and problem solving 81

IGCSE_CS_WB_Ch [Link] 81 28/01/21 9:31 AM

 Chapter 7

b. Complete the trace table for the algorithm.

Player 1 enters a number of 55.

Player 2 enters the data set 10, 25, 65, 50, 58, 54, 57, 55

guessCorrect player1Num player2Guess OUPUT

When writing computer programs, you may want the data input by a user to follow certain rules. You can set rules for
the data input and this is done using validation. There are several types of validation check.

82 Algorithm design and problem solving

IGCSE_CS_WB_Ch [Link] 82 28/01/21 9:31 AM

 Chapter 7

Exercise 6 Validation

1 Complete the table with a description and an example for each type of validation. The first one has been done for you:

Type of validation Description of validation Example

A range check looks whether the data input is

Range check The number must be between 1 and 100.
within a given range of values.

Length check

Type check

Presence check

Format check

Check digit

Algorithm design and problem solving 83

IGCSE_CS_WB_Ch [Link] 83 28/01/21 9:31 AM

 Chapter 7

2 You can also perform a visual check on data, or have a user enter the same data twice, known as a double entry check.

These two checks are not types of validation, what are they types of?

There are certain standard algorithms that you need to know the purpose of and how they operate, these are a linear search
and a bubble sort.

Exercise 7 Linear search and bubble sort

1 Consider the data set:

1, 13, 25, 14, 18, 36, 21

a. Explain how a linear will find the value 36 in the data set.

b. Explain how a bubble sort will sort the data set into order, from lowest to highest.

One important skill when creating algorithms is the ability to identify errors in a computer program. You may not always
write a program perfect first time, so you need to be able to identify where you may have gone wrong.

84 Algorithm design and problem solving

IGCSE_CS_WB_Ch [Link] 84 28/01/21 9:31 AM

 Chapter 7

Exercise 8 Identifying errors

1 Consider the algorithm:

count 0

WHILE count <=3

OUTPUT “Please enter a colour.”

INPUT colour

IF colour = “Red” OR colour = “Blue” AND colour =

“Purple”

THEN

OUTPUT “That is one of my favourite colours.”

ELSE

INPUT “That is not one of my favourite colours, try again.”

ENDIF

ENDWHILE

count count + 1

The algorithm should:

• allow a user to input a colour

• check whether the colour is a favourite colour
• outputs messages to say whether it is a favourite colour or to try again if not
• loop until the user has had three guesses.

The algorithm contains errors, can you identify these errors? When you have, rewrite the algorithm with the errors corrected.

Algorithm design and problem solving 85

IGCSE_CS_WB_Ch [Link] 85 28/01/21 9:31 AM

 Chapter 7

86 Algorithm design and problem solving

IGCSE_CS_WB_Ch [Link] 86 28/01/21 9:31 AM

 Chapter 7

2 Consider the algorithm:

flag FALSE

lowestScore 100

highestScore 0

totalScore 0

count 10

WHILE flag = TRUE

OUTPUT “Please input the score.”

INPUT score

IF score < lowestScore

THEN

lowestScore score

ENDIF

IF score != highestScore

THEN

highestScore score

ELSE

OUTPUT “Do you have any more scores to input, Y or N?”

INPUT answer

IF answer = “N”

THEN

flag FALSE

ENDIF

ENDIF

count count + 1

ENDWHILE

totalScore totalScore + score

averageScore totalScore/count

OUTPUT lowestScore, highestScore, totalScore

Algorithm design and problem solving 87

IGCSE_CS_WB_Ch [Link] 87 28/01/21 9:31 AM

 Chapter 7

The algorithm should:

• allow the user to input a score
• checks whether the score input is the lowest score input. If it is, it records the new lowest score
• checks whether the score input is the highest score input. If it is, it records the new highest score
• loops until the user has now more scores to input
• calculates the average score input
• when all scores have been input, it outputs the lowest score, the highest score and the average score

The algorithm contains errors, can you identify these errors? When you have, rewrite the algorithm with the errors corrected.

88 Algorithm design and problem solving

IGCSE_CS_WB_Ch [Link] 88 28/01/21 9:31 AM

 Chapter 7

Algorithm design and problem solving 89

IGCSE_CS_WB_Ch [Link] 89 28/01/21 9:31 AM

 Chapter 7

Revision checklist

Need to revisit Satisfactory Confident

I understand the program development life cycle, limited to: analysis,

design, coding and testing
I understand that every computer system is made up of sub-systems,
which are made up of further sub-systems
I understand how a problem can be decomposed into its component
parts
I can use different methods to design and construct a solution to a
problem
I can explain the purpose of a given algorithm
I understand standard methods of solution
I understand the need for validation checks to be made on input data
and the different types of validation check
I understand the need for verification checks to be made on input
data and the different types of verification check
I can suggest and apply suitable test data
I can complete a trace table to document a dry-run of an algorithm
I can identify errors in given algorithms and suggest ways of
correcting these errors
I can write and amend algorithms for given problems or scenarios,
using: pseudocode, program code and flowcharts

90 Algorithm design and problem solving

IGCSE_CS_WB_Ch [Link] 90 28/01/21 9:31 AM