Welcome to the World of Algorithms!
Welcome to your first step into Decision Mathematics 1 (D1). You might be wondering, "What on earth is an algorithm?" Simply put, an algorithm is just a set of instructions to complete a task. Think of it like a recipe for baking a cake or the steps you follow to tie your shoelaces. If you follow the steps exactly, you get the same result every time!
In this chapter, we will look at how to organize data, find specific items, and pack things efficiently. These techniques are used every day by companies like Amazon to sort packages or Google to find search results.
1. The Basics: Flow Charts and Text
Algorithms can be written as a list of text instructions or shown visually as a flow chart. Don't worry if flow charts look like a maze at first; they are just a map of "Yes/No" decisions.
Important Prerequisite: Finding the Middle Item
In Edexcel D1, there is a specific rule for finding the middle item of a list. If a list has \(n\) items, the position of the middle item is found by calculating: \( \frac{n+1}{2} \).
If the result is not a whole number, you must round up.
Example:
If you have 5 items: \( \frac{5+1}{2} = 3 \). The 3rd item is the middle.
If you have 6 items: \( \frac{6+1}{2} = 3.5 \). You round up to 4. The 4th item is the middle.
Key Takeaway: Always follow the instructions exactly as written, even if you think you see a shortcut. In the exam, the marks are for showing the process, not just the final answer!
2. Sorting Algorithms: Bubble Sort
The Bubble Sort is a simple way to put a list of numbers in order (either ascending/smallest to largest or descending/largest to smallest).
How it works:
1. Start at the beginning of the list.
2. Compare the first two numbers. If they are in the wrong order, swap them. If not, leave them.
3. Move to the next pair (2nd and 3rd) and repeat until you reach the end of the list. This is called a pass.
4. At the end of the first pass, the largest number will have "bubbled" to the end.
5. Repeat the passes until a pass happens with no swaps at all. This means the list is sorted!
Memory Aid: Think of heavy bubbles sinking to the bottom (the end of the list) or light bubbles rising to the top.
Common Mistake: Students often stop as soon as the list looks sorted. You must complete one final pass with "no swaps" to prove to the algorithm that it is finished!
3. Sorting Algorithms: Quick Sort
The Quick Sort is much faster than the Bubble Sort for long lists, but it requires a bit more concentration. It uses a pivot to split the list.
Step-by-Step Process:
1. Pick a Pivot: Following the Edexcel rule, choose the middle item of your list (using the \( \frac{n+1}{2} \) rule).
2. The Split: Write down all numbers smaller than the pivot to its left and all numbers larger than the pivot to its right. (This creates two sub-lists).
3. Repeat: Treat each sub-list as a new mini-list and pick a new pivot for each.
4. Identify: Once an item has been chosen as a pivot, it is in its final sorted position. Usually, we mark these with a box or circle.
Quick Review:
- Bubble Sort: Slow, compares adjacent pairs, needs a "no swap" pass.
- Quick Sort: Fast, uses pivots, splits the list into smaller parts.
4. Searching Algorithms: Binary Search
Imagine you are looking for a word in a dictionary. You don't start at page 1 and read every word, right? You jump to the middle and decide if your word is before or after that page. That is a Binary Search.
CRITICAL RULE: You can only use a Binary Search on a list that is already sorted. If the list is jumbled, the search won't work!
The Process:
1. Find the middle item of the whole list.
2. Is this your target value? If yes, stop!
3. If your target is smaller than the middle, discard the middle and the entire right half of the list.
4. If your target is larger than the middle, discard the middle and the entire left half of the list.
5. Repeat with the remaining half until you find the value or have no items left (meaning the value isn't there).
Did you know? A Binary Search is incredibly efficient. Even if you had a list of 1,000,000 items, you could find any item in just 20 steps!
5. Bin Packing
Bin Packing is about fitting items of different sizes into "bins" of a fixed capacity. For example, fitting files onto USB sticks or boxes into a delivery van.
Method A: First-Fit
Take each item in the order given and put it into the first bin that has enough space.
Analogy: Being a "lazy" packer—just grabbing the next item and shoving it into the first gap you see.
Method B: First-Fit Decreasing
1. First, sort the list into descending order (largest to smallest).
2. Then, apply the First-Fit algorithm.
Analogy: This is like a professional packer—putting the big, awkward items in first so the small ones can fill the gaps. This usually uses fewer bins!
Key Takeaway for Bin Packing: Always check your subtraction! A common mistake is thinking an item fits in a bin when there is actually 1 unit too little space left.
Summary Quick-Check
- Algorithm: A set of instructions.
- Middle Item: \( \frac{n+1}{2} \), round up.
- Bubble Sort: Compare pairs, need a "no swap" pass to finish.
- Quick Sort: Uses pivots to divide and conquer.
- Binary Search: Only works on sorted lists; keeps halving the search area.
- First-Fit Decreasing: Sort largest-to-smallest first, then pack.
Don't worry if these processes feel a bit repetitive at first—that's exactly what an algorithm is designed to be! Keep practicing the steps, and you'll find these are some of the most reliable marks you can get in your Further Maths exam.