Algorithm design and problem-solving
Cambridge AS & A Level Computer Science 9618 · Paper 2 · Unit 9
Paper 2 · Unit 9. Computational thinking, expressing algorithms, stepwise refinement and trace tables.
1. Computational thinking
Abstraction removes unnecessary detail so only the key features of a problem are kept, making it simpler to solve (e.g. a map shows roads, not every building). Decomposition breaks a problem into smaller sub-problems that can be solved separately, often as modules or subroutines.
2. Ways to express an algorithm
| Method | Description |
|---|---|
| Structured English | A restricted, numbered set of English statements using keywords like IF, REPEAT, OUTPUT |
| Flowchart | Diagram using standard symbols: terminator, process, input/output, decision, arrows |
| Pseudocode | Language-independent code using Cambridge keywords (DECLARE, IF, FOR, WHILE, REPEAT, CASE, PROCEDURE, FUNCTION) |
An identifier table lists each identifier with its data type and purpose, e.g. Max : INTEGER : stores the largest value found.
3. Stepwise refinement
Stepwise refinement starts with a high-level outline and breaks each step into more detailed steps until each can be written directly as code. It supports decomposition and makes large problems manageable.
1. Input marks 2. Calculate average 2.1 Total ← 0 2.2 FOR each mark: Total ← Total + mark 2.3 Average ← Total / NumberOfMarks 3. Output average and grade
4. Dry runs and trace tables
A trace table records the value of each variable and output as an algorithm is followed step by step. It is used to test an algorithm by hand and find logic errors.
Try it: dry-run with a trace table
Numbers:
Max ← Numbers[1]
FOR Index ← 2 TO 5
IF Numbers[Index] > Max
THEN
Max ← Numbers[Index]
ENDIF
NEXT Index
OUTPUT Max5. Examiner tips
- Abstraction removes detail; decomposition splits into parts. Do not mix them up.
- Use Cambridge pseudocode keywords and the ← assignment arrow.
- Trace tables: write a new row only when a value changes, and include outputs.
- Identifier tables need name, data type and purpose.
- Indent pseudocode inside IF and loops.
6. Practice questions
Practice: answer and check instantly
Type a short answer, then press Check or Enter.
Show answer
Abstraction.
Show answer
Decomposition.
Show answer
A diamond.
Show answer
The left arrow ←.
Show answer
Stepwise refinement.
Show answer
A trace table.
Show answer
An identifier table.
Show answer
NEXT.
Exam-style questions
9. Explain the difference between abstraction and decomposition, with an example of each. [4]
Show mark guide
Abstraction removes unnecessary details to focus on what matters [1] e.g. a route planner ignores building details [1] · decomposition breaks a problem into sub-problems [1] e.g. a game split into input, scoring and display modules [1].
10. Write pseudocode that inputs 10 numbers and outputs how many are greater than 50. [5]
Show mark guide
Count initialised to 0 [1] · FOR loop 1 TO 10 [1] · INPUT inside loop [1] · IF Number > 50 THEN Count ← Count + 1 [1] · OUTPUT Count after the loop [1].
7. Topic test: predict your grade
Topic test: predict your grade
15 questions, about 10 minutes. Answer them all, then press Mark my test.
Frequently asked questions
What is the difference between abstraction and decomposition?
Abstraction removes unnecessary detail to focus on what matters. Decomposition breaks a problem into smaller sub-problems that can be solved separately.
What is stepwise refinement?
Stepwise refinement starts with a high-level outline of an algorithm and breaks each step into more detailed steps until each can be coded directly.
How do you complete a trace table?
Follow the algorithm one line at a time and write a new value in the column for any variable that changes, including any outputs.