Detailed · Deep study
1The program development life cycle
| Stage | Tasks |
|---|---|
| analysis | abstraction (removing unnecessary detail to focus on what matters); decomposition of the problem; identification of the problem and the requirements (what the solution must do) |
| design | decomposition into sub-systems; structure diagrams, flowcharts and pseudocode showing how the solution will work |
| coding | writing the program code, with iterative testing – each module is tested and corrected as it is written |
| testing | testing the completed program code using test data to make sure it works as required |
2Sub-systems and decomposition
Every computer system is made up of sub-systems, which are made up of further sub-systems. Decomposition breaks a problem into its component parts so each can be solved separately: inputs (data entered), processes (calculations and decisions), outputs (results shown or printed) and storage (data kept for later).
Solutions can be designed and constructed using structure diagrams (the hierarchy of sub-systems), flowcharts (the flow of control through an algorithm) and pseudocode (structured, English-like statements).
3The purpose of an algorithm
To explain the purpose of an algorithm, state what it does overall (e.g. "it outputs the total and average of ten marks") and describe the processes involved: the inputs, the loop, what is calculated, what is output.
4Standard methods of solution
Linear search checks each item in a list in turn, from the first, until it finds the item or reaches the end.
DECLARE Names : ARRAY[1:30] OF STRING
DECLARE Index : INTEGER
DECLARE Found : BOOLEAN
OUTPUT "Enter the name to find"
INPUT SearchName
Found ← FALSE
Index ← 1
WHILE Found = FALSE AND Index <= 30 DO
IF Names[Index] = SearchName
THEN
Found ← TRUE
ELSE
Index ← Index + 1
ENDIF
ENDWHILE
IF Found = TRUE
THEN
OUTPUT SearchName, " found at position ", Index
ELSE
OUTPUT SearchName, " not found"
ENDIFBubble sort compares each pair of neighbouring items and swaps them if they are in the wrong order. After each pass the largest remaining item has "bubbled" to the end. Passes repeat until a pass makes no swaps.
DECLARE Numbers : ARRAY[1:6] OF INTEGER
Top ← 6
REPEAT
Swap ← FALSE
FOR Index ← 1 TO Top - 1
IF Numbers[Index] > Numbers[Index + 1]
THEN
Temp ← Numbers[Index]
Numbers[Index] ← Numbers[Index + 1]
Numbers[Index + 1] ← Temp
Swap ← TRUE
ENDIF
NEXT Index
Top ← Top - 1
UNTIL NOT Swap OR Top = 1Totalling adds each value to a running total; counting adds 1 each time something happens. To find the maximum or minimum, keep the largest/smallest so far and compare each value with it. The average is the total divided by the number of values.
Total ← 0
PassCount ← 0
Highest ← Marks[1]
Lowest ← Marks[1]
FOR Index ← 1 TO 30
Total ← Total + Marks[Index] // totalling
IF Marks[Index] >= 50
THEN
PassCount ← PassCount + 1 // counting
ENDIF
IF Marks[Index] > Highest
THEN
Highest ← Marks[Index] // maximum
ENDIF
IF Marks[Index] < Lowest
THEN
Lowest ← Marks[Index] // minimum
ENDIF
NEXT Index
Average ← Total / 30 // average
OUTPUT "Total ", Total, ", passes ", PassCount
OUTPUT "Highest ", Highest, ", lowest ", Lowest, ", average ", Average5Validation and verification
Validation is an automatic check by the computer that data entered is reasonable and meets set rules. It is needed because invalid data would give wrong results or make the program fail. Validation cannot tell if data is correct – only that it is sensible.
| Validation check | What it checks | Example |
|---|---|---|
| range check | a value is between a lower and an upper limit | mark from 0 to 100 |
| length check | the number of characters is exactly, or at least / at most, a given number | password at least 8 characters; phone number 11 digits |
| type check | the data is of the correct data type | age must be an integer |
| presence check | data has been entered (the field is not empty) | email address must be filled in |
| format check | the data follows a set pattern | date as DD/MM/YYYY; postcode format |
| check digit | the last digit, calculated from the other digits, is correct | ISBN, barcode |
REPEAT
OUTPUT "Enter a mark from 0 to 100"
INPUT Mark
IF Mark < 0 OR Mark > 100
THEN
OUTPUT "Invalid mark - please re-enter"
ENDIF
UNTIL Mark >= 0 AND Mark <= 100REPEAT
OUTPUT "Enter a password of at least 8 characters"
INPUT Password
UNTIL LENGTH(Password) >= 8 // length check
REPEAT
OUTPUT "Enter your name"
INPUT Name
UNTIL Name <> "" // presence checkVerification checks that data has been accurately copied from one source to another (e.g. from a paper form) or entered as intended. It is needed because typing errors can produce valid but wrong data.
| Verification check | How it works |
|---|---|
| visual check | the user reads through the data on screen and compares it with the original document |
| double entry check | the data is entered twice (e.g. a new password); the computer compares the two and asks again if they differ |
6Test data
| Type | Meaning | Example: whole-number mark from 0 to 100 |
|---|---|---|
| normal | data that should be accepted | 45, 72 |
| abnormal | data that should be rejected | −5, 150, "ten" |
| extreme | the largest/smallest acceptable value | 0 and 100 |
| boundary | the largest/smallest acceptable value and the corresponding smallest/largest rejected value | 0 and −1; 100 and 101 |
7Trace tables
A trace table documents a dry run of an algorithm: working through it by hand, writing down the values of the variables, the outputs and any user prompts at each step. It is used to find the purpose of an algorithm or to find errors.
01 Count ← 0
02 Total ← 0
03 Max ← 0
04 REPEAT
05 INPUT Number
06 Total ← Total + Number
07 IF Number > Max
08 THEN
09 Max ← Number
10 ENDIF
11 Count ← Count + 1
12 UNTIL Count = 4
13 OUTPUT Total, Max| Number | Count | Total | Max | OUTPUT |
|---|---|---|---|---|
| 0 | 0 | 0 | ||
| 5 | 1 | 5 | 5 | |
| 9 | 2 | 14 | 9 | |
| 3 | 3 | 17 | ||
| 7 | 4 | 24 | ||
| 24, 9 |
8Finding and correcting errors
01 Total ← 0
02 FOR Count ← 1 TO 10
03 INPUT Number
04 Total ← Number
05 NEXT Count
06 Average ← Total / 9
07 OUTPUT AverageWorked example
Identify the errors
Identify the two errors in the algorithm and suggest corrections.
- 1
Line 04 replaces the total instead of adding to it.
Total ← Total + Number
- 2
Line 06 divides by the wrong number of values.
Average ← Total / 10
Answerline 04 and line 06
Common errors: a variable not initialised (or reset inside a loop), the wrong operator (> instead of >=), a loop running the wrong number of times, and the wrong variable output.
9Writing and amending algorithms
Algorithms can be written as pseudocode, program code (Python, Visual Basic or Java) or flowcharts. When amending an algorithm, keep the parts that work, and add or change only the lines needed – e.g. adding validation to an input, or a counter to a loop.
See Topic 8 · ProgrammingThe pseudocode statements are covered in detail in 8.1 Programming concepts.10Exam focus
Key words: analysis; design; coding; testing; abstraction; decomposition; structure diagram; flowchart; pseudocode; linear search; bubble sort; totalling; counting; validation; verification; normal/abnormal/extreme/boundary data; trace table; dry run.
Quick self-check
Answer in your head first, then reveal.
Analysis (1); design (1); coding (1); testing (1).
10 and 11, or 18 and 19 (2).
Validation checks data is reasonable/meets rules (1); verification checks data has been copied/entered accurately (1).
Compare neighbouring items (1); swap if in wrong order (1); repeat through the list (1); until a pass with no swaps (1).
Any two: presence; format; range; type (2).
