Show understanding that an algorithm is a solution to a problem expressed as a sequence of defined steps

9.2 Algorithms

Objective

Show understanding that an algorithm is a solution to a problem expressed as a sequence of defined steps.

What is an Algorithm?

An algorithm is a finite, well‑defined set of instructions that, when followed, solves a particular problem or performs a specific task. It must be:

• Unambiguous – each step is clear and has a single interpretation.
• Finite – it terminates after a limited number of steps.
• Effective – each step is simple enough to be carried out, in principle, by a human using pencil and paper.

Key Characteristics

Representing Algorithms

Algorithms can be expressed in several forms, each useful for different purposes.

Pseudocode

Pseudocode is a high‑level, language‑independent description that mixes natural language with programming constructs.

// Example: Find the maximum value in an array A[1..n]
INPUT: array A, integer n
max ← A[1]
FOR i ← 2 TO n DO
IF A[i] > max THEN
max ← A[i]
END IF
END FOR
OUTPUT max

Flowcharts

Flowcharts use standardized symbols to illustrate the control flow of an algorithm.

Mathematical Notation

Some algorithms are described using formal mathematical expressions. For example, the Euclidean algorithm for the greatest common divisor (GCD) can be written as:

\$\$\text{gcd}(a,b) =

\begin{cases}

a, & \text{if } b = 0\\[4pt]

\text{gcd}(b, a \bmod b), & \text{otherwise}

\end{cases}\$\$

Example Algorithms

1. Linear Search

Searches for a target value \$x\$ in an unsorted list \$L\$ of length \$n\$.

1. Set \$i \leftarrow 1\$.
2. While \$i \le n\$:

   1. If \$L[i] = x\$, output “found at position \$i\$” and stop.
   2. Otherwise set \$i \leftarrow i + 1\$.

3. If the loop ends, output “not found”.

2. Binary Search (sorted list)

Assumes \$L\$ is sorted in ascending order.

INPUT: sorted array L[1..n], target x
low ← 1
high ← n
WHILE low ≤ high DO
mid ← ⌊(low + high) / 2⌋
IF L[mid] = x THEN
OUTPUT mid
STOP
ELSE IF L[mid] < x THEN
low ← mid + 1
ELSE
high ← mid - 1
END IF
END WHILE
OUTPUT “not found”

Analyzing Algorithms

Two primary measures are used:

• Time complexity – how the running time grows with input size \$n\$.
• Space complexity – how much additional memory is required.

Big‑O notation provides an upper bound on growth rates. For example:

• Linear search: \$O(n)\$ time, \$O(1)\$ space.
• Binary search: \$O(\log n)\$ time, \$O(1)\$ space.

Why Algorithms Matter in Computer Science

Algorithms are the bridge between problem statements and executable programs. Understanding how to design, represent, and analyse algorithms equips students to:

1. Choose the most appropriate solution for a given problem.
2. Predict performance and resource requirements.
3. Communicate solutions clearly to peers and to a computer.

Summary Checklist

• Can you define an algorithm and list its essential properties?
• Are you able to write a simple algorithm in pseudocode?
• Do you know how to illustrate an algorithm with a flowchart?
• Can you analyse the time and space complexity using Big‑O notation?