Algorithm design and problem-solving
The program development life cycle, decomposition, flowcharts and pseudocode, standard searching and sorting algorithms, validation, verification, test data and trace tables.
📌 Key points
- The program development life cycle has four stages: analysis (abstraction, decomposition, identifying requirements), design (structure diagrams, flowcharts, pseudocode), coding (writing and iterative testing) and testing (using test data).
- Abstraction removes unnecessary details to focus on what matters; decomposition breaks a problem into smaller sub-problems, each with inputs, processes, outputs and storage.
- A structure diagram shows how a system is broken into sub-systems. Flowchart symbols: terminator (start/stop), process (rectangle), input/output (parallelogram), decision (diamond) and flow lines (arrows).
- A linear search checks each item in a list in turn, from the first, until the item is found or the end of the list is reached.
- A bubble sort compares each pair of adjacent items and swaps them if they are in the wrong order; passes are repeated until a whole pass makes no swaps.
- Totalling adds each value to a running total (Total ← Total + Value); counting adds 1 each time (Count ← Count + 1); the average is Total ÷ Count; the maximum/minimum is found by comparing each value with the largest/smallest so far.
- Validation is an automatic check that data is reasonable and sensible: range, length, type, presence, format and check digit checks. Valid data can still be wrong.
- Verification checks that data has been copied or entered accurately: visual check (comparing with the original) and double entry (entering the data twice and comparing).
- Test data: normal (should be accepted), abnormal/erroneous (should be rejected), extreme (the largest and smallest acceptable values) and boundary (the value on each limit and the value just outside it).
- A trace table records the value of each variable and output as an algorithm is dry-run step by step, to find errors and work out what it does.
📖 Key terms
- Abstraction
- Removing unnecessary detail from a problem so only the important parts are considered.
- Decomposition
- Breaking a complex problem down into smaller, more manageable parts.
- Validation
- An automatic check that data entered is reasonable and meets set rules.
- Verification
- A check that data has been accurately copied from one source to another.
- Extreme data
- The largest and smallest values that should be accepted.
- Boundary data
- The values at each limit and just beyond each limit (one accepted, one rejected).
- Trace table
- A table used to record the values of variables at each step when dry-running an algorithm.
✏️ Worked example
Complete a trace table for this algorithm and give the output:
Total ← 0
FOR Count ← 1 TO 4
Total ← Total + Count * 2
NEXT Count
OUTPUT Total
- Start: Total = 0.
- Count = 1: Total = 0 + 2 = 2.
- Count = 2: Total = 2 + 4 = 6.
- Count = 3: Total = 6 + 6 = 12.
- Count = 4: Total = 12 + 8 = 20.
- The loop ends and the output is 20.
When asked for test data, give the actual value and its type, e.g. "50 – extreme" for a range of 1 to 50. For boundary data give both values: one on the limit (50, accepted) and one just outside (51, rejected).
Test yourself8 questions from a bank of 16. A new mix every time.
Start the quiz →