Home Notes Papers

Algorithm design and problem-solving

Paper 2

This section is examined in Paper 2.

The Problem-Solving Process (PDLC)
Before writing code, you must understand how to solve a problem computationally. Cambridge expects you to know the Program Development Life Cycle (PDLC) and the specific techniques used during the Analysis stage.

1. Analysis Stage: This is where you define the problem. You must identify:

  • Inputs: What data goes in?
  • Outputs: What results are produced?
  • Processes: How do inputs become outputs?

To manage complexity, Cambridge uses two key techniques:

  • Abstraction: Hiding irrelevant details to focus on the core logic. For example, when designing a map app, you abstract away the color of the cars and focus only on road connections.
  • Decomposition: Breaking a large problem into smaller, manageable sub-problems (e.g., splitting 'Calculate Payroll' into 'Input Hours', 'Calculate Tax', 'Output Net Pay').

2. Design Stage: You create the solution using:

  • Flowcharts: Visual diagrams using standard symbols (Oval=Start/End, Parallelogram=I/O, Rectangle=Process, Diamond=Decision).
  • Pseudocode: Text-based algorithm description.
  • Structure Diagrams: Hierarchical breakdown of modules.

3. Coding & Testing: You write the code and test it using:

  • Normal Data: Valid input (e.g., age 25).
  • Boundary/Extreme Data: Values at the limits (e.g., age 0 or 150).
  • Erroneous/Abnormal Data: Invalid input (e.g., age -5 or 'abc') to check error handling.
Pseudocode Syntax and Structure
Pseudocode is a high-level description of an algorithm. It is not real code, but it must follow strict logical rules. Cambridge accepts specific keywords.
Standard Pseudocode Syntax
INTEGER count
STRING name
REAL average
count <- 0
(Use <- or = depending on syllabus version, but <- is safer for clarity)
INPUT age
PRINT "Result: ", result
IF condition THEN<br> action<br>ELSE<br> action<br>ENDIF
WHILE condition DO<br> action<br>ENDWHILE
FOR i <- 1 TO n DO<br> action<br>NEXT i
Key Rule: Always use meaningful variable names (e.g., totalScore instead of x). Indentation is crucial for readability and showing block structure.
Writing a Simple Algorithm: Calculate Average
Problem: Write an algorithm to find the average of 5 numbers entered by the user.
// 1. Declare variables
INTEGER count
REAL number, total, average

// 2. Initialize total
total <- 0

// 3. Loop to get input
FOR count <- 1 TO 5 DO
    INPUT number
    total <- total + number
NEXT count

// 4. Calculate average
average <- total / 5

// 5. Output result
PRINT "The average is: ", average

Why this works:

  • We use a FOR loop because the number of iterations (5) is known.
  • total accumulates the sum. If we didn't initialize it to 0, it might contain garbage data.
  • Division by 5 is constant, so we don't need a variable for the count of numbers.
⚠︎ Confusing Abstraction with Decomposition
The Error: Students often say 'Abstraction is breaking the problem into smaller parts.'

The Correction: This is Decomposition.

  • Abstraction is about ignoring details (hiding complexity).
  • Decomposition is about splitting the problem into modules or steps.

Examiner Tip: When asked to explain how abstraction helps, say: 'It allows the programmer to focus on the essential features of the problem without being distracted by irrelevant details.' Do not mention breaking things down.

Describing the Purpose of an Algorithm
Context: You are often given a snippet of pseudocode or a flowchart and asked to 'Describe the purpose of this algorithm.'

Why Examiners Accept This: They want to see that you understand the logic, not just the syntax. Vague answers like 'It does math' get zero marks.

Correct Approach: Identify the specific operations:

  1. Does it find a maximum/minimum?
  2. Does it sort data?
  3. Does it calculate a total/average?
  4. Does it validate input?

Example Phrase: 'This algorithm iterates through a list of numbers, comparing each value to a stored maximum. If the current value is greater than the stored maximum, it updates the maximum. Finally, it outputs the largest number in the set.'

Key Markscheme Keywords: 'finds the largest/smallest', 'calculates total/average', 'validates input range'.

Tracing an Algorithm with a Trace Table
Q:

Given the following pseudocode, complete the trace table for inputs 10, 20, and 30.

total <- 0
FOR i <- 1 TO 3 DO
    INPUT num
    total <- total + num
NEXT i
PRINT total
A:

Trace Table:

i num (Input) total
1 10 10
2 20 30
3 30 60

Final Output: 60

Explanation:

  • Iteration 1: i=1. Input num=10. total becomes 0+10=10.
  • Iteration 2: i=2. Input num=20. total becomes 10+20=30.
  • Iteration 3: i=3. Input num=30. total becomes 30+30=60.
  • Loop ends. Print total.
Linear Search Algorithm

Purpose: To find a specific value (target) in an unsorted list.

How it works: It checks every element one by one from the start until the target is found or the end of the list is reached.

Pseudocode Structure:

found <- FALSE
index <- 0
WHILE (index < length OF list) AND (found = FALSE) DO
    IF list[index] = target THEN
        found <- TRUE
        PRINT "Found at index", index
    ELSE
        index <- index + 1
    ENDIF
ENDWHILE
IF found = FALSE THEN
    PRINT "Not found"
ENDIF
Efficiency: Linear Search is O(n), meaning time grows linearly with the input size. In the worst case (target is last or not present), it checks all n items.
Binary Search Algorithm

Prerequisite: The list MUST be sorted (ascending or descending).

Purpose: To find a target value in a sorted list much faster than linear search.

How it works:

  1. Compare the target with the middle element of the list.
  2. If they match, return the index.
  3. If the target is less than the middle element, ignore the right half and search the left half.
  4. If the target is greater than the middle element, ignore the left half and search the right half.
  5. Repeat until found or list is empty.
Efficiency: Binary Search is O(\log n). It halves the search space with each step. For 1,000,000 items, Linear Search might take 1,000,000 steps; Binary Search takes only ~20 steps.
Binary Search Trace Example
List: [10, 20, 30, 40, 50, 60, 70] (Indices 0 to 6)
Target: 42

Step Low Index High Index Mid Index (Low+High)//2 Mid Value Action
1 0 6 3 40 Target (42) > 40. Search right half. Low = 3+1 = 4.
2 4 6 5 60 Target (42) < 60. Search left half. High = 5-1 = 4.
3 4 4 4 50 Target (42) < 50. Search left half. High = 4-1 = 3.
4 4 3 - - Low > High. Loop ends. Not found.

Note: Indices are 0-based in this example. Always check if the question specifies 0-based or 1-based indexing.

⚠︎ Binary Search on Unsorted Data
The Error: Applying Binary Search to a list that is not sorted.

The Correction: Binary Search relies on the order of elements to eliminate half the list. If the list is unsorted, eliminating the 'right' or 'left' half might discard the target value.

Examiner Tip: If asked 'Why can't we use binary search here?', answer: 'Because the data is not sorted.' Do not say 'because it is too slow'—binary search is actually faster than linear search if the list were sorted.

Describing Bubble Sort Efficiency
Context: You are asked to compare Bubble Sort with other algorithms or describe its efficiency.

Why Examiners Accept This: They look for the specific complexity class and the reason for it.

Correct Phrase: 'Bubble Sort has a time complexity of O(n^2) in the worst case. This is because it uses nested loops: for each element, it compares it with every other adjacent element. As the number of items (n) increases, the number of comparisons increases quadratically.'

Key Markscheme Keywords: 'nested loops', 'quadratic time complexity', 'O(n^2)', 'compares adjacent elements'.

Bubble Sort Algorithm

Purpose: To sort a list of values in ascending (or descending) order.

How it works:

  1. Compare adjacent elements.
  2. If they are in the wrong order, swap them.
  3. Repeat this process for the entire list until no swaps are needed.

Pseudocode Structure:

FOR i <- 0 TO length OF list - 2 DO
    swapped <- FALSE
    FOR j <- 0 TO length OF list - 2 - i DO
        IF list[j] > list[j+1] THEN
            // Swap
            temp <- list[j]
            list[j] <- list[j+1]
            list[j+1] <- temp
            swapped <- TRUE
        ENDIF
    NEXT j
    IF swapped = FALSE THEN
        EXIT FOR // List is already sorted
    ENDIF
NEXT i
Optimization: The inner loop reduces by i each time because the largest elements 'bubble up' to the end and don't need to be checked again. The swapped flag allows early exit if the list is already sorted (best case O(n)).
Identifying Sorting Algorithm from Trace
Q:
The following trace shows a list [5, 2, 8, 1] being sorted. In Pass 1, the list becomes [2, 5, 1, 8]. Identify the sorting algorithm and explain why.
A:

Algorithm: Bubble Sort.

Explanation:

  • The largest value (8) has moved to the end of the list in the first pass.
  • This 'bubbling up' of the largest element is characteristic of Bubble Sort.
  • In a Selection Sort, the smallest value would move to the front. In an Insertion Sort, elements are inserted into their correct position one by one, not necessarily moving the max to the end in the first pass.
Algorithmic Efficiency (Big O Notation)

Definition: Big O notation describes how the runtime or space requirements of an algorithm grow as the input size (n) increases.

Common Complexities:

  • O(1): Constant time. Accessing an array index. Fastest.
  • O(\log n): Logarithmic time. Binary Search. Very efficient for large data.
  • O(n): Linear time. Linear Search. Time grows directly with input size.
  • O(n^2): Quadratic time. Bubble Sort, Selection Sort. Time grows with the square of input size. Inefficient for large n.
Key Distinction: Do not confuse 'exponential' (O(2^n)) with 'quadratic' (O(n^2)). Bubble Sort is quadratic, not exponential. Exponential algorithms are generally unusable for large inputs.
⚠︎ Confusing Flowchart Symbols
The Error: Using a Rectangle for Input/Output or a Diamond for Process.

The Correction:

  • Oval/Circle: Terminal (Start/End).
  • Parallelogram: Input/Output. Always use this for PRINT and INPUT.
  • Rectangle: Process (Calculation, Assignment).
  • Diamond: Decision (IF/ELSE conditions).

Examiner Tip: If you draw a rectangle for PRINT, you will lose marks. Examiners look specifically for the parallelogram shape for I/O operations.

Explaining Why an Algorithm is Maintainable
Context: You are asked to suggest how to make a program easier to maintain.

Why Examiners Accept This: Maintenance refers to future updates. Code that is hard to read is hard to fix.

Correct Phrases:

  • 'Use meaningful variable names (e.g., totalScore instead of t) so other programmers can understand the code without comments.'
  • 'Add comments to explain complex logic blocks.'
  • 'Use modular design (subroutines/functions) to break the problem into smaller, testable parts.'

Key Markscheme Keywords: 'readability', 'meaningful identifiers', 'modular', 'comments', 'documentation'.

Designing Test Data
Q:
A program accepts a password between 8 and 12 characters long. Give two pieces of test data and explain the purpose of each.
A:
Test Data 1: "abc" (Length 3)
Purpose: To check that the program rejects erroneous/abnormal data that is too short.

Test Data 2: "abcdefgh" (Length 8)
Purpose: To check boundary/extreme data. This is the minimum valid length, ensuring the program accepts the lower limit correctly.

Beta v0.7.8 Free while we're in beta — it transitions to paid post launch. Thank you for supporting us at this stage!