2.1.1 Problem Solving and Algorithms — Cambridge 9618

What is an Algorithm?

An algorithm is a precise, step-by-step set of instructions for solving a problem or completing a task in a finite number of steps. Every algorithm must:

Have clear inputs and outputs — what data goes in and what result comes out
Be unambiguous — each step must be precisely defined with no room for misinterpretation
Be finite — must terminate after a finite number of steps (never loop forever)
Be correct — must produce the correct output for all valid inputs
Be general — works for the full class of problem, not just one specific example

Problem-Solving Stages

Cambridge 9618 uses a structured approach to computational problem-solving:

Understand the problem — identify inputs, outputs, and constraints. What must the solution do? What are the edge cases?

Decompose the problem — break it into smaller, manageable sub-problems. Each sub-problem can be solved independently.

Identify the algorithm design — choose an appropriate algorithmic approach (e.g., linear search, binary search, sorting, recursion).

Represent the algorithm — express it as pseudocode, flowchart, or structure diagram.

Trace and test — dry-run the algorithm manually using a trace table; check all paths work correctly.

Implement and refine — code it up and refine based on testing results.

Abstraction

Abstraction is the process of removing or hiding unnecessary detail to focus on what is important for solving the problem. It allows complex real-world problems to be represented in a manageable way.

Example: when designing an algorithm to find the shortest route between two cities, we abstract the real world to a graph — cities become nodes, roads become weighted edges. The actual geography, traffic signals, and roadworks are stripped away.

Decomposition

Decomposition means breaking a complex problem into smaller sub-problems that are easier to solve. Each sub-problem can then be solved, coded, and tested independently, then combined. This is the foundation of modular programming.

Example decomposition of a school management system:

Student records management
Timetable scheduling
Attendance tracking
Exam results processing

Each of these can be further decomposed into smaller procedures.

Cambridge 9618 Pseudocode

Cambridge 9618 uses a specific pseudocode style. Key conventions:

Assignment: ← (e.g., x ← 5)
Comparison: = (e.g., IF x = 5)
Output: OUTPUT
Input: INPUT
For loops: FOR i ← 1 TO 10 ... NEXT i
While loops: WHILE condition DO ... ENDWHILE
Repeat loops: REPEAT ... UNTIL condition
Procedures: PROCEDURE name(params) ... ENDPROCEDURE
Functions: FUNCTION name(params) RETURNS type ... ENDFUNCTION

Example — Find the Maximum of N Numbers

DECLARE n : INTEGER
DECLARE i : INTEGER
DECLARE num : REAL
DECLARE maxVal : REAL

INPUT n
INPUT maxVal

FOR i ← 2 TO n
    INPUT num
    IF num > maxVal
        THEN maxVal ← num
    ENDIF
NEXT i

OUTPUT "Maximum is: ", maxVal

Trace Tables

A trace table is used to manually execute (dry-run) an algorithm, recording the value of each variable at each step. Used to:

Verify an algorithm is correct
Identify bugs (logic errors)
Show the intermediate values during execution

Cambridge exam questions often ask you to complete a trace table for a given algorithm — you must show each variable's value changing as each instruction executes.

Algorithm Characteristics

Property	Meaning	Why it matters
Correctness	Produces correct output for all valid inputs	An incorrect algorithm is useless however fast it runs
Efficiency	Uses minimal time and memory resources	Poor efficiency fails at scale (billions of inputs)
Clarity	Easy to read, understand and maintain	Real software must be maintained by teams over years
Generality	Works for the full problem class, not just one example	A solution for only one specific input is not useful
Finiteness	Terminates in a finite number of steps	An infinite loop is not an algorithm

Exam tip: In Cambridge 9618 Paper 2, you will regularly need to write pseudocode using Cambridge's exact notation (←, FOR/NEXT, WHILE/ENDWHILE, etc.), complete trace tables, and explain algorithm design decisions. Practice writing pseudocode by hand — the exam is not on a computer.

⚠️ Common Mistakes

Using = for assignment — Cambridge uses ← for assignment and = only for comparison
Confusing abstraction and decomposition — abstraction removes unnecessary detail; decomposition breaks a problem into sub-problems
Saying an algorithm "always terminates" — it must terminate; if it has a loop, you must ensure the loop condition is eventually met
Incomplete trace tables — show every step, including unchanged variables, exactly as Cambridge mark schemes require

✅ Notes completed!

▶

Video coming soon

Click slide or press arrow keys to navigate

Worksheet — 2.1.1 Problem Solving and Algorithms

6 questions · instantly marked · Cambridge 9618 standard

Q1State four properties that every algorithm must have.[4]

✅ Mark scheme

Any four: correct (produces correct output for all valid inputs) [1]; finite (terminates in a finite number of steps) [1]; unambiguous (each step precisely defined) [1]; general (works for the full class of problem) [1]; has clear inputs and outputs [1].

Q2Distinguish between abstraction and decomposition in problem-solving. Give an example of each.[4]

✅ Mark scheme

Abstraction: removing unnecessary detail to focus on relevant aspects of a problem [1]; e.g., representing a road network as a graph (nodes and edges) ignoring traffic signals [1]; Decomposition: breaking a complex problem into smaller, manageable sub-problems [1]; e.g., breaking a school system into student records, timetabling, attendance [1].

Q3A student writes the following pseudocode but it contains two errors. Identify both errors.

FOR i = 1 TO 5
  total = total + i
END FOR

[2]

✅ Mark scheme

Error 1: assignment uses = instead of ← — should be total ← total + i [1]; Error 2: loop counter variable i should use ← not = — should be FOR i ← 1 TO 5 [1]; Error 3 (bonus): loop terminator should be NEXT i not END FOR [1] (accept any 2 of these 3).

Q4Explain what a trace table is and why it is used.[3]

✅ Mark scheme

A trace table records the value of each variable at each step of an algorithm as it is manually executed (dry run) [1]; it is used to verify that the algorithm produces the correct output [1]; and to identify logic errors by showing intermediate variable values [1].

Q5Write Cambridge 9618 pseudocode to calculate the sum of all even numbers from 2 to 100.[4]

✅ Mark scheme

DECLARE total : INTEGER [1];
total ← 0 [1];
FOR i ← 2 TO 100 STEP 2 [1];
total ← total + i;
NEXT i;
OUTPUT total [1].
(Accept loop with MOD check as alternative for step award.)

Q6A problem-solving approach involves six stages. Describe what happens in stage 2 (decomposition) and explain why it is important.[3]

✅ Mark scheme

Decomposition involves breaking a complex problem down into smaller, simpler sub-problems [1]; each sub-problem can be solved, coded and tested independently [1]; it is important because large problems become manageable — teams can work on different modules simultaneously and modules can be reused [1].

Q7A structure chart is being designed for a program that: reads a list of student scores, calculates the average, identifies the highest score, and outputs a formatted report. Draw a structure chart by listing the top-level module and its sub-modules. Indicate any modules that are reused (called more than once).[4]

✅ Mark scheme

Top-level module: Process Student Results [1]; Sub-modules: Read Scores, Calculate Average, Find Highest Score, Output Report [1]; Read Scores may call a Read Single Score module repeatedly — indicated as a reused/looped module with a circular arrow [1]; correct hierarchical relationship — top module calls each sub-module in sequence, sub-modules do not call each other [1].

Q8Explain the concept of stepwise refinement in algorithm design. Using the problem "sort a list of names alphabetically and print them", show two levels of refinement, making the algorithm more detailed at each step.[4]

✅ Mark scheme

Stepwise refinement: breaking a high-level problem into smaller, more manageable sub-problems, refining each further until each step is simple enough to implement directly [1]; Level 1: (1) Get list of names, (2) Sort names, (3) Print names [1]; Level 2 refinement of Sort: (2.1) Compare adjacent names, (2.2) If out of order, swap them, (2.3) Repeat until no swaps needed [1]; Level 2 refinement of Print: (3.1) FOR each name in sorted list, (3.2) OUTPUT name [1].

Topic Quiz

Question 1 of 10

You scored

out of 10

Card 1 of 6

Click to reveal definition

🎉

All cards reviewed!

Term	Definition

What is an Algorithm?

Problem-Solving Stages

Abstraction

Decomposition

Cambridge 9618 Pseudocode

Example — Find the Maximum of N Numbers

Trace Tables

Algorithm Characteristics

Worksheet — 2.1.1 Problem Solving and Algorithms

Mini Test — 2.1.1 Problem Solving