Welcome to the World of Algorithms!
Welcome! In this chapter of Modelling with Algorithms, we are going to explore the "recipes" of the mathematical world. Whether you are using a GPS to find the quickest route home or a computer is sorting through millions of files, there is an algorithm working behind the scenes.
Don’t worry if you’ve never coded before or if "Big O notation" sounds like a different language. We are going to break these concepts down into simple, logical steps that anyone can follow. Let’s get started!
1. What is an Algorithm?
At its simplest, an algorithm is just a finite sequence of instructions to solve a specific problem. Think of it like a recipe for baking a cake: you start with ingredients (input), follow steps in order (process), and end up with a cake (output).
Key Components:
- Initial State: Where you start.
- Input: The data you give the algorithm (e.g., a list of numbers).
- Output: The final result the algorithm produces.
- Variable: A "storage box" for a value that can change as the algorithm runs (e.g., "Let \(i = i + 1\)" means update the box labeled \(i\)).
- Finite: This is crucial! An algorithm must eventually stop. It cannot run forever.
Analogy: Imagine you are teaching a robot to make a cup of tea. You can't just say "make tea." You have to say: 1. Boil water. 2. Put tea bag in cup. 3. Pour water. If you forget to tell it to stop pouring, you’ll have a flooded kitchen! That’s why termination (stopping) is key.
Quick Review: An algorithm must have a clear start, clear steps, and a definite end.
2. Following the Map: Flowcharts and Pseudocode
Algorithms are usually presented in two main ways: Flowcharts (visual maps) and Pseudocode (English-like instructions).
Flowchart Symbols to Remember:
- Ovals: Start or Stop.
- Rectangles: A process or instruction (e.g., "Add 1 to \(x\)").
- Diamonds: A decision or "if" statement (e.g., "Is \(x > 10\)?"). These always have two paths coming out: "Yes" or "No".
Understanding the Logic:
Algorithms often use iterative processes (loops). This just means repeating a set of steps until a condition is met.
Example: "While the water is not boiling, keep heating the kettle."
Memory Aid: In pseudocode, the phrase "Let \(i = i + 1\)" is very common. Don't think of it as an algebraic equation (where \(i\) would cancel out!). Think of it as an instruction: "Replace the old value of \(i\) with the new value (old value + 1)."
Summary: Flowcharts are for visual learners; pseudocode is for those who prefer lists. Both do exactly the same job!
3. Algorithmic Complexity: How Hard is the Computer Working?
Not all algorithms are created equal. Some are fast, and some are very slow when the problem gets bigger. We measure this using Complexity.
The "Big O" Notation
We use Order Notation (e.g., \(O(n)\) or \(O(n^2)\)) to describe how the time taken by an algorithm grows as the size of the problem (\(n\)) grows.
- Linear Complexity \(O(n)\): If you double the number of items, the time doubles. (e.g., searching a list one by one).
- Quadratic Complexity \(O(n^2)\): If you double the number of items, the time quadruples (\(2^2 = 4\)). This happens when you have a loop inside another loop!
Did you know? We usually focus on the Worst Case scenario. This ensures that no matter how unlucky the input is, we know the maximum time the algorithm will take.
Quick Review Box: If an \(O(n^2)\) algorithm takes 5 seconds for 100 items, how long for 200 items?
Size doubled (\( \times 2 \)), so time increases by \(2^2 = 4\).
New time = \(5 \times 4 = 20\) seconds.
4. Sorting Algorithms: Putting Things in Order
The syllabus specifically highlights the Quick Sort algorithm. It’s a "divide and conquer" method.
How Quick Sort Works:
- Choose a pivot (usually the first or last item in the list).
- Compare every other item to the pivot.
- Move items smaller than the pivot to the left, and items larger to the right.
- The pivot is now in its final correct position.
- Repeat the process for the new "sub-lists" on the left and right.
Common Mistake: When performing Quick Sort by hand, students often forget that once a pivot is chosen and used to split a list, that pivot is "locked" in place. Don't move it again in the next pass!
Takeaway: Sorting algorithms like Quick Sort generally have a worst-case complexity of \(O(n^2)\).
5. Packing Algorithms and Heuristics
Sometimes, finding the perfect answer takes too long. In the real world, "good enough and fast" is often better than "perfect but slow." This is where Heuristics come in.
Bin Packing:
Imagine you are packing boxes into a delivery van. You want to use the fewest bins possible.
- First Fit: Take each item in the order given and put it in the first bin it fits into.
- First Fit Decreasing (FFD): Sort the items into descending order first, then use First Fit. This usually works better because you pack the big, awkward items first!
- Full Bin: A strategy where you look for combinations of items that fill a bin exactly.
Important Point: These are Heuristic algorithms. They are efficient and fast (\(O(n^2)\) complexity), but they are not guaranteed to give the absolute minimum number of bins. They just give a very good guess.
Summary: Use First Fit for speed; use First Fit Decreasing for a better result (but you have to sort the list first!).
6. Proving Algorithms
How do we know an algorithm actually works?
- Proof by Exhaustion: Testing every single possible case (only works for very small problems!).
- Disproof by Counter-example: If you find just one case where the algorithm fails, you have proven it is incorrect.
Encouragement: Don't worry if these proofs seem abstract! Most exam questions will ask you to show why a specific step works or provide a simple example where a heuristic doesn't give the best answer.
Key Takeaway for the Chapter:
Algorithms are logical tools for efficiency. By understanding their structure (flowcharts/pseudocode), efficiency (complexity), and limitations (heuristics), you can model and solve complex real-world problems systematically.