A4 · Algorithm Design

Spec reference: Section A - Computational Thinking
Key idea: Design a precise, step-by-step strategy to solve a problem.

---

▶ Introduction to Algorithms

---

Designing a step-by-step strategy

Algorithm design usually follows this process:

1. Understand the problem - what are the inputs and outputs?
2. Decompose - break it into smaller steps.
3. Identify patterns - are any steps repeated?
4. Abstract - remove details not needed for the solution.
5. Write the algorithm - in pseudocode, structured English or a flowchart.
6. Trace/test - step through the algorithm manually with sample data.
7. Refine - fix any errors or inefficiencies found.

---

Properties of a good algorithm

Property	Meaning
Correct	Produces the right output for all valid inputs
Unambiguous	Each step has exactly one interpretation
Finite	It ends after a fixed number of steps
Efficient	It doesn't use more time or memory than needed
General	Works for the full range of valid inputs, not just one case

---

Algorithm design example

Problem: Find the largest number in a list.

Step 1: Understand the problem

• Input: a list of numbers
• Output: the largest number in that list

Step 2: Design the algorithm

1. Set largest = first element of the list
2. For each remaining element in the list:
   2a. If the element is greater than largest:
       Set largest = that element
3. Output largest

Step 3: Trace with sample data

List: [4, 9, 2, 7, 1]

Step	Current element	largest
Start	-	4
2a	9 > 4 → update	9
2a	2 < 9 → no change	9
2a	7 < 9 → no change	9
2a	1 < 9 → no change	9
Output	-	9 ✓

---

Algorithm efficiency

Not all correct algorithms are equally good. Efficiency describes how an algorithm's time or memory use grows as the input gets larger.

Term	Meaning
Time complexity	How many steps does the algorithm take?
Space complexity	How much memory does it use?
O(1)	Constant - always the same regardless of input size
O(n)	Linear - steps grow proportionally with input size
O(n²)	Quadratic - steps grow with the square of input size

Exam context

You don't need to calculate Big O formally, but you should understand that an algorithm that loops through a list twice is less efficient than one that loops through it once.

---

Expressing algorithms

Algorithms can be expressed in three ways - all are valid and each has its place:

Method	When to use
Structured English	Natural language, easiest to communicate to non-programmers
Pseudocode	More formal, closer to code - best for exam answers
Flowcharts	Visual - good for showing decision logic

We cover pseudocode in B1 · Pseudocode and flowcharts in B2 · Flowcharts.

---

Common mistakes in algorithm design

• Forgetting edge cases - what if the list is empty? What if two values are equal?
• Infinite loops - a loop with no exit condition will never terminate.
• Off-by-one errors - starting at index 1 instead of 0, or looping one iteration too many.
• Assuming the input is valid - always consider invalid or unexpected input.

---

Summary

Term	Meaning
Algorithm	A finite, ordered set of steps to solve a problem
Trace	Stepping through an algorithm manually with sample data to verify correctness
Efficiency	How well an algorithm uses time and memory as input size increases
Edge case	An unusual or extreme input that might cause an algorithm to fail

---

Test Yourself

Question 1 of 5

Which of the following is NOT a required property of an algorithm?