1.

UNDERSTANDING ALGORITHMS
This section focuses on defining algorithms,
understanding their purpose, and exploring various ways
to represent them.
What is an Algorithm? An algorithm is a precise method
for solving a problem. It is a set of clear, step-by-
step instructions designed to achieve a specific
result. Algorithms are fundamental to computer
programming and form the basis of computer programs.
Characteristics of a Successful Algorithm When
evaluating whether an algorithm is successful, three
key points are considered:
 Accuracy: It must consistently lead to the
expected outcome (e.g., creating a route from
Beijing to Shanghai).
 Consistency: It must produce the same result each
time it is run with the same inputs.
 Efficiency: It must solve the problem in the
shortest possible time, using as few computer
resources as possible.
An algorithm should also be:
 Unambiguous: Instructions must be clear and
cannot be misunderstood. For example, "turn left"
is unambiguous, while "turn" is not.
 A sequence of steps.
 Reusable and will always provide the same result
for the same problem.
 A solution to a problem.
Relationship Between Algorithms and Programs Algorithms
and programs are closely related but distinct.
  An algorithm is the detailed design for a
solution. It's the logical sequence of steps to
solve a problem.
 A program is when that design is implemented
using a specific programming language, making it
executable by a computer. A well-written
algorithm should be free of logic errors and easy
to code in any high-level language.
Ways to Display an Algorithm Algorithms can be
expressed in various ways to make them understandable.
1. Written Descriptions
 This is the simplest way to express an algorithm,
using natural language to list the steps.
 Example: Algorithm for Making a Cup of Coffee
▪ Fill kettle with water.
▪ Turn on kettle.
▪ Place coffee in cup.
▪ Wait for water to boil.
▪ Pour water into cup.
▪ Add milk and sugar.
▪ Stir.
2. Flowcharts
 Flowcharts use diagrams with special symbols to
show an algorithm visually and represent its
logical flow.
 Standard Flowchart Symbols:
▪ Rectangle: Indicates a process or action to
be carried out.
▪ Diamond: Indicates a decision to be made.
 ▪ Parallelogram: Indicates an input or output.
▪ Oval/Rounded Rectangle: Indicates the start
or end of an algorithm.
▪ Arrows: Show the logical flow of the
algorithm and the order of steps.
◦ Example: Flowchart for Making a Cup of Coffee
▪ (Start) → Fill kettle with water → Turn on
kettle → Place coffee in cup → (Wait for kettle to
boil) → Pour water into cup → Add milk and sugar → Stir
→ (End).
▪ The instruction "Wait for kettle to boil" is
unambiguous, meaning the water must be boiling, unlike
"wait for the water to heat".
3. Pseudocode
 Pseudocode is a structured, code-like language
used to describe an algorithm. It resembles
programming code but is not tied to any specific
language.
 ◦ Purpose: It allows developers to
concentrate on the logic and efficiency of the
algorithm without worrying about the strict
syntax rules of a particular programming
language. It is relatively straightforward to
translate pseudocode into any high-level
programming language.
◦ Key Concepts in Pseudocode:
▪ Variables and Identifiers: Variables are
'containers' used to store data, and their values can
change during program execution. Constants are
'containers' that hold values that remain fixed. Each
variable and constant needs a unique, descriptive
identifier to make the code easier to read (e.g.,
firstName instead of X). Common naming conventions
include 'camel case' (firstName) or 'snake case'
(first_name).
▪ Text (Strings): Text to be displayed is
typically placed in quotation marks (single or double).
Variable names are not put in quotation marks when
their value is to be displayed.
▪ Arithmetic Operators: These are characters
that perform calculations on numbers.
• Table 1.1: Arithmetic Operators
◦ +: Addition (e.g., 8 + 5 = 13)
◦ -: Subtraction (e.g., 17 - 4 = 13)
◦ *: Multiplication (e.g., 6 * 9 = 54)
◦ /: Real division (returns result with
decimal places, e.g., 13 / 4 = 3.25)
◦ DIV (Quotient): Returns only the
whole number part of a division (e.g., 13 DIV 4 = 3)
◦ MOD (Modulus/Modulo): Returns the
remainder of a division (e.g., 13 MOD 4 = 1)
◦ ^: Exponentiation (to the power of,
e.g., 3 ^ 3 = 27)
◦ Example: Algorithm for Adding Two Numbers
▪ Written Description:
• Enter first number.
• Enter second number.
• Calculate total by adding first and
second numbers.
 • Output total.
▪ Flowchart:
• (Start) → Input first number → Input
second number → Total = first number + second number →
Output total → (End).
▪ Pearson Edexcel Pseudocode:
• 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
-------------------------------------------------------
-------------------------
2. CREATING ALGORITHMS
This section delves into how algorithms are
constructed, particularly for computer execution,
introducing fundamental programming constructs.
Algorithms for Computers Unlike humans who can infer
meaning, computers are "mindless machines" that follow
instructions exactly. Therefore, algorithms for
computers must be explicit and unambiguous. For
instance, a human understands "Wait for water to boil"
by repeatedly checking, but a computer needs specific
conditions (e.g., "wait until the water reached
100°C").
Basic Constructs of Algorithms Algorithms are created
using three basic constructs:
1. Sequence
◦ This refers to step-by-step instructions in the
correct order. Most simple algorithms begin with a
sequence of commands.
2. Selection
◦ Selection (or conditional statement) allows a
choice to be made between different alternatives based
on a condition.
◦ It is often represented by an IF...THEN...ELSE
statement.
◦ Flowchart Representation: A diamond symbol with
two outgoing paths labeled 'YES' and 'NO' represents a
decision, leading to different sequences of actions.
◦ Example (Pseudocode):
▪ IF day = ‘Saturday’ OR day = ‘Sunday’ THEN
▪ SET alarm TO 11
▪ ELSE
▪ SET alarm TO 8
▪ END IF
3. Iteration (Loops)
◦ Iteration means a process is repeated. An action
is repeated until a condition is met or a particular
outcome is reached. It is often referred to as a
'loop'.
◦ Flowchart Representation: Arrows that loop back
to a decision symbol indicate iteration, where a
question is repeated until the desired outcome is
achieved.
◦ Types of Loops:
▪ Definite Loops: Used when the number of
repetitions is known in advance. In Pearson Edexcel
pseudocode, these can be REPEAT...END REPEAT or
FOR...END FOR loops.
• REPEAT 50 TIMES SEND ‘*’ TO DISPLAY END
REPEAT
• FOR times FROM 1 TO 100 DO SEND ‘*’ TO
DISPLAY END FOR
▪ Indefinite Loops: Used when the number of
repetitions is not known in advance. They repeat until
a specified condition is reached. WHILE loops are
common for indefinite iteration.
• SET counter TO 10
• WHILE counter > 0 DO
• SEND counter TO DISPLAY
• SET counter TO counter - 1
• END WHILE
◦ Everyday Examples of Iteration: Eating until a
plate is empty, waiting for traffic lights to change,
an actor repeating lines.
-------------------------------------------------------
-------------------------
3. SORTING AND SEARCHING ALGORITHMS
This section explores common algorithms used for
organizing and finding data efficiently.
Importance of Sorting and Searching In computer
programs, sorting and searching are crucial tasks,
especially with millions of data items. Sorted data
makes searching much more efficient, similar to how an
alphabetical dictionary or time-ordered train timetable
is more useful.
Sorting Algorithms Many algorithms exist for sorting
data, with varying efficiencies. Data items are
compared and moved to achieve either ascending order
(smallest to largest) or descending order (largest to
smallest).
1. Bubble Sort
◦ Method: This algorithm starts at one end of a
list and repeatedly compares adjacent pairs of data
items. If they are in the wrong order (e.g., for
ascending sort, the first is larger than the second),
they are swapped. This comparison and swapping process
continues to the end of the list, completing a 'pass'.
The entire process is repeated until a pass occurs with
no swaps, indicating the list is fully sorted.
◦ Logic: Larger items "bubble up" to their correct
position at the end of the list after each pass.
◦ Flowchart representation: Involves loops and
decisions to compare and swap elements.
◦ Efficiency: Bubble sort uses a brute force
approach, repeating the same task. It is generally
slower for lists of more than 1000 items but might be
acceptable for smaller lists (less than 1000 items) due
to its simpler coding. A computer would need an extra
pass to confirm no swaps were made, even if a human
could visually see the list was sorted earlier.
2. Merge Sort
 ◦ Method: Merge sort uses a divide and conquer
method. It works by dividing a list into two smaller
lists and continues dividing these sub-lists
recursively until the size of each list is one. Once
individual items are in lists of size one (which are
inherently sorted), these single-item lists are then
merged back together in the correct sorted order. This
process is repeated until the entire original list is
sorted.
◦ Recursion: The process of repeatedly applying a
method to the results of a previous application of that
method.
◦ Efficiency: Merge sort is one of the most
efficient sorting algorithms. The graph comparing
performance shows that merge sort is significantly
faster than bubble sort for lists with many items.
Searching Algorithms These algorithms are used to find
specific items within a list.
1. Linear Search (Sequential Search)
◦ Method: This is a simple and straightforward
algorithm. It starts at the beginning of the list and
checks each item, one by one, in sequence. It continues
until it finds the item it is looking for or reaches
the end of the list without finding it.
◦ Efficiency:
▪ Best case: The item is the first one in the
list (1 comparison).
▪ Worst case: The item is the last one in the
list or not present (up to n comparisons for n items).
 ◦ When to use: A linear search is preferable if the
list is to be searched just once, especially if it's
unsorted.
2. Binary Search
◦ Method: Like merge sort, a binary search uses a
divide and conquer method. It works by repeatedly
selecting the median (middle item) of the list to
reduce the search space.
◦ Prerequisite: The list must be sorted into
ascending or descending order for a binary search to
work.
◦ Steps:
1. Select the median item of the list.
2. If the median item is the search item, stop.
3. If the median is too high, repeat steps 1
and 2 with the sub-list to the left of the median.
4. If the median is too low, repeat steps 1 and
2 with the sub-list to the right of the median.
5. Repeat until the item is found or all items
have been checked.
◦ Efficiency:
▪ Best case: The item is in the median position
(1 comparison).
▪ Worst case: For a list of 1000 items, it
would take a maximum of ten comparisons. This is far
more efficient than a linear search for large lists.
◦ When to use: A binary search is better for a
large list that will be searched many times, as the
initial cost of sorting the list is offset by the
efficiency of subsequent searches.
-------------------------------------------------------
-------------------------
4. DECOMPOSITION AND ABSTRACTION
This section introduces two critical thought processes
within computational thinking that help computer
scientists tackle complex problems.
Computational Thinking Computational thinking is the
approach computer scientists use to solve problems,
making solutions executable by a computer. Beyond
algorithm design, it includes decomposition and
abstraction as key skills.
Decomposition
• Definition: Decomposition is the process of breaking
a large problem down into smaller, more manageable
parts (sub-problems). This is usually the first step in
problem-solving.
• Benefits:
◦ Easier to solve: Smaller problems are less
daunting and easier to understand.
◦ Parallel work: Different sub-problems can be
worked on by different teams simultaneously.
◦ Easier error correction: Errors are easier to
spot and correct in smaller algorithms.
◦ Code reuse: Algorithms developed for sub-problems
can often be reused.
• Example: Creating a 'Noughts and Crosses' (Tic-Tac-
Toe) Game
◦ A large problem like creating a game can be
decomposed into sub-problems such as:
▪ Designing the 3x3 grid interface.
 ▪ Keeping track of selected squares.
▪ Deciding the computer's moves.
▪ Determining when the game is over and who
won.
Abstraction
• Definition: Abstraction is the process of removing or
hiding unnecessary detail so that only the important
points or essential features remain. This simplifies a
problem, making it easier to understand and solve.
• Levels of Abstraction: There are different levels;
higher levels require less detail. For instance, when
using a 'print' command, a programmer doesn't need to
know the intricate details of how the printer
physically works.
• Everyday Examples:
◦ When someone says "cat" or "street," you form a
general mental image, abstracting the essential
features without needing every minute detail of that
specific cat or street.
◦ Starting a car by turning a key is an
abstraction; the driver doesn't need to understand the
complex mechanics of the engine.
• Computer Science Examples (Modelling Real-World
Events):
◦ When creating algorithms, computer scientists
abstract the basic details of a problem to represent
them in a way a computer can process.
◦ Virtual Dice: In a computer game requiring a die
roll, the programmer abstracts the essential feature of
a die (selecting a random number from 1 to 6) and
implements this as a routine, rather than simulating
the physical act of rolling. This is a computer model
or simulation of a real-life event.
◦ Noughts and Crosses Game (Continued): After
decomposition, abstraction helps in defining the
inputs, outputs, and processing needed at a high level.
▪ Inputs: Start game, user entries, choice to
play again/finish.
▪ Outputs: Messages for user's turn, invalid
square selection, draw, winner, play again prompt.
▪ Processing and Initialisation: Setting up the
grid, initialising variables, computer's move logic,
checking for wins/draws.
▪ These processes can be further abstracted
into subprograms (self-contained modules of code) like
computerEntry, checkIfWon, or checkDraw, reducing
complexity and promoting code reuse.