Welcome to the World of Algorithms!
Welcome to the first chapter of Discrete Mathematics. Don’t let the name "Further Maths" intimidate you—algorithms are actually something you use every single day! Whether you are following a recipe to bake a cake, following GPS directions, or even just deciding what to wear based on the weather, you are using an algorithm. In this chapter, we will learn how to write these "mathematical recipes" clearly, how to test them, and how to figure out which ones are the fastest.
1. What is an Algorithm?
At its simplest, an algorithm is a set of step-by-step instructions used to solve a specific problem. For a process to be a true algorithm, it must have three things:
1. Input: Something you start with (like a list of numbers).
2. Output: Something you end with (like the sorted list).
3. Finiteness: It must eventually stop! An instruction that goes on forever isn't helpful.
Key Types of Strategies
Sometimes, we have different "mindsets" when creating an algorithm:
• Greedy: This algorithm makes the best possible choice at each individual step, hoping it leads to the best overall result. Analogy: If you were picking coins to make 40p, a greedy algorithm would grab the biggest coin first (a 20p), then another (20p).
• Heuristic: These are "rules of thumb." They might not give the perfect, most optimal answer every time, but they are very fast and "good enough" for big problems.
• Recursive: This is an algorithm that "calls itself." It breaks a big problem down into a smaller version of the same problem. Analogy: To clean a whole house, clean one room, then "call" the instruction to clean the rest of the house.
Quick Review: The Checklist
• Is it Deterministic? (Does the same input always give the same output?)
• Does it have a Stopping Condition? (A rule that tells the "counter" when to quit.)
• Does it have a Counter? (A way to keep track of how many times a step has been repeated.)
Key Takeaway: An algorithm is a finite, predictable set of instructions that turns an input into an output.
2. Tracing and Working with Algorithms
In your exam, you will often be asked to "trace" an algorithm. This means acting like a computer and following the instructions exactly, even if you think you know a shortcut!
Tools for Tracing
Algorithms can be shown as Flow Diagrams (using boxes and arrows) or Pseudo-code (instructions written in English-like math language). You will need to know two specific functions:
• INT(x): This is the "floor" function. It rounds any number down to the nearest whole number. For example, \( INT(4.7) = 4 \) and \( INT(5.99) = 5 \).
• ABS(x): This is the "absolute value." It ignores the minus sign. For example, \( ABS(-3) = 3 \) and \( ABS(3) = 3 \).
Key Takeaway: Tracing requires a Trace Table. Use a new row every time a variable (like \( x \) or \( y \)) changes its value.
3. The Order of an Algorithm (Efficiency)
Not all algorithms are created equal. Some take much longer than others as the "size" of the problem (denoted as n) gets bigger. We measure this using Big O Notation.
Understanding Big O
If an algorithm has a run-time formula of \( T(n) = n^2 + 5n + 10 \), we say its Order is \( O(n^2) \). Why? Because as \( n \) becomes huge (like a million), the \( n^2 \) part becomes so much bigger than the others that the \( 5n \) and \( 10 \) don't really matter anymore. We call the highest power the dominant term.
The Hierarchy of Orders
From fastest (most efficient) to slowest (least efficient):
\( O(1) \) [Constant] \( \subset O(\log n) \) [Logarithmic] \( \subset O(n) \) [Linear] \( \subset O(n \log n) \) \( \subset O(n^2) \) [Quadratic] \( \subset O(n^3) \) [Cubic] \( \subset O(a^n) \) [Exponential] \( \subset O(n!) \) [Factorial]
Did you know? An exponential algorithm \( O(2^n) \) is so slow that if \( n=100 \), it would take longer than the age of the universe to finish on a normal computer!
Math Trick: Sum of Integers
When analyzing how many comparisons a sorting algorithm makes, you often need this formula:
The sum of the first \( n \) integers is \( \sum_{r=1}^n r = \frac{1}{2}n(n+1) \).
Since the highest power here is \( n^2 \), many simple sorting algorithms are of Quadratic Order \( O(n^2) \).
Key Takeaway: Efficiency is about how the run-time scales. If an \( O(n^2) \) algorithm takes 4 seconds for 10 items, it will take \( 2^2 = 4 \) times longer (16 seconds) if you double the items to 20.
4. Sorting Algorithms
Sorting is the most common task in computing. You need to know three main methods:
A. Bubble Sort
You compare the first two items. If they are in the wrong order, swap them. Then move to the next pair. By the end of the first "pass," the largest item has "bubbled" to the end.
• Efficiency: \( O(n^2) \). It's simple but slow for big lists.
B. Shuttle Sort
Similar to Bubble Sort, but once you make a swap, you immediately check the items behind it to see if that swapped item needs to move even further back.
• Efficiency: Also \( O(n^2) \), but often does fewer swaps than Bubble Sort in practice.
C. Quick Sort (Stage 2)
You pick a "pivot" (usually the first item). You put all items smaller than the pivot to its left and all items larger to its right. Then you repeat this for the two new lists created.
• Efficiency: Usually very fast, but worst-case it is \( O(n^2) \).
Key Takeaway: Always start sorting from the left unless the question tells you otherwise!
5. Packing Algorithms (Bin Packing)
This is about fitting items of different sizes into "bins" of a fixed capacity. It's like trying to pack a suitcase efficiently.
The Strategies (Heuristics)
• Next-Fit: Put items into the current bin until the next one doesn't fit. Close that bin and move to a new one. (You never go back to old bins).
• First-Fit: For each new item, try to fit it into the first bin you started with. Only start a new bin if it won't fit in any existing bin.
• First-Fit Decreasing (FFD): Sort your items into descending order first, then use First-Fit. This is usually the most efficient "offline" method.
• Full Bin: A "manual" search for combinations of items that fill a bin exactly to 100% capacity.
Memory Aid: Online vs. Offline
• Online: You pack items as they arrive (Next-Fit, First-Fit).
• Offline: You see all the items first and can sort them (FFD).
Key Takeaway: FFD is usually best, but you must remember to sort the list first, or you'll lose marks!
6. The Knapsack Problem
Imagine you are a thief with a bag (knapsack) that can only hold a certain weight. You want to pick items that give you the maximum profit without breaking the bag.
This is a classic optimisation problem. You have to balance the mass of an item against its value.
Quick Review Takeaway: Algorithms are tools. We use Tracing to check they work, Big O to check they are fast, and Heuristics to solve tricky problems like packing and sorting.