Algorithm design and problem-solving: IGCSE Computer Science Complete Notes

The Problem Every Programmer Faces

You are given a task: build a program that accepts student marks, finds the highest score, and outputs the result. Where do you start? Do you jump straight to coding? Most students do, and most students lose marks for it. The IGCSE Computer Science syllabus expects you to show a structured approach to solving problems before writing a single line of code. That structured approach is what this topic is about.

Algorithm design and problem-solving sits at the heart of Paper 2 (0478). The examiners want to see that you can break a problem apart, design a solution using pseudocode or flowcharts, trace through your logic, and test it properly. Every skill in this topic connects to real exam questions, so precision matters.

The Program Development Life Cycle

Every program goes through four stages. The Cambridge IGCSE syllabus names them explicitly, and you should know what happens at each one.

Analysis is where you ask: what are the inputs? What should the output be? What processing needs to happen? If the problem says "accept 10 numbers and output the average," your analysis identifies the inputs (10 numbers), the process (sum them, divide by 10), and the output (the average).

Design is where you represent your solution visually or in structured text. Coding turns that design into executable instructions. Testing confirms the program handles all expected and unexpected scenarios.

Decomposition and Structure Diagrams

Large problems are difficult to solve in one step. Decomposition means breaking a complex problem into smaller, manageable sub-problems. Each sub-problem can then be solved independently.

This approach is called top-down design (or stepwise refinement). You start with the main problem at the top and divide it into sub-tasks. Each sub-task can be divided further until every piece is simple enough to implement directly.

A structure diagram shows this hierarchy visually. The main task sits at the top, with branches leading down to sub-tasks, which branch further into smaller steps.

Example: a program to manage a class register might decompose like this:

• Class Register System
  • Add Student (get name, get ID, store record)
  • Remove Student (search by ID, delete record)
  • Display All Students (loop through records, format output)

Each leaf node in the structure diagram is small enough to write as a short sequence of instructions. That is the goal of decomposition: reduce complexity until each piece is straightforward.

Algorithm Design Methods

Pseudocode

Pseudocode is a structured way of writing an algorithm using English-like statements. The Cambridge IGCSE syllabus uses a specific pseudocode syntax, and you should follow it closely in exams.

Key constructs in Cambridge pseudocode:

• Assignment: Variable ← Value (written as Variable ← Value)
• Input: INPUT Variable
• Output: OUTPUT Variable
• Selection: IF...THEN...ELSE...ENDIF
• Counted loop: FOR...TO...NEXT
• Pre-condition loop: WHILE...DO...ENDWHILE
• Post-condition loop: REPEAT...UNTIL

Flowcharts

Flowcharts use standard symbols to represent an algorithm visually:

Flowcharts must have exactly one Start and one Stop terminal. Every decision diamond must have two labelled exits (typically "Yes" and "No"). Arrows must show the direction of flow clearly.

Trace Tables

A trace table tracks the value of every variable as you step through an algorithm line by line. Each row represents one step of execution. Trace tables are essential for finding logic errors and are commonly tested in the IGCSE exam.

The columns of a trace table correspond to: each variable in the algorithm, and optionally an OUTPUT column. You fill in a new row each time a variable changes or an output is produced.

Worked Example 1: Trace Table Walkthrough

Step through the algorithm with a trace table:

Analysis of each iteration:

1. Index = 1: Number is 5. Since 5 > 0, Total becomes 0 + 5 = 5, Count becomes 0 + 1 = 1.
2. Index = 2: Number is -3. Since -3 is NOT > 0, the IF block is skipped. Total stays at 5, Count stays at 1.
3. Index = 3: Number is 8. Since 8 > 0, Total becomes 5 + 8 = 13, Count becomes 1 + 1 = 2.
4. Index = 4: Number is 0. Since 0 is NOT > 0, the IF block is skipped. Total stays at 13, Count stays at 2.

Final output: 13, 2. The algorithm totals only the positive numbers and counts how many there are.

Standard Algorithms

The IGCSE syllabus requires you to know several standard algorithms. You need to be able to write them in pseudocode, trace through them, and explain how they work.

Linear Search

Linear search checks each element in a list one by one until it finds the target value or reaches the end.

Pseudocode:

Linear search works on unsorted data. Its weakness is speed: for a list of 1000 items, it might need up to 1000 comparisons in the worst case.

Bubble Sort

Bubble sort compares adjacent pairs and swaps them if they are in the wrong order. It repeats passes through the list until no swaps occur.

Pseudocode:

The three-line swap using a temporary variable is critical. You cannot simply write List[Index] ← List[Index + 1] first, because that overwrites the original value before you can move it. The temporary variable preserves it.

Totalling, Counting, and Finding Max/Min

These are fundamental patterns that appear in almost every algorithm question.

Totalling: Start with Total = 0, then add each value in a loop.

Counting: Start with Count = 0, then increment by 1 each time a condition is met.

Finding Maximum: Set Max to the first value, then compare each subsequent value. If a value is larger than Max, update Max.

Finding Minimum: Same logic, but check if the value is smaller.

Pseudocode for finding the maximum in a list:

Worked Example 2: Writing Pseudocode from a Problem Statement

Step 1 - Analysis:

• Inputs: 30 marks (each between 0 and 100)
• Processes: validate each mark, calculate total, find highest
• Outputs: average mark, highest mark

Step 2 - Design (pseudocode):

Step 3 - Identify the patterns used:

1. Validation: The REPEAT...UNTIL loop rejects marks outside 0-100. This is a range check. The loop forces re-entry until the data is valid.
2. Totalling: Total accumulates every valid mark.
3. Finding maximum: Highest is compared against each new mark and updated when a larger value appears.
4. Counting: The FOR loop itself counts through 30 students, so a separate counter is not needed.

Notice that Highest is initialised to 0. This works here because all valid marks are 0 or above. If the range could include negative numbers, you would initialise Highest to the first actual input value instead.

Validation and Verification

These are two distinct concepts, and the examiners expect you to know the difference.

Validation is an automated check performed by a program to ensure data is reasonable and within expected rules. It does NOT check whether the data is correct - only whether it is acceptable.

Verification checks that data has been accurately transferred or entered. It confirms the data matches what was intended.

Types of Validation

Types of Verification

• Double entry: The user enters the same data twice (e.g., "confirm your email"). The system compares both entries and flags any mismatch.
• Screen/visual check: The data is displayed back to the user, who visually confirms it is correct before submission.

Test Data

Testing is the final stage of the development life cycle, and examiners frequently ask you to create a test plan. There are three categories of test data:

1. Normal data: Valid inputs that the program should accept and process correctly. For a mark between 0 and 100, normal data would be 45, 72, or 88.
2. Abnormal (erroneous) data: Inputs that the program should reject. For the same range, abnormal data would be -5, 101, or "abc".
3. Extreme (boundary) data: Values at the very edge of the accepted range. For 0 to 100, the boundary values are 0 and 100 themselves. You should also test the values just outside: -1 and 101.

A complete test plan for a mark-entry program (range 0-100) might look like this:

Common Mistakes

These errors appear repeatedly in student scripts. Avoid them.

1. Forgetting to initialise variables. If Total is not set to 0 before a loop, it may contain garbage data. Always initialise accumulators, counters, and flags before using them.
2. Off-by-one errors in loops. A FOR loop from 1 TO 10 runs 10 times. A FOR loop from 0 TO 9 also runs 10 times. But 0 TO 10 runs 11 times. Count carefully.
3. Confusing validation with verification. Validation checks rules (range, type, length). Verification checks accuracy (double entry, visual check). They are different processes with different purposes.
4. Missing the temporary variable in a swap. To swap A and B, you need: Temp = A, then A = B, then B = Temp. Skipping the temporary variable destroys one value.
5. Not testing boundary values. If a question says "between 1 and 50," your test plan must include 1 and 50 as boundary tests. Many students only test values in the middle.
6. Writing pseudocode without closing keywords. Every IF needs ENDIF. Every WHILE needs ENDWHILE. Every FOR needs NEXT. Missing closers will cost you marks.
7. Initialising max/min incorrectly. Setting Max to 0 is only safe if all possible values are non-negative. For general data, initialise Max to the first element of the list.

Exam Strategy

For trace table questions, work methodically. Draw the table with a column for every variable and one for output. Step through each line of the algorithm. Do not skip steps or try to do multiple iterations in your head at once. Write each change as it happens.

When asked to identify errors in a given algorithm, trace through it with simple test data first. The trace table will reveal where the logic breaks. Common errors to look for include: uninitialised variables, wrong comparison operators (using > instead of >=), and loops that iterate one too many or one too few times.

Self-Check Questions

1. A program accepts an integer input that must be between 10 and 20 inclusive. Write three pieces of test data: one normal, one boundary, and one abnormal. For each, state whether it should be accepted or rejected.
2. Explain the difference between validation and verification. Give one example of each.
3. The following pseudocode is intended to count how many numbers in a list of 5 are greater than 50. Identify the error:
   
   Count ← 0
FOR Index ← 1 TO 5
  INPUT Number
  IF Number > 50 THEN
    Count ← 1
  ENDIF
NEXT Index
OUTPUT Count
4. Draw or describe a trace table for a bubble sort algorithm applied to the list [4, 2, 7, 1] during the first complete pass.
5. Name the four stages of the program development life cycle in the correct order.