1.1.

1 Algorithms
• A solution to a problem with the following characteristics is called an
algorithm
• Unambiguous
• A sequence of steps
• Can be used again and will always provide the same result
• Provide a solution to a problem
• Most problems have more than one solution, so different algorithms
can be created for the same problem
Successful Algorithm
• Three points to consider when deciding whether an algorithm is
successful or not:
• Accuracy – lead to expected output
• Consistency – must produce the same result each time it is run
• Efficiency – must solve the problem in the shortest possible time, using as few
computer resources as possible
Algorithm vs. Program
• They are related but not the same

• An algorithm is detailed design for a solution

• A program is when that design is implemented
1.1.2 Display an algorithm
• An algorithm can be expressed in the following ways
• (Designed for humans to follow)
• Written descriptions
• Flowcharts
• (Form the basis of computer programs)
• Pseudocode
• program code
Display an algorithm- written descriptions
• Simplest way of expressing an algorithm
• Example – adding two numbers
• Enter the first number
• Enter the second number
• Calculate the total by adding the first and the second numbers
• Output the total
Display an algorithm- flowcharts
• Show an algorithm as a diagram
• Provide a visual display
• There are special symbols that have to be used in a flowchart, you
can’t make up your own – no body would be able to understand your
algorithm

Indicates a subprocess that may

be defined in a separate flowchart connector
Display an algorithm – flowcharts
• Example – flowchart showing the adding of two numbers
Display an algorithm- pseudocode
• Code the solution in an actual programming language
• Allow developer to concentrate on the logic and efficiency of the
algorithm without having to bother about the rules of any particular
programming language
• Relatively straightforward to translate an algorithm written in
pseudocode into any high-level programming language
Display an algorithm- pseudocode
• Example – algorithm for adding two numbers
• SEND ‘please enter the first number’ TO DISPLAY
• RECEIVE firstNumber FROM KEYBOARD
• SEND ‘please enter the second number’ TO DISPLAY
• RECEIVE secondNumber FROM KEYBOARD
• SET total TO firstNumber + secondNumber
• SEND total TO DISPLAY
Display an algorithm- pseudocode
• Give a clear step-by-step instructions that the computer will be
expected to carry out
• Introduce some important programming concepts including:
• Variables with identifiers - total, firstNumber and secondNumber
• Text in single/double quotation marks (not for variable display)
• Arithmetic operators
• Produce a written description and
pseudocode of this algorithm.
Display an algorithm – program code
• Python!!!
Creating Algorithm - Sequence
• Simplest type of control structure in computer programming
• Sequence control structure contains a series of steps of statements
that are executed in the same order as they are written
Pseudocode Flowchart
statement_1
statement_2
......
...... Statement_1 Statement_2 Statement_n
statement_n

Sequence control structure

Creating Algorithm - Selection
• Allow a program to choose between two or more alternatives depending
on the condition specified
• Use the IF…THEN…ELSE…END IF statement structure and a conditional
expression to determine what the program should do next
• A conditional expression is a logical expression returning a Boolean value
(i.e. True or False)
• The conditional expression in an IF statement will be evaluated first
• If the condition is True – THEN part will be executed
• If the condition is False – THEN part will be skipped and ELSE part will be
executed instead
Creating Algorithm - Selection
logic structure Pseudocode Flowchart

IF… IF {conditional expression} THEN

THEN… {THEN part}
END IF END IF

IF {conditional expression} THEN

IF…
{THEN part}
THEN…
ELSE
ELSE…
{ELSE part}
END IF
END IF
Creating Algorithm - Selection
• Relational operators and logical operators are commonly used in the
conditional expression of a control structure
Relational operator Example Description
= X = 100 X is equal to 100.
<> X <> 100 X is not equal to 100.
> X > 100 X is greater than 100.
< X < 100 X is less than 100.
>= X >= 100 X is greater than or equal to 100.
<= X <= 100 X is less than or equal to 100.
Examples of relational operators
Creating Algorithm - Selection

Logical operator Example Description

AND (X = 1) AND (Y = 5) X is equal to 1 and Y is equal to 5.

OR (X = 1) OR (Y = 5) X is equal to 1 or Y is equal to 5.

NOT NOT (X = 1) X is not equal to 1.

Examples of logical operators
 Example
Convert the following flowchart into pseudocode.
Creating Algorithm – different Peter’s solution

solutions to the same problem

Peter, Paul and Mary are each
asked to work out a solution to the Fee = 30

problem. They all use the IF

statement to design their
algorithms, but the solution Fee = 60

flowcharts they draw are different.

Yes
Age > 60

Fee = 20
No
 Paul’s solution

Mary’s solution

Age > 60

Fee = 20 Fee = 60 Fee = 30 Fee = 30 Fee = 60 Fee = 20

Creating Algorithm - Iteration
• The same block of statements will be repeated as long as a certain
condition is met.
• The condition can be checked either before or after executing the
loop-body, depending on which iteration control structure is used.
• If the condition is checked before executing the loop-body, the loop is
a pretest loop. Otherwise, the loop is a posttest loop.

Pretest loop
Posttest loop
Creating Algorithm - Iteration
• For loop
• Repeats the statements written in the
loop-body a specific number of times.
• Can be implemented as an increment or a
decrement loop.

FOR {variable} FROM {initial value} TO {final value} DO

{loop-body}
END FOR
Creating Algorithm - Iteration
• WHILE-loop
• When a program comes to a WHILE-loop, the conditional expression will be
evaluated first.
• If the condition is satisfied, the program will run the loop-body, and then the
condition is evaluated again.
• The loop will continue to run as long as the condition is satisfied.

WHILE {condition} DO
{loop-body}
END WHILE
Creating Algorithm - Iteration
• Iteration
• REPEAT…UNTIL-loop
• When a program comes to a REPEAT…UNTIL loop, the loop-body will continue
to run until a condition called the ‘exit condition’ is met.
• A posttest loop

REPEAT
{loop-body}
UNTIL {condition}

Flowchart and pseudocode for a REPEAT… UNTIL-loop

Creating Algorithm
• A human can understand the instructions
by checking the kettle over and over again
• How about for a computer?
→ Unambiguous
Activity
 1.1.3 Understand the purpose of an algorithm
Q1: what is the purpose of
this algorithm?
Q2: what would be the
output of this algorithm
for these test scores:
91, 56 and 78?
1.1.4 and 1.1.5 Tracing and Testing Algorithms
• After an algorithm is designed, we need to ensure that it meets our
purpose.
• Three types of programming errors:
• Syntax Error
• Run-Time Error
• Logic Error
• Unlike in program testing, we can ignore syntax errors for algorithm
testing.
Tracing and Testing Algorithms
• Dry run
• Used to examine the logic and code of a program by simulating the execution
of the program on paper.
• Conducted before commencing test execution.
• To dry run a program, we have to build a trace table.
• List the values of the variables on the table when running through the
program one line at a time.
• We can have a better understanding of the actual performance of the
program.
Tracing and Testing Algorithms
• Dry run
• The steps of a dry run:
• Prepare a set of test data.
• Create a trace table.
• Input the test data into the program.
• Let the test data run through the program one line at a time.
• Write down the values of all the variables for each line.
• Particularly useful for tracing algorithms that are written in pseudocode.
• Pseudocode cannot be executed by a computer until it has been converted
into a computer program.
 Example
• In the program below (PROGRAM DVT), we will demonstrate
how the test data runs through the program by using a trace
table. Suppose the value of the test data Num1 = 3 and
Num1 = 5.
Value of Num1 Value of Num2
PROGRAM DVT
10 RECEIVE Num1 FROM KEYBOARD 3 (test data) Undefined
20 Num2 = Num1 + 2
30 Num1 = Num2 - 1
40 Num2 = Num1 * 5
50 Num2 = Num2 / 2
60 SEND Num1, Num2 TO DISPLAY
Example - Using a trace table to run through a
control structure
Use a trace table to show the values of num, i and the condition
(i < 4) at the end of each iteration of the following control
structure.
num = 2 num i i < 4
i = 0
WHILE i < 4 DO
num = num + i
i = i + 1
END WHILE
Tracing and Testing Algorithms
• Test data
• Used to check the accuracy of a program
• Usually generated or selected intentionally
• Valid test data
• Show whether the program design is correct.
• Invalid test data
• Test whether the program can handle improper entries.
• We use test data to test a program and obtain a test result.
• We compare the test result with the expected result.
• If the test result is not the same as the expected result, there may be errors in
the program.
Tracing and Testing Algorithms
• Test data
• Should not be chosen at random.
• Important points for preparing a set of test data:
• Cover the whole range of allowable data.
• Should be able to test whether a program can handle improper entries, i.e. It should
include invalid entries.
• Should be able to test all parts of a program such that:
• Every branch of a selection control structure is tested.
• Every module of a large program is tested.
• In boundary cases, the test data is a set of critical values that
• Affect the result of the condition check
• The logical path of control structures in a program.
Example - Tracing and Testing Algorithms
• Determining the expected results and reasons for using the chosen
test data
• Miss Wong designs an algorithm to return the grade for an inputted mark.
The mark is a whole number, ranging from 0 to 100. Her grading system is as
follows:
Grade Range of marks

A Mark > 90
B 80 < Mark ≤ 90
C 65 < Mark ≤ 80
D 50 < Mark ≤ 65
F Mark ≤ 50
Example - Tracing and Testing Algorithms
Test Expected Test for Test for Test for
data result extreme value boundary case invalid data

0 F ✓
• Determining the
50 F
expected results ✓
and reasons for 65
using the chosen
80
test data
• Write down the 90
expected output
and determine 100
the reasons of
105
using such test
data. −20

18.8 Invalid entry ✓

1.1.8 Sorting and Searching Algorithm - Bubble Sort
• When data is sorted, different items must be compared with each other
and moved so that they are in either ascending order or descending
order
• Bubble sort algorithm
• Start at the one end of the list and compares pairs of data items
• If they are in wrong order, they are swapped
• Continue the comparison of pairs to the end of the list (each traversal → a pass)
• Repeat the process until there have been no swaps during a pass
Sorting and Searching Algorithm - Bubble Sort
• Example – in Ascending Order
Sorting and Searching Algorithm –
Bubble Sort
• Flowchart and Python codes

def bubbleSort(arr):
n = len(arr)

# Traverse through all array elements

for i in range(n):

# Last i elements are already in place

for j in range(0, n-i-1):

# traverse the array from 0 to n-i-1

# Swap if the element found is greater
# than the next element
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
Sorting and Searching Algorithm - Merge Sort
• Merge sort algorithm
• A divide and conquer method
• Divide a list into two smaller lists until the size of each list is one
• Repeatedly applying a method → recursion
• For each pair of lists, merge them in correct order of items
• Continue until you can produce the final sorted list
Sorting and Searching Algorithm - Merge Sort
• Example – in Ascending Order
def mergeSort(arr): # python
if len(arr) > 1:
mid = len(arr)//2 # Finding the mid of the array
L = arr[:mid] # Dividing the array elements
R = arr[mid:] # into 2 halves
mergeSort(L) # Sorting the first half
mergeSort(R) # Sorting the second half
i = j = k = 0
while i < len(L) and j < len(R): # Copy data to temp arrays L[] and R[]
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L): # Checking if any element was left
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
Sorting and Searching Algorithm - Linear Search
• Very basic and simple search algorithm
• Search an element in a given list by traversing the list from the starting
till the desired element is found
• Return the index and stop of the element if there is a match. Otherwise
return -1
FUNCTION LinearSearch (values[], target, n) {
FOR i FROM 0 TO n-1 DO
IF value[i] == target THEN
RETURN i
RETURN -1
END FOR
Sorting and Searching Algorithm - Binary Search
• A divide and conquer method
• Sorted list
• Select the median item of the list, check if it is equal to the target, stop
and return the index of the item
• If the median is too high, repeat the above step with the sub-list to the left
• If the median is too low, repeat the above step with the sub-list to the right
• Repeat the above step until you can find the target or otherwise return -1
Sorting and Searching Algorithm - Binary Search
FUNCTION BinarySearch (values[], len, target) {
max = len -1
min = 0

WHILE (max >= min) D)

(int) guess = (max + min) /2
IF value[guess] == target THEN
SEND guess TO DISPLAY
ELSE
IF value[guess] > target THEN
max = guess -1 // left half
ELSE
min = guess + 1//right half
END WHILE
RETURN -1
1.1 Algorithms
• 1.1.6 Understand how to code an algorithm in a high-level language.
• 1.1.7 Understand how the choice of algorithm is influenced by the
data structures and data values that need to be manipulated.
• 1.1.9 Be able to evaluate the fitness for purpose of algorithms in
meeting specified requirements efficiently, using logical reasoning
and test data.
1.2 Decomposition and Abstraction
• Computational thinking is the thought
processes involved in formulating
problems and their solutions so that
the solutions are represented in a
form that can be effectively carried
out by a computer
• Skills required for computational
thinking
• Algorithm design
• Decomposition
• Abstraction
Decomposition
• First step in the problem-solving process
• Break down a problem into smaller, more manageable sub-problems
which are easier to solve and algorithms can be developed to solve
each of them
• Advantages of decomposition
• Sub-problems can be worked on by different teams at the same time
• Easier to spot and correct errors / bugs
• Codes can be reused
Decomposition - Example
Abstraction
• The process of removing or hiding unnecessary detail so that only the
important points remain
• E.g. I was walking down the street when I saw a cat

• When we create algorithms, we abstract

the basic details of the problem and
represent them in a way that a computer
is able to process
Levels of Abstraction
• The higher the level of abstraction, the less detail is required

• E.g. when programmers write the ‘print’ command they do not have
to bother about all the details of how this will be accomplished

• E.g. a driver turning the ignition key to start a car does not have to
understand how the engine works or how the spark to ignite the
petrol is generated
Abstraction – Example – Noughts and Crosses
Question
• What is the purpose of the algorithm?
• Explain how the algorithm calculates the total amount
that should be paid?
• Give two variables that are used in the algorithm.
• Two of the constructs are labelled A and B. State the
type of each construct.
• The Wong family is visiting the park. The family
consists of two children, one ages 10 and one aged 5,
their two parents, an aunt and their grandfather, who is
aged 78. Use the algorithm to calculate how much the
family should have to pay for entry.