Welcome to the World of Algorithms!
Welcome to the first step in your Discrete Mathematics journey! Don’t let the name "Algorithms" intimidate you. In simple terms, an algorithm is just a set of instructions used to solve a problem—exactly like a recipe for baking a cake or the steps you follow to tie your shoelaces.
In this chapter, we are going to learn how to communicate these instructions clearly, how to measure how "fast" an algorithm is, and look at some classic methods for sorting data and finding the best routes through networks. Let’s dive in!
1. What Makes an Algorithm?
Before we start writing them, we need to know what a "good" algorithm looks like. According to the OCR syllabus, every algorithm must be:
• Finite: It must eventually stop. A recipe that tells you to "stir forever" isn't a good algorithm!
• Deterministic: If you follow the same steps with the same starting data, you should always get the exact same result.
• Input/Output: It needs something to start with (input) and should give you an answer at the end (output).
Key Terms to Remember
Greedy Algorithm: This type of algorithm makes the "best" choice at every single step without looking ahead. Imagine being at a buffet and always taking the biggest slice of pizza available right now—that’s a greedy approach!
Heuristic: This is a "rule of thumb" or a shortcut. It might not give the 100% perfect answer every time, but it’s usually "good enough" and much faster than checking every possibility.
Recursive: This is when an algorithm calls itself. Think of a set of Russian nesting dolls; to get to the center, you have to keep opening a smaller version of the same doll.
Quick Review: The Basics
Input → Algorithm (Instructions) → Output
Example: Ingredients → Recipe → Cake
2. Working with Algorithms: Trace and Interpret
One of the most important skills is "tracing" an algorithm. This means acting like a computer and following the instructions line-by-line using a trace table.
Algorithms can be shown as flow diagrams (using boxes and arrows) or pseudo-code (instructions written in a style that looks like computer code but uses plain English).
Mathematical Tools You’ll Need
In pseudo-code, you will often see these two functions:
1. \( \text{INT}(x) \): This tells you to round down to the nearest whole number. For example, \( \text{INT}(4.7) = 4 \) and \( \text{INT}(4.1) = 4 \).
2. \( \text{ABS}(x) \): This is the "absolute value." It just makes the number positive. So, \( \text{ABS}(-5) = 5 \) and \( \text{ABS}(5) = 5 \).
Don't worry if this seems tricky at first! Tracing is just about being organized. Use a table with a column for each variable and update the values as you go.
Key Takeaway: Tracing helps you understand what an algorithm is actually achieving without having to build it on a computer.
3. Sorting Strategies: Putting Things in Order
Sorting is a huge part of discrete maths. We focus on two main methods: Bubble Sort and Shuttle Sort. Both start from the left-hand end of the list.
The Bubble Sort
Imagine the largest numbers are "heavy" and sink to the bottom (the end of the list), while the smaller numbers "bubble" to the top.
1. Compare the first two items. If the first is bigger, swap them.
2. Move one step to the right and compare the next pair. Repeat until you reach the end.
3. The last number is now in the correct place. Repeat the whole process for the remaining numbers.
The Shuttle Sort
Think of this as "shuttling" a number back to its correct position as soon as you find it.
1. Compare the first and second items. Swap if needed.
2. Now look at the third item. Compare it with the second. If it needs to move left, swap it, then compare it with the first.
3. Basically, for every new item you look at, you keep swapping it to the left until it hits a number smaller than itself.
Common Mistake: In a Bubble Sort, many students forget that even if the list looks sorted, the algorithm must finish its "passes" or have a specific "stopping condition" (like a pass with no swaps) to officially end.
Key Takeaway: Both sorting algorithms are "quadratic," meaning if you double the number of items, the time it takes roughly quadruples!
4. Packing Problems: Fitting it All In
How do we fit items into bins of a certain size? These are heuristic (shortcut) methods. They are usually "online" (you pack items as they arrive) or "offline" (you look at all items before starting).
• Next-Fit (Online): Put the item in the current bin. If it doesn't fit, close that bin forever and start a new one.
• First-Fit (Online): Try to put the item in the first bin created. If it doesn't fit, try the second, then the third, and so on. Only start a new bin if it won't fit in any existing one.
• First-Fit Decreasing (Offline): Sort the items into descending order first (biggest to smallest), then use the First-Fit method. This usually gives a much better result!
• Full Bin (Heuristic): Look for combinations of items that will fill a bin exactly to 100% capacity.
Did you know? First-Fit Decreasing is "offline" because you have to know all the items in advance to sort them. Next-Fit is "online" because you could be packing boxes as they come off a conveyor belt!
5. The "Order" of an Algorithm (Big O Notation)
We need a way to measure efficiency. We use Order notation, like \( O(n^2) \) or \( O(n^3) \), where \( n \) is the "size" of the problem (e.g., the number of items in a list).
• If an algorithm is \( O(n) \), and you double the items, it takes 2x longer.
• If it is \( O(n^2) \), and you double the items, it takes 4x longer (\( 2^2 \)).
• If it is \( O(n^3) \), and you double the items, it takes 8x longer (\( 2^3 \)).
Memory Aid: When looking at a formula for run-time, like \( T(n) = 3n^2 + 5n + 10 \), the order is determined by the "dominant term" (the one with the highest power). So this would be \( O(n^2) \).
Key Takeaway: Knowing the order allows you to predict how long a massive computer task will take based on a small test run.
6. Network Algorithms: Finding the Best Path
Prerequisite: Remember that a network is just a graph with "weights" (numbers) on the edges, like distances or costs.
Dijkstra’s Algorithm (Shortest Path)
This finds the shortest route between a starting node and every other node. It is a greedy algorithm because it always picks the "closest" unvisited node next.
• Order: Quadratic, \( O(n^2) \), where \( n \) is the number of vertices.
Minimum Connector (Spanning Trees)
This is about connecting every single node in a network using the minimum total weight of edges. Think of connecting houses to a water main using the least amount of pipe.
1. Kruskal’s Algorithm: Always pick the shortest edge available anywhere in the graph, as long as it doesn't create a "cycle" (a closed loop).
2. Prim’s Algorithm: Start at one node. Always pick the shortest edge that connects a node you’ve "visited" to a node you "haven’t visited" yet.
Quick Review: Dijkstra vs. Prim/Kruskal
• Use Dijkstra to find a route from A to B.
• Use Prim or Kruskal to link everything together as cheaply as possible.
Key Takeaway: Prim’s and Kruskal’s algorithms both find the Minimum Spanning Tree (MST) but use different strategies. Both have cubic order, \( O(n^3) \).
Summary Table of Algorithm Orders
• Sorting (Bubble/Shuttle): \( O(n^2) \) (Quadratic)
• Shortest Path (Dijkstra): \( O(n^2) \) (Quadratic)
• Minimum Connector (Prim/Kruskal): \( O(n^3) \) (Cubic)
You've reached the end of the Algorithms chapter! Keep practicing your trace tables and sorting passes—consistency is the key to mastering Discrete Maths. You've got this!