General Algorithms (Edexcel A-Level Further Mathematics): Revision Notes

Example 1: Flowchart Algorithm

Design a flowchart to determine whether a number is even or odd.

Steps:

1. Start.
2. Input $n$
3. Check $n \mod 2 = 0$

• If true, output "Even."
• If false, output "Odd."

4. End.

Pseudocode**:**

BEGIN
  Input n
  IF n MOD 2 = 0 THEN
    Output "Even"
  ELSE
    Output "Odd"
  ENDIF
END

Example 2: Determine the Order of an Algorithm

Problem:

Given an algorithm that multiplies two $n \times n$ matrices using three nested loops:

Solution:

5. Each loop runs $n$ times.
6. The total number of operations is proportional to $n \times n \times n = n^3$
7. Order: The algorithm is $O(n^3)$

Example 3: Shortest Path Algorithm

Find the shortest path between two nodes in a graph using Dijkstra's algorithm.

Order of the Algorithm:

Using a priority queue for efficient selection of the smallest distance:

• Priority queue operations take $O(\log n)$
• Processing all edges takes $O(E \log n)$, where $E$ is the number of edges.
• Thus, the algorithm's order is $O(E \log n)$

Common Mistakes

1. Misinterpreting flowcharts: Be careful with decision points; clearly follow branches.
2. Forgetting base cases: Recursive algorithms often fail without proper termination conditions.
3. Overlooking efficiency: Always analyse the time complexity of nested loops or iterative steps.
4. Incorrect initialisation: Ensure variables (e.g., distances in shortest path problems) are initialised correctly.
5. Confusing pseudocode with implementation: Pseudocode is for planning, not direct coding.

Key Formulas

1. Big-O Notation:

• $O(1)$: Constant time.
• $O(n)$: Linear time.
• $O(n^2)$: Quadratic time.
• $O(\log n)$: Logarithmic time.

2. Matrix Multiplication Complexity: $O(n^3)$ for standard nested-loop algorithms.

3. Graph Search Algorithms:

• Dijkstra's Algorithm: $O(E \log n)$
• Floyd-Warshall Algorithm: $O(n^3)$