Describe and use decomposition

9.1 Computational Thinking – Decomposition (and Abstraction)

Learning Objective

Students will be able to describe and apply decomposition as a problem‑solving technique, recognise its link with abstraction, and relate both concepts to the Cambridge International AS & A Level Computer Science (9618) syllabus (AO1, AO2, AO3).

1. What Is Decomposition?

• Definition: The process of breaking a complex problem or system into smaller, manageable sub‑problems (or components) that can be solved independently.
• Key idea: “Divide and conquer”. Each sub‑problem has a well‑defined interface (inputs, outputs, data structures) that allows the pieces to be recombined.

2. What Is Abstraction?

• Definition: The technique of ignoring non‑essential details and focusing on the essential features of a problem or component.
• Relationship to decomposition: After a problem is decomposed, each part can be abstracted into a “black box” – we only need to know its interface, not its internal workings.

Quick Activity – Identify Abstractions

Choose a real‑world system (e.g., a library). List three details you could abstract away when modelling it in software.

3. Why Decompose?

• Reduces cognitive load – smaller pieces are easier to understand.
• Supports teamwork – different developers can work on different modules.
• Enables reuse – a solved sub‑task can be used in other problems.
• Facilitates testing and debugging – faults can be isolated to a specific component.
• Aligns with the PDLC (AO3 – design, implementation, testing).

4. Steps for Effective Decomposition (AO2)

1. Understand the whole problem. Identify the goal, constraints and required output.
2. Identify major components. Look for natural divisions (e.g., input, processing, output; or UI, database, business logic).
3. Break components into sub‑tasks. Continue dividing until each sub‑task can be expressed as an algorithm or pseudocode.
4. Define interfaces. Specify the inputs, outputs and data structures for each sub‑task.
5. Implement & unit‑test each sub‑task. Verify correctness before moving on.
6. Integrate sub‑tasks. Combine the solved pieces to obtain the complete solution.

Stepwise Refinement (AO2)

Iteratively replace a high‑level description with more detailed pseudocode or flow‑chart steps while keeping the original interface unchanged.

High‑level:  Read list of numbers
Refinement:
open file “data.txt”
while not EOF
read line
convert line to integer
append integer to list
end while
close file

5. Worked Examples Across the Syllabus

5.1 Example 1 – Calculating the Average of a List (Core AO2)

function main()
numbers ← readNumbers()          // input
total   ← sumNumbers(numbers)    // processing
count   ← length(numbers)        // processing
avg     ← total / count
output(avg)                      // output
end function
function readNumbers()
// stepwise refinement: open file, read lines, convert to int
…
end function
function sumNumbers(list)
total ← 0
for each x in list
total ← total + x
return total
end function

5.2 Example 2 – Simple Client‑Server Protocol (Communication & Networks)

Problem: Design a protocol where a client sends a text message to a server, the server acknowledges receipt, and both then close the connection.

Decomposition

1. Client: create socket & connect to server.
2. Client: send message.
3. Server: accept connection.
4. Server: receive message.
5. Server: send acknowledgement.
6. Client: receive acknowledgement.
7. Both: close socket.

Interface example (pseudo‑API)

clientSend(message:string) → ack:string
serverReceive() → message:string
serverSendAck(ack:string) → void

5.3 Example 3 – CPU Fetch‑Execute Cycle (Processor Fundamentals)

Problem: Model one iteration of the fetch‑execute cycle for a simple accumulator‑based CPU.

Decomposition

1. Fetch instruction from memory address in the Program Counter (PC).
2. Increment PC.
3. Decode instruction (identify opcode and operand).
4. Execute instruction (e.g., LOAD, ADD, STORE).
5. Update registers / memory as required.

Abstraction: The “Execute” step is abstracted as a black‑box function execute(opcode, operand) that hides the internal micro‑operations.

5.4 Example 4 – Normalising a Database (Databases)

Problem: Store student results so that data redundancy is minimised.

Decomposition

1. Identify entities: Student, Course, Result.
2. Define attributes for each entity (e.g., Student{id, name}).
3. Determine primary keys and foreign‑key relationships.
4. Translate each entity into a table (record abstraction).
5. Write SQL queries to insert, update and retrieve data.

5.5 Example 5 – Breadth‑First Search (Artificial Intelligence)

Problem: Find the shortest path between two nodes in an un‑weighted graph.

Decomposition

1. Initialise an empty queue and a visited set.
2. Enqueue the start node.
3. While the queue is not empty:

   • Dequeue a node.
   • If it is the goal, terminate.
   • Otherwise, enqueue all un‑visited neighbours and mark them visited.

Abstraction: The “enqueue neighbours” step is abstracted as expand(node), hiding the underlying adjacency‑list implementation.

6. Programming Constructs Used in Decomposition

• Selection: IF … THEN … ELSE – decides which sub‑task to perform.
• Iteration: FOR, WHILE/REPEAT – repeats a sub‑task.
• Procedures/Functions: Encapsulate a sub‑task and expose a clean interface.
• Recursion (optional): A form of decomposition where a task calls itself with a simpler input.

Example – Count Positive Numbers (Selection + Iteration)

function countPositives(list)
count ← 0
for each x in list               // FOR loop
if x > 0 then                // IF selection
count ← count + 1
end if
end for
return count
end function

7. Data Types & Structures in Decomposition

7.1 Arrays / Lists

Used when the sub‑task processes an ordered collection (e.g., average calculation, BFS queue).

7.2 Records (Structures)

record Student
id    : integer
name  : string
grade : integer
end record

When calculating a class average, a sub‑task extracts grade from each Student record – an example of abstraction (the rest of the record is hidden).

7.3 Dictionaries / Maps

Useful for counting frequencies (e.g., word‑count exercise) or representing associative data such as a symbol table.

8. Decomposition in Real‑World Projects

9. Link to the Software Development Life‑Cycle (PDLC) & Testing (AO3)

10. Concept Bridge – How Decomposition Appears in the Rest of the Syllabus

11. Practice Exercises

Exercise 1 – Word‑Frequency Counter (Data Structures, File I/O, Testing)

Task: Design an algorithm that reads a text file, counts how many times each word occurs, and outputs the three most frequent words.

1. Identify at least four sub‑tasks.
2. State the input and output for each sub‑task.
3. Write a unit test for the “Count words” sub‑task (e.g., input = [“cat”, “dog”, “cat”] → output = {cat:2, dog:1}).

Suggested Decomposition

Exercise 2 – Normalising a Student‑Result Database (Databases, Decomposition & Abstraction)

Design the schema for storing student results, then write pseudocode to compute the class average.

1. Decompose the data model into tables (Student, Course, Result).
2. For each table, list the fields (attributes) and primary/foreign keys.
3. Write a sub‑task “extractGrades” that takes a list of Result records and returns an array of integers.
4. Show how “extractGrades” is called from a higher‑level “classAverage” function.

12. Key Takeaways

• Decomposition turns a large problem into a set of smaller, solvable sub‑problems.
• Abstraction hides the internal details of each sub‑task, exposing only a clean interface.
• Clear interfaces are essential for integration, testing, and teamwork.
• Stepwise refinement adds detail to each sub‑task until it can be directly coded.
• Choosing appropriate data structures (arrays, records, dictionaries) is part of the decomposition process.
• Decomposition is a core skill across the entire Computer Science syllabus – from data representation to AI.
• Effective decomposition improves readability, maintainability, and aligns with the PDLC (AO3).