Welcome to the World of Algorithms!
Welcome to Unit D1: Decision Mathematics 1. We are starting with Algorithms. Don't let the name scare you—an algorithm is simply a set of "step-by-step instructions" to solve a problem. Think of it like a recipe for baking a cake or the instructions for building a Lego set. If you follow the steps exactly, you get the right result every time!
In this chapter, we will learn how to describe these instructions and look at specific ways to pack, sort, and search through data. These techniques are used every day by companies like Amazon to pack delivery trucks or by Google to sort search results.
1. What exactly is an Algorithm?
An algorithm is a finite sequence of precise instructions that leads to a solution. In your exam, algorithms are usually shown in two ways:
1. Textual instructions: A numbered list of steps.
2. Flow charts: A visual map of the steps.
Flow Chart Symbols
To read a flow chart, you just need to know what the shapes mean:
• Ovals: Start or Stop.
• Rectangles: Instructions (e.g., "Add 1 to X").
• Diamonds: Decisions (e.g., "Is X > 10?"). These always have "Yes" and "No" arrows coming out of them.
Quick Review: An algorithm must be finite (it has to end), precise (no guessing!), and effective (it must solve the problem).
2. Bin Packing Algorithms
Imagine you have a set of items of different weights and you need to pack them into bins that can only hold a certain maximum weight. The goal is to use as few bins as possible. This is called the Bin Packing Problem.
Method A: First-Fit
This is the "lazy" way. You take each item in the order given and put it into the first bin that has enough space for it.
The Trap: You must always check Bin 1, then Bin 2, then Bin 3, and so on. Don't just skip to a new bin because the previous one looks full!
Method B: First-Fit Decreasing
This is usually more efficient.
1. First, sort the items into descending order (largest to smallest).
2. Then, apply the First-Fit algorithm to this sorted list.
Analogy: If you are packing a suitcase, you put the big boots in first and fit the socks in the gaps later!
Method C: Full-Bin
This is the "puzzle" way. You look for combinations of items that will exactly fill a bin.
Example: If your bin capacity is 10, and you have items of 7, 3, 4, and 6, you pair (7+3) and (6+4) to fill two bins perfectly.
Key Takeaway: First-Fit is fast but messy. First-Fit Decreasing is usually better but requires you to sort the list first. Full-Bin is the best but can be hard to do with very long lists.
3. Sorting Algorithms
Sometimes we have a messy list of numbers and we need to put them in order. We use Sorting Algorithms for this.
The Bubble Sort
Think of this like bubbles rising in a glass of soda. The "heaviest" (largest) numbers sink to the end of the list one by one.
How it works:
1. Compare the first two numbers. If the first is bigger than the second, swap them.
2. Move to the next pair (2nd and 3rd) and repeat.
3. Once you reach the end of the list, the largest number is in its final position. This is one pass.
4. Repeat the passes until a pass happens with no swaps.
The Quick Sort
This is much faster for big lists. It uses a pivot to split the list.
Important Edexcel Rule: For your exam, the pivot is always the middle item of the list. If there is an even number of items, choose the item to the right of the center.
Steps:
1. Pick your pivot.
2. Create two sub-lists: items smaller than the pivot go to the left; items larger than the pivot go to the right.
3. Repeat this process for each sub-list until every item has been a pivot.
Memory Aid: "Pick, Partition, Repeat!"
Common Mistake: In Quick Sort, don't change the relative order of the items when you move them to the left or right of the pivot. If '5' was before '3' in the original list and both are smaller than the pivot, '5' should still be before '3' in the new sub-list.
4. Searching Algorithms: Binary Search
If you have a sorted list, you can find a specific item very quickly using a Binary Search.
Analogy: If you are looking for the word "Mathematics" in a dictionary, you don't start at page 1. You open the middle, see if you are too far or not far enough, and throw away the half you don't need!
How to find the Middle Item
The syllabus requires a specific method. If a list has \(n\) items:
The position of the middle item is \(\frac{n+1}{2}\).
If this is not a whole number, round it up.
Example: In a list of 10 items, \(\frac{10+1}{2} = 5.5\). Round up to 6. The 6th item is your middle.
Step-by-Step Binary Search:
1. Find the middle item of the list.
2. If it's the item you want, Stop.
3. If the item you want is smaller, discard the middle item and everything to its right.
4. If the item you want is larger, discard the middle item and everything to its left.
5. Repeat with the remaining "half" of the list until you find the item or the list is empty (meaning the item isn't there).
Quick Review Box:
• Prerequisite: The list MUST be sorted before you can use Binary Search.
• If the list is messy: You must use Bubble Sort or Quick Sort first!
• Efficiency: Binary Search is extremely fast because it cuts the search area in half every single time.
Summary Checklist
Before moving on to the next chapter, make sure you can:
• Explain what an algorithm is.
• Follow a flow chart or a list of text instructions accurately.
• Use First-Fit and First-Fit Decreasing to pack items into bins.
• Perform a Bubble Sort (remembering to stop only when a pass has 0 swaps).
• Perform a Quick Sort (always using the middle item as the pivot).
• Use Binary Search to find an item in a sorted list (remembering the \(\frac{n+1}{2}\) rule).
Don't worry if these seem a bit tedious at first! The key to Decision Mathematics is being methodical. Use a pencil, take your time, and double-check your swaps!