Problem Solving
Develop computational thinking skills to understand how computer systems work, and design, implement and analyse algorithms for solving real problems.
Students must use the pseudocode command set (Appendix 5) and flowchart symbols (Appendix 6) specified in the specification. Students should be given repeated opportunities to tackle computational problems of various sorts, including some substantial problem-solving tasks involving design, implementation and evaluation.
What is an Algorithm? (1.1.1)
An algorithm is a precise, step-by-step set of instructions used to solve a problem or complete a task. Every algorithm must eventually terminate and produce a correct result. Algorithms are used everywhere in computing — from sorting data to powering search engines.
Algorithms can be expressed in multiple forms, each useful in different contexts:
- Flowcharts — diagrammatic representation using standard symbols.
- Pseudocode — structured English-like notation.
- Written descriptions — plain English explanation.
- Program code — actual code in a language like Python, C# or Java.
Creating Algorithms (1.1.2)
When creating an algorithm to solve a problem, you must use appropriate programming constructs:
Good algorithm design also requires choosing the appropriate notation — flowchart for visual representation, pseudocode for structured planning, or draft code when moving towards implementation.
Understanding Purpose (1.1.3)
- What problem it is solving
- What data it takes as input
- What output it produces
- The role of each step or section
- What happens at each iteration of a loop
- What condition is tested in each selection
Determining Output (1.1.4)
Given an algorithm and a specific set of input data, you must be able to dry-run (trace) through the algorithm step by step and determine the exact output produced. This requires careful attention to sequence, selection branches, loop counts and variable values.
Identifying and Correcting Errors — Trace Tables (1.1.5)
A trace table is a debugging tool. You create a column for each variable and fill in each cell as you step through the code line by line. Example tracing a loop that sums numbers 1 to 4:
| Line | i | total | Output |
|---|---|---|---|
| SET total TO 0 | – | 0 | – |
| FOR i FROM 1 TO 4 | 1 | 0 | – |
| SET total TO total + i | 1 | 1 | – |
| FOR i FROM 1 TO 4 | 2 | 1 | – |
| SET total TO total + i | 2 | 3 | – |
| FOR i FROM 1 TO 4 | 3 | 3 | – |
| SET total TO total + i | 3 | 6 | – |
| FOR i FROM 1 TO 4 | 4 | 6 | – |
| SET total TO total + i | 4 | 10 | – |
| SEND total TO DISPLAY | 4 | 10 | 10 |
Types of errors: logic errors, incorrect loop bounds, wrong variable updated, incorrect condition in IF statement.
Coding algorithms in high-level language
An algorithm written in pseudocode or a flowchart must be translated into actual program code. The programmer must understand the syntax of their chosen language.
Data structures influence algorithm choice
- Binary search requires a sorted array
- Merge sort works best with linked lists
- Bubble sort acceptable for small, nearly-sorted datasets
Evaluating algorithms
- Correct output for all valid inputs?
- Handle edge cases?
- Efficient enough?
- Readable and maintainable?
Bubble Sort Sorting
Repeatedly steps through list, compares adjacent elements and swaps if out of order. Pass repeats until no swaps needed.
- O(n²) time complexity
- Simple, works on any unsorted list
- Best case O(n) if already sorted
Merge Sort Sorting
Divide-and-conquer. Splits list into halves, recursively sorts, then merges back in order.
- O(n log n) time complexity
- Consistent performance
- Requires extra memory for merging
Linear Search Searching
Checks each element sequentially until target found or end reached. Works on unsorted/sorted data.
- O(n) worst case
- No pre-sorting required
- Simple to implement
Binary Search Searching
Requires sorted data. Repeatedly halves search space by comparing to middle element.
- O(log n) time complexity
- Very efficient for large sorted datasets
- Cannot be used on unsorted lists
Comparing Bubble Sort vs Merge Sort
Bubble Sort — Simple, low memory, O(n²). Suitable for small/nearly-sorted data.
Merge Sort — Complex, O(n log n), extra memory, suitable for large datasets.
Comparing Linear Search vs Binary Search
Linear Search — Works on any data, O(n). Use for unsorted/small lists.
Binary Search — Requires sorted data, O(log n). Use when data is already sorted.
The Three Programming Constructs
- Sequence — Instructions executed in order.
- Selection — Decision making (IF/ELSE).
- Iteration — Loops (FOR, WHILE, REPEAT).
Analysing a Problem (1.2.1)
Before writing any algorithm, clearly identify: Inputs, Outputs, Processing, Initialisation, Storage.
Decomposition (1.2.2)
Breaking a large problem into smaller sub-problems. Benefits: easier design, parallel development, modular code, easier debugging.
Example: School management system → student records, attendance, grading, reports, login.
Abstraction (1.2.3)
Removing unnecessary detail to focus on essential features. Examples: maps, bank account models, game physics abstraction.
Programming Abstractions (1.2.4)
Take real-world scenario and program an abstraction: identify relevant data/behaviours, choose data types, write algorithms to model them.
Computational Thinking — The Four Pillars
Decomposition — break into smaller parts.
Abstraction — focus on essential features.
Pattern Recognition — identify similarities across problems.
Algorithm Design — plan step-by-step solution.
Flowchart Symbols (Appendix 6)
- Rounded rectangle (oval) — START/END
- Rectangle — Process
- Diamond — Decision (YES/NO)
- Parallelogram — Input/Output
- Arrow — Flow direction
- Rectangle with double lines — Subprocess