Understand system decomposition

Algorithm Design and Problem‑Solving – Problem (System) Decomposition

Learning objectives (Cambridge AO 1‑3)

By the end of this lesson students will be able to:

• AO1 – Knowledge and understanding: define problem (system) decomposition and the term sub‑system; recognise the required pseudo‑code conventions (indentation, line‑numbering, CASE statements, comments).
• AO2 – Application: apply the six‑step decomposition process to a given problem; design clear interfaces (inputs, outputs, data types, pre‑conditions); produce structured pseudo‑code and a top‑down flowchart.
• AO3 – Evaluation: evaluate the decomposition by validating, verifying and testing the solution; justify the choice of sub‑systems and explain how they fit into the programme‑development life‑cycle (PDLC).

1. What is problem (system) decomposition?

Problem (system) decomposition is the systematic breaking‑down of a complex problem or system into a set of smaller, more manageable sub‑systems (or sub‑tasks). Each sub‑system performs a single, well‑defined function, can be designed and coded independently, and is later combined to form the complete solution. In the Cambridge syllabus this is also called top‑down design or divide‑and‑conquer.

2. The six steps of problem decomposition (aligned to AO 1‑3)

1. Analyse the whole problem (AO1) – read the specification, list required inputs, outputs, constraints and any validation checks.
2. Identify major sub‑systems (AO2) – recognise distinct functions the programme must perform (e.g. input, initialise, process, output).
3. Break each major sub‑system into smaller sub‑tasks (AO2) – continue until each sub‑task can be expressed as a single pseudo‑code statement or a short block of code (≤ 3 lines).
4. Define the interface of every sub‑task (AO2) – state input variables, output variables, data types, and any pre‑conditions.
5. Arrange the sub‑tasks (design stage) (AO2) – decide execution order, loops and conditionals; produce a top‑down flowchart or structured pseudo‑code using Cambridge conventions.
6. Validate, verify and test the decomposition (AO3) – use test data, trace tables and error‑identification techniques to show that the combined sub‑systems satisfy the original specification.

3. Mapping the steps to the programme‑development life‑cycle (PDLC)

4. Programming‑concepts reminder (Topic 8)

When you translate a decomposition into pseudo‑code you will need the following Cambridge constructs:

• DECLARE – variables, constants, arrays (specify size and data type).
• INPUT / OUTPUT – READ and OUTPUT statements (parallelogram symbols in flowcharts).
• Selection – IF … THEN … END IF and CASE … OF … END CASE for multi‑way decisions.
• Iteration – FOR … TO … DO … END FOR and WHILE … DO … END WHILE.
• Procedures / Functions – optional for large programmes; list parameters (input, output, in‑out) and return type.
• File I/O (optional extension) – OPEN, READ FROM, WRITE TO, CLOSE.

Example – “Find the Highest and Lowest Marks”

Problem statement

Given a list of n integer marks, output the highest and lowest mark. Each mark must be between 0 and 100.

Decomposition (sub‑systems)

1. Input – read n and the n marks into an array MARKS[ ].
2. Initialise – set MAX ← MARKS[0] and MIN ← MARKS[0].
3. Validate marks – check each mark is in the range 0‑100; stop with an error message if not.
4. Process – loop through the remaining marks, updating MAX and MIN.
5. Output – display MAX and MIN.

Interface table for the sub‑systems

Structured pseudo‑code (Cambridge conventions, line‑numbered)

01  DECLARE n, i, MAX, MIN : INTEGER
02  DECLARE MARKS[ ] : ARRAY[0..99] OF INTEGER   // max 100 marks
03  
04  READ n
05  FOR i ← 0 TO n‑1 DO
06      READ MARKS[i]
07  END FOR
08  
09  // ---- Validation -------------------------------------------------
10  FOR i ← 0 TO n‑1 DO
11      IF MARKS[i] < 0 OR MARKS[i] > 100 THEN
12          OUTPUT "Invalid mark at position", i
13          STOP
14      END IF
15  END FOR
16  
17  // ---- Initialise -------------------------------------------------
18  MAX ← MARKS[0]
19  MIN ← MARKS[0]
20  
21  // ---- Process ----------------------------------------------------
22  FOR i ← 1 TO n‑1 DO
23      IF MARKS[i] > MAX THEN
24          MAX ← MARKS[i]
25      END IF
26      IF MARKS[i] < MIN THEN
27          MIN ← MARKS[i]
28      END IF
29  END FOR
30  
31  // ---- Output -----------------------------------------------------
32  OUTPUT "Highest mark :", MAX
33  OUTPUT "Lowest  mark :", MIN

Validation, verification and testing (AO 3)

• Validation (input checking) – ensures data meet required range, format and length constraints (lines 10‑14).
• Verification (algorithm checking) – confirms the pseudo‑code produces the required outputs for all test cases.
• Testing strategy – use three kinds of test data:
  • Normal – typical values within the range.
  • Boundary – values at the limits (0 and 100).
  • Invalid/Extreme – values outside the range to test validation.
• Trace tables – step through the Process sub‑system, recording i, MARKS[i], MAX and MIN after each iteration.
• Common error‑identification points:
  • Off‑by‑one loop limits.
  • Wrong relational operator (> vs. >=).
  • Missing initialisation of MAX / MIN.
  • Omitting validation checks.

Sample trace table (normal data)

5. Boolean logic & logic‑gate activity (Topic 10)

Consider the validation condition “mark ≥ 50 AND mark ≤ 100”.

1. Write the Boolean expression using Cambridge symbols: (mark ≥ 50) ∧ (mark ≤ 100).
2. Draw the corresponding logic‑gate circuit (AND gate with two inputs, each fed by a comparator).
3. Complete the truth table below.

6. Benefits of problem decomposition

• Clarity – each sub‑system has a single, well‑defined purpose.
• Re‑usability – generic sub‑systems (e.g., “search an array”) can be used in many programmes.
• Testing & debugging – modules can be tested in isolation with trace tables.
• Collaboration – different team members can develop different sub‑systems simultaneously.

7. Common pitfalls and how to avoid them

8. Cross‑topic notes

• Databases (Topic 9): In a larger system the Input sub‑system might read marks from a file or an SQL table (e.g., SELECT mark FROM marks WHERE student_id = …). The same decomposition principles apply – the database query becomes a separate sub‑system with its own interface.
• Optional extensions – error‑detection & encryption (Topic 2): For more advanced work you could add a parity check on the input data or encrypt the marks before writing them to a file. These are not required for this lesson but illustrate how additional concepts can be layered onto a well‑decomposed design.

9. Problem‑decomposition checklist (summary table)

10. Practice questions

1. Decompose the problem “Calculate the average of a list of numbers and indicate for each number whether it is above or below the average”.
   • Provide at least three sub‑systems.
   • Define the interface (inputs, outputs, data types) for each sub‑system.
   • Write a short pseudo‑code fragment (≤ 4 lines) for one sub‑system (e.g., the “compare with average” sub‑system).
2. The pseudo‑code for bubble sort is given below. Identify a sensible decomposition into two sub‑systems, describe the interface between them and sketch a trace table for the list [42, 17, 93, 5].

   FOR i ← 0 TO n‑2 DO
       FOR j ← 0 TO n‑i‑2 DO
           IF A[j] > A[j+1] THEN
               TEMP ← A[j]
               A[j] ← A[j+1]
               A[j+1] ← TEMP
           END IF
       END FOR
   END FOR
   

3. Explain why clear interface definitions are essential when two sub‑systems are developed by different students. Give two concrete examples of problems that can arise if interfaces are ambiguous.
4. Using the “Highest and Lowest Marks” algorithm, create trace tables for the following test data sets:
   • Normal data: n = 4, marks = [55, 70, 68, 82]
   • Boundary data: n = 3, marks = [0, 100, 50]
   • Invalid data: n = 2, marks = [‑5, 105] – show how the validation check stops the programme.

Suggested diagram (for teacher)

A top‑down flowchart showing the main problem at the top, branching into the five sub‑systems (Input, Initialise, Validate, Process, Output). The Process block contains a loop (rectangle) with a decision diamond for the “max/min” comparisons. Use the standard Cambridge symbols: parallelogram (input/output), rectangle (process), diamond (decision), arrows for flow.