CAIE 9618 · Paper 2 · Topic 2.1.1

Algorithm Design &
Problem Solving

Decomposition · Abstraction · Stepwise Refinement · Structure Charts

CSZone Cambridge International AS & A Level Computer Science 9618

What is an Algorithm?

Precise Steps to Solve a Problem

An algorithm is a finite, ordered set of unambiguous instructions that, when followed, solves a problem or achieves a task. Algorithms must: terminate, produce the correct output for all valid inputs, and handle edge cases.

PROPERTIES OF A GOOD ALGORITHM

Correct — produces right output. Efficient — uses minimal time/memory. Clear — unambiguous steps. Finite — always terminates. General — works for all valid inputs.

REPRESENTATIONS

Pseudocode — structured English-like notation. Flowchart — visual diagram using standard symbols. Structure chart — hierarchical decomposition. Program code — actual implementation.

Decomposition

Breaking a Problem Down

Decomposition is breaking a large, complex problem into smaller, more manageable sub-problems that can be solved independently and then combined.

Makes complex problems manageable — each sub-problem is smaller and easier to solve

Enables parallel development — different team members work on different sub-problems simultaneously

Promotes reusability — sub-solutions (procedures/functions) can be reused across the project

Simplifies testing — each module tested independently before integration

Example: "Build a school library system" → decompose into: Add book, Remove book, Search catalogue, Issue book, Return book, Generate report

Abstraction

Focusing on What Matters

Abstraction is the process of removing or hiding unnecessary detail to focus on the important aspects of a problem. This creates a simplified model that is easier to work with.

REPRESENTATIONAL ABSTRACTION

Representing real-world objects with only the relevant features. A map omits 3D detail but keeps roads and distances. A queue data structure hides the array implementation.

ABSTRACTION BY GENERALISATION

Grouping similarities to create a common solution. A SORT algorithm is a generalised solution — it works regardless of whether you're sorting names, prices, or scores.

Layers of abstraction: High-level code (Python) → Assembly → Machine code → Logic gates → Transistors. Each layer hides complexity from the layer above.

Stepwise Refinement

Top-Down Design

Stepwise refinement (top-down design) starts with a high-level outline of a solution and progressively adds more detail at each step until the level of individual programming instructions.

STEP 1 — HIGH LEVEL

Solve the quiz game

STEP 2 — REFINE

Load questions → Ask questions → Mark answers → Show score

STEP 3 — FURTHER REFINE

"Ask questions": FOR each question, display text, read answer, compare to key, increment score if correct

STRUCTURE CHARTS

A structure chart shows the hierarchical relationship between modules. Top = main program. Each level = sub-modules. Arrows show data flow. Used to visualise decomposition graphically.

Algorithm Efficiency

Time and Space Complexity

Efficiency measures how algorithm performance scales as input size (n) grows. Expressed as Big-O notation:

O(1) — CONSTANT

Time doesn't depend on n. e.g. Accessing array element by index.

O(log n) — LOGARITHMIC

Halves problem each step. e.g. Binary search.

O(n) — LINEAR

One operation per item. e.g. Linear search.

O(n²) — QUADRATIC

Nested loops over n items. e.g. Bubble sort, selection sort.

O(n log n) — LINEARITHMIC

Divide and conquer. e.g. Merge sort, quicksort.

Exam Practice

Cambridge-style questions

Question 1

Explain what is meant by "decomposition" in algorithm design. Give one benefit of using decomposition when developing a large software system.

3 marks

2 marks

Decomposition is breaking a large, complex problem down into smaller, more manageable sub-problems (1), each of which can be solved independently and then combined to form the complete solution (1).

1 mark

Benefit: allows different team members to work on different sub-problems in parallel (1) OR allows each module to be tested independently before integration (1).

Common Mistakes

Don't lose easy marks

1

Confusing abstraction and decomposition — decomposition is breaking a problem into smaller parts. Abstraction is hiding unnecessary detail. They are related but distinct: you often use decomposition first, then abstraction to simplify each sub-problem.

2

Saying an algorithm is just "a set of steps" — for the Cambridge exam you need to say it is a finite, ordered, unambiguous set of instructions. Missing "unambiguous" or "finite" can cost a mark on definition questions.

3

Confusing efficiency with speed — O(n²) is less efficient than O(n log n) not simply "slower". Efficiency describes how performance scales with input size, not just absolute speed. A fast computer running O(n²) can still be slower than a slower computer running O(log n) for large n.

Topic Summary — 2.1.1

What You Need to Know

ALGORITHM

Finite, ordered, unambiguous instructions
Must terminate and produce correct output
Representations: pseudocode, flowchart, structure chart

DECOMPOSITION & ABSTRACTION

Decomposition: break into sub-problems
Abstraction: remove unnecessary detail
Stepwise refinement: top-down progressive detail

EFFICIENCY (BIG-O)

O(1) < O(log n) < O(n) < O(n log n) < O(n²)
Binary search: O(log n)
Linear search: O(n)
Bubble sort: O(n²) · Merge sort: O(n log n)

CSZone

Next Video

2.1.2

Pseudocode & Programming Constructs

CAIE Pseudocode Standard · Selection · Iteration

Head to CSZone.co.uk for the complete worksheet, quiz, and interactive tools