CHAPTER 9

Algorithm Design & Problem-Solving

Cambridge AS Level Computer Science 9618 · Paper 2

Syllabus section What you must be able to do

9.1 Computational Thinking Abstraction, decomposition, modular design

9.2 Algorithms Identifier tables, pseudocode (sequence/selection/iteration), flowcharts,

stepwise refinement, logic statements

9.1 Computational Thinking Skills

What is Abstraction?
Abstraction means removing unnecessary detail from a problem and keeping only what is essential to
solve it. You create a simplified model of the real world that the computer can work with.

• Purpose: To make complex problems manageable by hiding irrelevant detail.

• Benefit 1: Reduces complexity — easier to design and understand the solution.
• Benefit 2: Allows reuse — an abstract model can apply to many similar problems.
• Benefit 3: Helps identify what data and processes are actually needed.
• Benefit 4: Makes it easier to communicate the solution to others.

★ EXAM TIP: If the question says 'produce an abstract model', list ONLY the essential attributes/processes
needed. Cross out anything that isn't directly used in solving the problem. E.g. for a library system: you need
BookID, Title, BorrowerID — you do NOT need the colour of the book cover.

Abstraction — Worked Example

Real world object Unnecessary detail (remove) Essential detail (keep)

Car in a sat-nav system Colour, engine size, number of seats, fuel Current position (GPS), speed,
type direction

Student in a school Height, favourite colour, hobbies StudentID, Name, DOB, ClassID,
database Grades

Parking lot camera (AI) Car colour, driver's face, time of day Number plate characters, entry/exit
timestamp

What is Decomposition?
Decomposition means breaking a large problem into smaller sub-problems until each sub-problem is
simple enough to be solved individually. Each sub-problem becomes a procedure or function (a module)
in your program.

• Why decompose? Large problems are too complex to solve in one go.
• Result: Each module is independently written, tested, and debugged.
• Benefit 1: Easier to manage — different people can work on different modules.
 • Benefit 2: Modules can be reused in other programs.
• Benefit 3: Easier to test — test each module separately.
• Benefit 4: Makes stepwise refinement possible.

★ EXAM TIP: Decomposition questions often say 'describe how you would break this problem into
sub-problems'. Just name each sub-task and say it becomes a procedure/function. E.g. Login →
CheckPassword(), AddStudent(), GenerateReport() etc.

Decomposition — Example: School Report System

Main problem Sub-problems (modules)

Generate end-of-year school 1. GetStudentData() — read student records 2.

reports CalculateAverage() — compute subject averages 3.
AssignGrade() — determine A/B/C/D/E grade 4. PrintReport() —
format and output the report 5. SaveReport() — write to file

9.2 Algorithms
An algorithm is a solution to a problem expressed as a sequence of defined steps. Every step must be
unambiguous, finite, and lead to a result. In Paper 2, algorithms are written as pseudocode, described in
structured English, or drawn as flowcharts.

Identifier Tables
An identifier table lists every variable, constant, and parameter used in an algorithm. Cambridge expects
you to fill these in or create them from scratch. Every row must have: Identifier name, Data type,
Description/purpose.

Identifier Data Type Description

studentName STRING Full name of the student
score INTEGER Test score out of 100
average REAL Average score across all tests
isPassed BOOLEAN TRUE if student passed, FALSE otherwise
MAX_SCORE INTEGER Constant — maximum possible score (100)
grades ARRAY[1:30] OF INTEGER Stores scores for up to 30 students

★ EXAM TIP: Cambridge OFTEN gives you a half-complete identifier table and asks you to fill in missing
data types or descriptions. Common trap: confuse INTEGER and REAL. If a value can be a decimal (e.g.
average, price) use REAL. If whole numbers only, use INTEGER.

Data Types — Quick Reference

Data Type What it stores Example value
INTEGER Whole numbers (positive/negative/zero) 42, -7, 0

REAL Numbers with decimal points 3.14, -0.5, 100.0

CHAR A single character 'A', '5', '!'

STRING A sequence of characters (text) 'Hello', 'Ahmed123'

BOOLEAN TRUE or FALSE only TRUE, FALSE

DATE A calendar date 01/01/2026

ARRAY Collection of same data type ARRAY[1:10] OF INTEGER

FILE Reference to a file on disk Used with OPENFILE etc.

 9.2 Three Basic Constructs of Pseudocode
Every algorithm is built from exactly three constructs: Sequence, Selection, and Iteration. You must be
able to write, read, and trace all of them.

1. Sequence
Instructions execute one after another in the order written. No branching, no repeating.

DECLARE name : STRING

DECLARE score : INTEGER

INPUT name

INPUT score

OUTPUT name, ' scored ', score

2. Selection — IF and CASE

The program makes a decision and follows one path or another.

IF statement:

IF score >= 50

THEN

OUTPUT 'Pass'

ELSE

OUTPUT 'Fail'

ENDIF

Nested IF (check multiple grades):

IF score >= 90

THEN OUTPUT 'A'

ELSE IF score >= 70

THEN OUTPUT 'B'

ELSE IF score >= 50

THEN OUTPUT 'C'

ELSE OUTPUT 'Fail'

ENDIF

ENDIF

ENDIF

CASE statement (cleaner for many fixed options):

CASE OF grade

'A' : OUTPUT 'Excellent'

'B' : OUTPUT 'Good'

 'C' : OUTPUT 'Pass'

OTHERWISE : OUTPUT 'Fail'

ENDCASE

★ EXAM TIP: Use CASE when selecting from a fixed set of known values (e.g. menu options, grades). Use
IF when testing a range or condition (e.g. score > 50). Cambridge deducts marks if you use the wrong one.

3. Iteration — Three loop types

Repetition. Three loop types — you must know when to use each one.

Loop type When to use Pseudocode

FOR (count-controlled) When you know EXACTLY how many FOR i ← 1 TO 10 ... NEXT i
times to repeat

WHILE (pre-condition) Check condition BEFORE entering loop. WHILE count < 10 DO ... ENDWHILE
May never run if condition is false from
start.

REPEAT UNTIL Check condition AFTER. Always runs AT REPEAT INPUT value UNTIL value >
(post-condition) LEAST ONCE. Good for input validation. 0

★ EXAM TIP: Past papers LOVE asking 'justify why one loop is more suitable than another'. If the question
involves input validation (keep asking until valid input), always say REPEAT UNTIL because the loop must
run at least once. If the count is known, say FOR.

Full Pseudocode Example — Typical Paper 2 Style

Scenario: A program reads 10 student scores, calculates the average, and outputs whether each student
passed (score >= 50).

DECLARE scores : ARRAY[1:10] OF INTEGER

DECLARE total : INTEGER

DECLARE average : REAL

DECLARE i : INTEGER

total ← 0

FOR i ← 1 TO 10

OUTPUT 'Enter score for student ', i

INPUT scores[i]

total ← total + scores[i]

NEXT i

average ← total / 10

OUTPUT 'Class average: ', average

FOR i ← 1 TO 10

IF scores[i] >= 50
THEN OUTPUT 'Student ', i, ' : Pass'

ELSE OUTPUT 'Student ', i, ' : Fail'

ENDIF

NEXT i
 9.2 Flowcharts
Shape Name Used for

Oval / Rounded rect Terminal START and END of the algorithm

Parallelogram Input / Output INPUT or OUTPUT a value

Rectangle Process Assignment, calculation, any action

Diamond Decision Any YES/NO or TRUE/FALSE condition (IF, WHILE, REPEAT)

Arrow / Flow line Flow line Direction of execution

★ EXAM TIP: In a flowchart, the DECISION diamond always has exactly TWO exits labelled YES/NO or
TRUE/FALSE. A WHILE loop draws the arrow back BEFORE the process box. A REPEAT UNTIL draws the
arrow back AFTER the process box (the check is at the bottom).

■ WATCH OUT: Never use a rectangle for input/output. Cambridge will mark it wrong. Never use a diamond
for a calculation.

Reading a Flowchart — What to Look For

When Cambridge gives you a flowchart and asks you to write pseudocode from it:

• Start at the START terminal and trace every path.

• Every diamond becomes an IF, WHILE or REPEAT UNTIL depending on where the arrow loops back.
• If the arrow loops back to BEFORE the diamond → WHILE loop.
• If the arrow loops back to AFTER a process but BEFORE the diamond → REPEAT UNTIL.
• If there is no loop — just two paths that rejoin → IF / ELSE.
• Every parallelogram becomes INPUT or OUTPUT.
• Every rectangle becomes an assignment or calculation.

9.2 Structured English

Structured English is a halfway point between plain English and pseudocode. It uses English words but
with a structured format that maps directly to code. Cambridge uses it to describe an algorithm WITHOUT
requiring exact syntax.

Example — structured English for a login system:

Step 1: Get username and password from user

Step 2: Check if username exists in the database

Step 3: If it does, compare entered password with stored password

Step 4: If passwords match, grant access

Step 5: Otherwise, output 'Invalid login' and return to Step 1

Step 6: After 3 failed attempts, lock the account

The same algorithm in pseudocode:

DECLARE attempts : INTEGER

attempts ← 0
REPEAT

INPUT username

INPUT password

IF username = storedUsername AND password = storedPassword

THEN

OUTPUT 'Access granted'

attempts ← 3 // force exit

ELSE

attempts ← attempts + 1

OUTPUT 'Invalid login'

ENDIF

UNTIL attempts >= 3

IF attempts = 3 AND password <> storedPassword

THEN OUTPUT 'Account locked'

ENDIF
 9.2 Stepwise Refinement
Stepwise refinement is the process of starting with a high-level description of an algorithm and
progressively breaking it into more detailed steps until each step is specific enough to be directly
programmed. It combines decomposition with increasing detail.

How Stepwise Refinement Works

Level 1 — Very high level (almost plain English):

1. Get data

2. Process data

3. Output results

Level 2 — Slightly more detail:

1. Get data

1.1 Open the file

1.2 Read each record until end of file

1.3 Store each record in an array

2. Process data

2.1 Calculate total of all values

2.2 Calculate average

2.3 Find maximum value

3. Output results

3.1 Display average

3.2 Display maximum

3.3 Close file

Level 3 — Pseudocode (fully programmable):

OPENFILE '[Link]' FOR READ

DECLARE values : ARRAY[1:100] OF REAL

DECLARE count, i : INTEGER

DECLARE total, average, maxVal : REAL

count ← 0

total ← 0

WHILE NOT EOF('[Link]') DO

count ← count + 1

READFILE '[Link]', values[count]

ENDWHILE

maxVal ← values[1]

FOR i ← 1 TO count
 total ← total + values[i]

IF values[i] > maxVal THEN maxVal ← values[i]

NEXT i

average ← total / count

OUTPUT 'Average: ', average

OUTPUT 'Maximum: ', maxVal

CLOSEFILE '[Link]'

★ EXAM TIP: If Cambridge asks you to 'use stepwise refinement to express the algorithm', literally show two
or three levels. Start very vague, then add detail at each level. Show the PROCESS not just the final
pseudocode.

9.2 Logic Statements in Algorithms

Logic statements use Boolean operators to define conditions in an algorithm. Cambridge expects you to
use AND, OR, NOT correctly in pseudocode conditions.

Operator Meaning Example in pseudocode True when...

AND Both conditions must be IF age >= 18 AND hasID = TRUE Age is 18+ AND has ID
true
OR At least one condition IF score < 0 OR score > 100 Score is negative OR
must be true over 100
NOT Reverses the condition IF NOT isLoggedIn User is NOT logged in

Comparison Operators — Must Know These Exactly

Symbol Meaning Example

= Equal to IF name = 'Ahmed'

<> Not equal to IF password <> storedPwd

< Less than IF age < 18

> Greater than IF score > 50

<= Less than or equal to IF attempts <= 3

>= Greater than or equal to IF grade >= 70

← Assignment (give a value TO a variable) total ← total + 1

■ WATCH OUT: The most common error in Paper 2: using = for assignment instead of ←. Cambridge WILL
deduct marks. Assignment is always ←. = is ONLY used in comparisons (IF x = 5).
 Past Paper Patterns — Chapter 9 Questions
These are the question types from Chapter 9 that appear in 9618 Paper 2 (2021–2024). Every one of
these has appeared at least once:

Question type Marks What they want

Complete the identifier table 3–4 Fill in missing identifier names, data types, or descriptions. Check
every variable is declared.

Find the error in the 2–4 Wrong operator (= instead of ←), wrong data type, off-by-one in
pseudocode loop bounds, wrong loop type used.

Write pseudocode from 4–8 Translate step-by-step English into correct pseudocode syntax.
structured English Watch: loops, conditions, correct arrows.

Draw a flowchart from 4–6 Correct shapes for each construct, arrows looping correctly for
pseudocode iteration, YES/NO labels on diamonds.

Write pseudocode from a 4–6 Trace the flowchart and reproduce it in pseudocode. Identify loop
flowchart type from where the arrow goes back.

Describe the algorithm in 3–5 Use numbered steps, plain language. Do NOT write pseudocode
structured English unless asked. Just describe what happens.

Stepwise refinement 4–6 Show at least two levels. Start high-level, then add detail. Final level
should be close to pseudocode.

Justify choice of loop / selection 1–2 Say which type and WHY. E.g. 'REPEAT UNTIL because the loop
type must run at least once'.

Chapter 9 — The 10 Things You Must Know Cold

1 Abstraction = remove unnecessary detail, keep only essential.

2 Decomposition = break into sub-problems → each becomes a procedure/function.

3 Algorithm = sequence of defined steps to solve a problem.

4 Identifier table has: name, data type, description. ALWAYS.

5 Assignment uses ← not =. Comparison uses =. Wrong one = lost marks.

FOR = known count. WHILE = check before (may not run). REPEAT UNTIL = check after (always
6
runs once).

7 REPEAT UNTIL is best for input validation — always say this in justification questions.

8 Flowchart shapes: oval=start/end, parallelogram=I/O, rectangle=process, diamond=decision.

9 Stepwise refinement: show multiple levels going from vague to detailed. Show the PROCESS.

10 Logic operators: AND (both true), OR (one true), NOT (reverses). Use them in IF conditions.

★ EXAM TIP: Paper 2 gives you an INSERT with pseudocode functions and operators. Read it at the start of
the exam. Never use syntax from memory when the insert is right there. Common functions you will see:
LENGTH(), SUBSTRING(), LCASE(), UCASE(), DIV (integer division), MOD (remainder), INT() (round
down).