Welcome to Decision Mathematics!
Welcome to the world of Decision Mathematics 1 (Paper 3D). If you’ve ever wondered how GPS finds the fastest route, how warehouses pack boxes efficiently, or how social networks connect friends, you’re in the right place! This chapter, Algorithms and Graph Theory, is the foundation of it all.
Don’t worry if some of the terms sound a bit "techy" at first. Think of an algorithm as just a very precise recipe, and graph theory as a way of drawing maps to solve puzzles. Let’s dive in!
1. Algorithms: The Mathematical Recipes
An algorithm is a sequence of instructions used to solve a specific problem. In your exam, these might be given as a flow chart or a list of text instructions.
The "Order" of an Algorithm
Not all algorithms are created equal! Some are fast, and some take a long time as the problem gets bigger. The order of an algorithm (often called complexity) tells us how the run-time increases as the size of the problem (\(n\)) increases.
Quick Review: Common Orders
1. Linear: \(O(n)\) — If the list doubles, the time doubles.
2. Quadratic: \(O(n^2)\) — If the list doubles, the time quadruples! (Common in sorting).
3. Cubic: \(O(n^3)\) — If the list doubles, the time increases by 8 times.
Analogy: If you are searching for a name in a phonebook, a linear search means checking every page. A more efficient algorithm would be much faster!
Key Takeaway:
The size of the problem is usually the number of items or vertices. The efficiency is how the number of operations grows relative to that size.
2. Sorting Things Out: Bubble and Quick Sort
To process data, we often need to put it in order. There are two main methods you need to know.
Bubble Sort
In a Bubble Sort, you compare adjacent items. If they are in the wrong order, you swap them. You keep going through the list until a full pass happens with no swaps.
Common Mistake: Students often forget that you must complete a "check pass" at the end to prove the list is sorted, even if it looks finished!
Quick Sort
This is a "divide and conquer" algorithm. It’s usually much faster than Bubble Sort for large lists.
Step-by-Step:
1. Pick a pivot. Crucial Rule: For Edexcel, always choose the middle item of the list. (If the list has \(n\) items, the pivot is at position \([\frac{1}{2}(n+1)]\) if \(n\) is odd, or \([\frac{1}{2}(n+2)]\) if \(n\) is even).
2. Create two sub-lists: items smaller than the pivot and items larger.
3. Repeat the process for each sub-list until every item has been a pivot.
Memory Tip: Bubble sort is Basic and slow. Quick sort is... well, Quick!
3. Bin Packing: Fitting it All In
How do we fit items of different sizes into the fewest number of bins?
First-Fit Algorithm
Take each item in the order given and put it in the first available bin that has room. It’s easy, but not always efficient.
First-Fit Decreasing Algorithm
1. Sort the items into descending order (largest to smallest) first.
2. Apply the First-Fit algorithm.
Why do this? Usually, by placing the "big" items first, the smaller items can "fill the gaps" more effectively later.
Quick Review: To find the lower bound (the absolute minimum number of bins required), add up all item sizes and divide by the bin capacity. Always round up to the next whole number!
4. Graph Theory Basics
A graph is just a collection of vertices (dots, also called nodes) and edges (lines connecting them, also called arcs).
Important Terms to Know:
- Weight: A number associated with an edge (like distance or cost).
- Degree (or Valency): The number of edges connected to a vertex.
- Path: A sequence of edges where you don't visit the same vertex twice.
- Cycle: A path that starts and ends at the same vertex.
- Tree: A connected graph with no cycles.
- Spanning Tree: A tree that includes every vertex of the graph.
Did you know? The "degree" of a vertex is like how many hands that vertex is shaking!
5. Special Types of Graphs
The syllabus requires you to recognize some specific graph families:
Complete Graphs (\(K_n\))
A graph where every vertex is connected to every other vertex. We use the notation \(K_n\) where \(n\) is the number of vertices.
Isomorphic Graphs
Graphs that show the same information but are drawn differently. They have the same number of vertices and the same connections, even if they look like different shapes.
Planar Graphs
A graph that can be drawn so that no edges cross each other.
The Planarity Algorithm: To check if a graph is planar, try to find a Hamiltonian cycle and draw it as a circle. Then, place edges either inside or outside the circle to see if you can avoid crossings.
6. Eulerian and Hamiltonian Graphs
These are named after two famous mathematicians, and they focus on "tours" of a graph.
Eulerian Graphs (Edge Tours)
An Eulerian cycle travels along every edge exactly once and returns to the start.
- Eulerian: All vertices have an even degree.
- Semi-Eulerian: Exactly two vertices have an odd degree (the rest are even). You can start at one odd vertex and finish at the other.
Hamiltonian Cycles (Vertex Tours)
A Hamiltonian cycle visits every vertex exactly once and returns to the start. Unlike Eulerian graphs, there is no simple rule about degrees to find these – you just have to look for them!
Key Takeaway:
Eulerian = Every Edge.
Hamiltonian = Every Head (Vertex).
Summary Checklist
- Can you determine the order of an algorithm? (\(n, n^2, n^3\))
- Can you perform a Quick Sort using the middle item as a pivot?
- Do you know the difference between First-Fit and First-Fit Decreasing?
- Can you identify if a graph is Eulerian by looking at the degrees of the nodes?
- Do you understand that Isomorphic graphs are just "twins" drawn differently?
Don't worry if this seems like a lot of definitions! The more you draw the graphs and practice the sorting passes, the more natural it will feel. You've got this!