Skip to content
Cambridge IGCSE0478

Algorithm design and problem-solving

Computer Science 0478 Chapter Notes

What this chapter covers

Algorithm design and problem-solving
ShareWhatsAppPost
Algorithm design and problem-solving notes

Read online free. Download a watermarked copy with a free account.

Read the notes

The full Algorithm design and problem-solving notes as text: skim, search, and jump between subtopics.

~12 min read

In this chapter

  1. 1The program development life cycle
  2. 2Sub-systems, decomposition and design methods
  3. 3Purpose of an algorithm and trace tables
  4. 4Standard methods of solution
  5. 5Validation and verification
  6. 6Test data
  7. 7Finding and correcting errors
  8. 8Writing and amending algorithms

1. The program development life cycle

The program development life cycle has four stages: analysis, design, coding and testing.

In analysis, abstraction keeps the important aspects of the problem. The problem is decomposed into smaller parts and its requirements are identified.

In design, decomposition continues. The solution is shown with structure diagrams, flowcharts and pseudocode. In coding, the program is written and tested iteratively. In testing, the program code is tested with test data.

Examiner insight

“Most candidates were aware that abstraction means removing details from the problem that are not relevant.” “Many responses needed to show greater understanding of the specific uses of structure diagrams, flowcharts and pseudocode during the design stage.”

Worked example 16 marks

The program development life cycle is split into a number of stages.

Describe what happens during the analysis and design stages of the program development life cycle.

  1. 1

    Analysis: abstraction to emphasise the important aspects of the problem [1]

  2. 2

    Analysis: decomposition of the problem into smaller, manageable parts [1]

  3. 3

    Analysis: identification of the (functional) requirements of the problem [1]

  4. 4

    Design: decomposition to separate the problem into further sub-problems [1]

  5. 5

    Design: generate structure diagrams to represent the proposed system [1]

  6. 6

    Design: construct a flowchart, or write the algorithm in pseudocode [1]

2. Sub-systems, decomposition and design methods

Every computer system is made up of sub-systems, which are made up of further sub-systems. A problem is decomposed into its component parts in the same way.

Each part can be described by its inputs, processes, outputs and storage.

A solution is designed and constructed with structure diagrams, flowcharts or pseudocode.

Worked example 14 marks

A school system records one mark for each student in a test. It works out the class average and keeps it in a file.

Give one input, one process, one output and one item of storage for this system.

  1. 1

    Input: the mark entered for each student [1]

  2. 2

    Process: the marks are added up and divided by the number of students [1]

  3. 3

    Output: the class average, displayed on screen [1]

  4. 4

    Storage: the file that holds the class average [1]

3. Purpose of an algorithm and trace tables

To state the purpose of an algorithm, say what it does as a whole. Do not read it out line by line. To describe the processes, say what happens to the data: what is input, what is changed and what is output.

A trace table documents a dry-run. It has a column for each variable and one for the output. Work through the algorithm one statement at a time and write a new value only when a variable changes.

Write only the output itself in the output column, with no quotation marks. Stop when the algorithm stops.

Examiner insight

“Common errors seen included not realising that the last two values of the input data would not be used or including extra values in the output column.” “A common error was to describe the purpose as finding odd, even, or prime numbers.”

Worked example 14 marks

This algorithm is given.

``` Total ← 0 INPUT Number WHILE Number <> -1 DO Total ← Total + Number INPUT Number ENDWHILE OUTPUT Total ```

The numbers 4, 7, 2 and -1 are input, in that order.

(a) Complete a trace table with columns Total, Number and OUTPUT.

(b) State the purpose of the algorithm.

  1. 1

    (a) Total column: 0, 4, 11, 13 [1]

  2. 2

    Number column: 4, 7, 2, -1 [1]

  3. 3

    OUTPUT column: 13, written once, after -1 is read, with no quotation marks [1]

  4. 4

    (b) It adds up (totals) the numbers input until -1 is input, then outputs the total [1]

4. Standard methods of solution

A linear search checks each item in the list in turn, from the first, and compares it with the item wanted. A flag set to `TRUE` when the item is found lets the algorithm tell the user if it was not found.

A bubble sort compares each pair of adjacent items and swaps them if they are in the wrong order, using a temporary variable. It repeats passes until no swap is made.

Totalling adds each value to a total that starts at zero. Counting adds 1 to a count that starts at zero. For the largest or smallest value, compare each input with the stored value and replace it when the new one is larger or smaller. Start the store for the smallest value high, not at zero. The average is the total divided by the count.

Examiner insight

“A common error was to initialise the variable to store the smallest number to a low value, for example Small ← 0 instead of Small ← 1000” “A common error was to incorrectly state totalling instead of counting for Number ← Number + 1”

Worked example 14 marks

The following pseudocode algorithm uses a bubble sort to sort the array `Names[50]`.

Complete the algorithm.

``` Last ← ______ REPEAT Swap ← ______ FOR ______ ← 1 TO Last - 1 IF Names[Index] > Names[Index + 1] THEN Temp ← Names[Index] Names[Index] ← Names[Index + 1] Names[Index + 1] ← Temp Swap ← TRUE ENDIF NEXT Index Last ← Last - 1 UNTIL ______ Swap OR Last = 1 ```

  1. 1

    `Last ← 50` [1]

  2. 2

    `Swap ← FALSE` [1]

  3. 3

    `FOR Index ← 1 TO Last - 1` [1]

  4. 4

    `UNTIL NOT Swap OR Last = 1` (or `FALSE = Swap`) [1]

5. Validation and verification

Validation checks that data input is sensible, in real time, as it is entered. It does not prove the data is correct. Verification checks that no errors have been introduced during input.

Validation checks: a range check tests that a number is between two set values. A length check tests the number of characters. A type check tests the type of data, for example a whole number. A presence check tests that data has been input and not left blank. A format check tests that data follows a set pattern, such as two letters followed by three numbers. A check digit is a value placed at the end of a sequence of numbers, calculated from all the other values before it.

Verification checks: a visual check and a double entry check. In a double entry check the data is input twice and the two inputs are compared.

Examiner insight

“Some candidates confused validation with verification and gave responses that would be reasons to verify data on input.” “Some candidates incorrectly named validation checks, such as range or type check.”

Worked example 15 marks

(a) Identify the type of validation check used in each description.

(i) A check to make sure that data has been input and not left blank.

(ii) A value placed at the end of a sequence of numbers in the code. The value is calculated from all the other values before it.

(b) Explain the purpose of a format check and give an example of where it could be used.

  1. 1

    (a)(i) presence check [1]

  2. 2

    (ii) check digit [1]

  3. 3

    (b) to check that the input matches a specified style / pattern / structure [1]

  4. 4

    ... by containing set numbers of letters and numbers, or groups of digits [1]

  5. 5

    example: a date in the format dd/mm/yyyy [1]

6. Test data

Test data is used to see whether a program behaves in the intended manner. The program should accept and process the required data and reject unwanted data.

Normal data falls within the accepted parameters of a validation check and is accepted. Abnormal data is unwanted and is rejected. Extreme data is the highest or lowest value to be accepted. Boundary data is the largest or smallest acceptable value and the corresponding smallest or largest rejected value.

For a range check that accepts whole numbers from 1 to 100: normal 50, abnormal -5, extreme 1 and 100, boundary 1 with 0, and 100 with 101.

Examiner insight

“There was some confusion between extreme and boundary data.” “Common errors seen, included giving examples of extreme data that were erroneous and would not be accepted.”

Worked example 12 marks

Identify the type of test data in each description.

(i) Data that falls within the accepted parameters of a validation check and is accepted.

(ii) Data that is the highest or lowest value to be accepted.

  1. 1

    (i) normal (test data) [1]

  2. 2

    (ii) extreme (test data) [1]

7. Finding and correcting errors

To identify an error, give the line number and the correction. Check each line against what the algorithm is meant to do.

The errors the papers set include a wrong data type in a `DECLARE`, `OUTPUT` where `INPUT` is needed, a wrong loop condition, `Total + 1` where `Total + Number` is meant, a division the wrong way round, a wrong array index and a `NEXT` that does not match its `FOR`.

Examiner insight

“Candidates who had made themselves familiar with the pseudocode given in the syllabus achieved the highest marks.”

Worked example 14 marks

An algorithm has been written in pseudocode for a user to repeatedly input positive whole numbers and store them in an array called `Values[]` until -1 is input or until the array is full. The algorithm outputs the average of the numbers to 2 decimal places.

``` 01 DECLARE Counter : INTEGER 02 DECLARE Total : INTEGER 03 DECLARE Average : INTEGER 04 DECLARE Values : ARRAY[1:100] OF INTEGER 05 Counter ← 1 06 Total ← 0 07 OUTPUT "Please enter a positive whole number or -1 " 08 INPUT Number 09 WHILE Number = -1 AND Counter <= 100 DO 10 Values[Counter] ← Number 11 Total ← Total + 1 12 Counter ← Counter + 1 13 INPUT Number 14 ENDWHILE 15 Counter ← Counter - 1 16 Average ← Counter / Total 17 OUTPUT "The average is ", ROUND(Average, 2) ```

Identify the line numbers of four errors in the pseudocode and suggest a correction for each error.

  1. 1

    Line 3: should be `DECLARE Average : REAL` [1]

  2. 2

    Line 9: should be `WHILE Number <> -1 AND Counter <= 100 DO` [1]

  3. 3

    Line 11: should be `Total ← Total + Number` (or `Total + Values[Counter]`) [1]

  4. 4

    Line 16: should be `Average ← Total / Counter` [1]

8. Writing and amending algorithms

Precision is required: `x > y` is acceptable, but "x is greater than y" is not. Use Cambridge pseudocode, with keywords in capitals and `←` for assignment. Do not mix in Python.

Use an appropriate loop: `FOR ... NEXT` to iterate for a set number of inputs, and a condition-controlled loop (`REPEAT ... UNTIL` or `WHILE ... DO`) to input again until the data is valid. Test for the wrong input, not the correct one. Set totals and counters to zero before the loop.

Show at least two outputs: an input prompt, an error message or a completion message. A flowchart answer needs flow lines with arrows and must end at STOP.

Examiner insight

“Some candidates incorrectly mixed Python code in with their pseudocode statements.” “Candidates whose data entry checks looked for a correct input, rather than an incorrect one, found it more difficult to enable the data to be re-entered.”

Worked example 16 marks

Write the pseudocode for an algorithm to perform a validation check on each number as it is input to meet the following criteria:

  • Input 20 numbers, one at a time.
  • If a number is negative, store it in the current element of array `NegNumbers[]`.
  • If a number is not negative, ask for it to be input again until a negative number is input.
  • When all 20 negative numbers have been stored, output a message to state the check has been completed.

Use appropriate input prompts and output messages to make the requirements clear to the user. Do not declare any arrays or variables for this algorithm.

  1. 1

    Appropriate loop to iterate for 20 inputs [1]

  2. 2

    Input of a number [1]

  3. 3

    Condition-controlled loop to test if each input is or is not negative [1]

  4. 4

    Store a negative number in the correct array location in `NegNumbers[]` [1]

  5. 5

    Repeated input if the number is not negative, until it is negative [1]

  6. 6

    At least two outputs seen: input prompt, error message or completion message [1]

  7. 7

    ``` FOR Count ← 1 TO 20 REPEAT OUTPUT "Input a negative number" INPUT Number IF Number >= 0 THEN OUTPUT "Your number is not negative, please re-input" ELSE NegNumbers[Count] ← Number ENDIF UNTIL Number < 0 NEXT Count OUTPUT "The check has been completed" ```

Recap

  • The stages are analysis, design, coding and testing. Analysis uses abstraction and decomposition. Design uses structure diagrams, flowcharts and pseudocode.
  • A computer system is sub-systems within sub-systems. Describe a part by inputs, processes, outputs and storage.
  • State the purpose of an algorithm as a whole. In a trace table, write only the output, with no quotation marks.
  • Standard methods: linear search, bubble sort, totalling, counting, largest, smallest and average. Start totals and counts at zero, and the smallest at a high value.
  • Validation checks that data is sensible. Verification checks that no errors were introduced during input.
  • Test data: normal, abnormal, extreme and boundary. Boundary data includes the rejected value next to the limit.
  • To find an error, give the line number and the correction.
  • Write pseudocode precisely, with a loop, prompts and messages.

End-of-chapter exercise

Test yourself on the whole chapter. Work through these before moving on.

  1. State the stage of the program development life cycle in which a flowchart is constructed.1 mark
  2. Explain what is meant by decomposing a problem.2 marks
  3. The array `Data` holds 5, 3, 8, 1. A bubble sort makes one complete pass, sorting into ascending order. Write the contents of the array after this pass.2 marks
  4. The array `Marks[1:40]` holds 40 marks. Write pseudocode to count the marks that are 50 or more and output the count.4 marks
  5. A program finds the smallest of 20 temperatures. Every temperature is between 5 and 45. The program starts with `Smallest ← 0`. Explain why it outputs the wrong answer.3 marks
  6. A form asks for an age that must be a whole number from 11 to 18. Name the validation check that rejects (a) twelve typed as a word, (b) 25, (c) a blank entry.3 marks
  7. A user types a new email address twice and the system compares the two entries. Name this check and explain why it does not prove the email address is correct.3 marks
  8. A program accepts a whole number of hours from 1 to 12 inclusive. Give one example of each: normal, abnormal, extreme and boundary test data.4 marks
  9. A depot loads parcels onto a trolley. ``` Heavy ← 0 Load ← 0 INPUT Weight WHILE Weight > 0 AND Load + Weight <= 50 DO Load ← Load + Weight IF Weight >= 15 THEN Heavy ← Heavy + 1 ENDIF INPUT Weight ENDWHILE OUTPUT "Loaded ", Load OUTPUT "Heavy ", Heavy ``` (a) Complete a trace table with columns Heavy, Load, Weight and OUTPUT for the input data 12, 15, 9, 20, 6, -1, 8. (b) State the purpose of the algorithm. (c) The algorithm is run again and the first input is 60. State what is output and explain why.8 marks
  10. A weather station inputs the midday temperature, a whole number, for each of 30 days. A valid temperature is from -40 to 60 inclusive. The algorithm should make the user input each temperature again until it is valid. It should then output the lowest temperature and the number of days with a temperature below zero. ``` 01 Lowest ← 0 02 Frost ← 0 03 FOR Day ← 1 TO 30 04 INPUT Temp 05 WHILE Temp >= -40 AND Temp <= 60 DO 06 OUTPUT "Not valid, input again" 07 INPUT Temp 08 ENDWHILE 09 IF Temp < Lowest 10 THEN 11 Lowest ← Temp 12 ENDIF 13 IF Temp < 0 14 THEN 15 Frost ← Frost + Temp 16 ENDIF 17 NEXT Day 18 OUTPUT "Lowest ", Lowest 19 OUTPUT "Frost days ", Frost ``` (a) Identify the line numbers of three errors and suggest a correction for each. (b) A student changes line 01 to `Lowest ← -40`. Explain why the algorithm still outputs the wrong lowest temperature. (c) The corrected algorithm must also output the average temperature. Write the new pseudocode statements and state where each one is placed. (d) Give boundary test data for the upper limit of the validation check. State what should happen to each value.10 marks

Go deeper

Practise and revise with member-only material for this chapter.

Workbook

Exam-style practice questions with full worked solutions.

Unlock with a plan

Chapter at a Glance

A single-page summary of every key idea for fast revision.

Unlock with a plan

Free notes are just the start.

Unlock every Workbook and Chapter at a Glance, and generate your own worksheets and predicted papers.

Explore plans

Related chapters

Number systemsTypes and methods of data transmissionComputer architectureTypes of software and interruptsThe internet and the world wide webAutomated systems