Welcome to the World of Algorithms!
In this chapter, we are exploring the "engine room" of modern technology. From how Netflix recommends a show to how delivery trucks find the fastest route, algorithms are everywhere. In Further Mathematics, we study them to understand not just how to solve a problem, but how to do it efficiently. Don't worry if this seems a bit "computer-sciencey" at first—we will break it down into simple, logical steps!
1. What is an Algorithm?
At its heart, an algorithm is just a set of instructions. Think of it like a recipe for baking a cake: if you follow the steps exactly, you should get the same result every time.
Key Features of an Algorithm:
- Finiteness: It must have a clear beginning (Initial State) and an end. It shouldn't run forever!
- Input: The data you give it to start with.
- Output: The result or solution it produces.
- Variables: Temporary "storage boxes" for numbers or labels that change as the algorithm runs.
How Algorithms are Presented:
You will usually see algorithms in three formats:
- Written English: Step-by-step instructions in plain language.
- Flowcharts: A visual map using boxes and arrows.
- Pseudocode: A halfway house between English and computer code (e.g., "Let \(i = i + 1\)" means replace the current value of \(i\) with a value one higher).
Quick Review: An algorithm must be finite (it must terminate) and deterministic (following the steps lead to a specific outcome).
2. Algorithmic Complexity
Not all algorithms are created equal. Some are fast, and some are very slow when the "size" of the problem gets bigger. This is what we call Complexity.
The "Big O" Notation
We use Order Notation to describe how the time taken by an algorithm grows as the input size (\(n\)) grows. For this course, you specifically need to know about Quadratic Complexity, written as \(O(n^2)\).
Example: If you have a list of 10 items and it takes 100 seconds to sort, but a list of 20 items takes 400 seconds, the time is increasing by the square of the factor change (\(2^2 = 4\)). This is \(O(n^2)\) behavior.
Common Mistake to Avoid: Don't confuse "size of the problem" with the "value of the numbers." If you are sorting a list, \(n\) is how many numbers are in the list, not how big the numbers themselves are.
3. Sorting Algorithms: Quick Sort
Sorting is the most common task for an algorithm. The Quick Sort is a powerful method that uses a pivot to divide a list into smaller parts.
How to perform a Quick Sort (Ascending):
- Pick a pivot (usually the first or middle item in the list).
- Compare every other item to the pivot.
- Move items smaller than the pivot to a sub-list on the left and larger items to a sub-list on the right.
- The pivot is now in its final correct position.
- Repeat the process for the new sub-lists until every item has been a pivot.
Important Points:
- Comparisons: Every time you ask "is this number bigger than the pivot?", that is one comparison.
- Swaps: Every time you move an item, that counts as a swap.
- Worst Case: The worst-case complexity for Quick Sort is \(O(n^2)\).
Key Takeaway: Once a number is chosen as a pivot and the sub-lists are formed, that pivot stays exactly where it is for the rest of the algorithm!
4. Packing Algorithms (Bin Packing)
Imagine you have several items of different weights and you want to put them into bins that have a weight limit. This is a classic "optimisation" problem.
Heuristic Algorithms
A heuristic is a "rule of thumb" algorithm. It’s a method that finds a good solution quickly, but it doesn't guarantee the perfect (optimal) solution. We use these when the perfect solution would take a computer too many years to calculate!
Three Strategies You Need to Know:
- First Fit (FF): Take each item in the order given and put it into the first bin that has enough space.
- First Fit Decreasing (FFD): First, sort the items into descending order (largest to smallest), then use the First Fit method. This is usually much more efficient!
- Full Bin: Look for combinations of items that will fill a bin exactly to its capacity. Do these first, then pack the rest.
Analogy: First Fit is like packing a grocery bag as you pick items off the shelf. First Fit Decreasing is like laying all your groceries on the counter first and putting the big cereal boxes in before the small chocolate bars.
Did you know? Both First Fit and First Fit Decreasing have a worst-case complexity of \(O(n^2)\).
5. Proving and Repairing Algorithms
How do we know if an algorithm actually works for every possible input? We use mathematical proof.
Proof by Exhaustion
If there are only a small number of possible inputs, you can simply test every single one. If they all work, the algorithm is proven correct for that set of data.
Disproof by Counter-example
To show an algorithm is incorrect, you only need to find one specific example where it fails. For example, if a packing algorithm claims to always use the minimum number of bins, but you find one list where it uses three bins instead of two, you have disproved it!
Key Takeaway: If you are asked to "repair" an algorithm, look for the step where a logic error occurs—often it's a "greater than" sign that should be "greater than or equal to," or an index that starts at 1 instead of 0.
Summary: The Essentials
- Algorithms are finite, logical sets of instructions.
- Complexity \(O(n^2)\) means if the input doubles, the time taken roughly quadruples.
- Quick Sort uses pivots to organize lists; it is efficient but has an \(O(n^2)\) worst case.
- Bin Packing uses heuristics (FF or FFD) to find solutions that are good, even if not perfect.
- Proof: Use exhaustion to prove a small case; use a counter-example to disprove a general rule.