Algorithms and graph theory

Welcome to Decision Mathematics!

Welcome to the world of Decision Mathematics 1. This branch of math isn't about complex calculus or abstract geometry; it’s about the science of efficiency. Think of it as "Mathematics for the Real World." Whether it’s GPS finding the fastest route, a warehouse packing boxes, or a computer sorting your playlist, they all use algorithms. In this chapter, we will learn how to follow these sets of instructions step-by-step and understand the "map-like" structures called graphs.

Don't worry if some of the terms sound a bit technical at first—we’ll break everything down into simple, bite-sized pieces!

1. Algorithms: The "Recipes" of Math

An algorithm is simply a sequence of precise instructions used to solve a specific problem. You use them every day! A recipe for baking a cake or the instructions for building a Lego set are both algorithms.

Efficiency and Order

In Further Maths, we don't just care if an algorithm works; we care how fast it is. This is called efficiency. We measure efficiency by looking at the order of an algorithm.

Size of the problem (\(n\)): Usually the number of items in a list or the number of vertices on a graph.
Order: A measure of how the "run-time" (the number of operations) increases as the size of the problem increases. If you double the number of items and the time quadruples, the algorithm is likely quadratic order \(O(n^2)\).

Quick Review: Common Orders
• Linear \(O(n)\): Time grows at the same rate as the list.
• Quadratic \(O(n^2)\): Time is proportional to the square of the size (common for sorting).
• Cubic \(O(n^3)\): Time is proportional to the cube of the size.

Key Takeaway: The lower the order, the more "efficient" the algorithm is for large problems!

2. Sorting and Packing

Imagine you have a messy pile of books and you need to put them in alphabetical order. How do you do it systematically? That’s where sorting algorithms come in.

Bubble Sort

The Bubble Sort is the simplest way to sort. You compare adjacent items and swap them if they are in the wrong order. The largest items "bubble up" to the end of the list.

Step-by-step:
1. Start at the beginning of the list.
2. Compare the first two items. Swap if the first is bigger than the second.
3. Move to the next pair and repeat until you reach the end (this is one pass).
4. Repeat the passes until a pass happens with no swaps.

Quick Sort

Quick Sort is much faster for big lists. It uses a pivot to split the list into two smaller lists (one with smaller items, one with larger items).

Edexcel Rule for Pivots: To find the middle item (pivot) in a list of \(N\) items:
• If \(N\) is odd, use position \( \frac{1}{2}(N+1) \).
• If \(N\) is even, use position \( \frac{1}{2}(N+2) \).

Example: In a list of 6 items, the pivot is item number 4. In a list of 9 items, the pivot is item number 5.

Bin Packing

How do we fit items into the fewest number of "bins" (containers)?
• First-Fit: Put each item into the first bin that has room.
• First-Fit Decreasing: Sort items into descending order first, then use First-Fit. This is usually more efficient!
• Full-Bin: Look for combinations of items that fill a bin exactly.

Common Mistake: In First-Fit, always check Bin 1, then Bin 2, then Bin 3 for every single item. Don't just stay at the current bin!

3. Graph Theory: The Basics

A graph is a collection of points called vertices (or nodes) connected by lines called edges (or arcs).

Key Terms to Learn:

• Weight: A number associated with an edge (like distance, cost, or time). A graph with weights is called a network.
• Degree (or Valency): The number of edges meeting at a vertex. If a vertex has 3 edges, its degree is 3 (odd).
• Path: A sequence of edges where you never visit the same vertex twice.
• Cycle: A path that starts and ends at the same vertex.
• Connected: A graph where you can get from any vertex to any other vertex.
• Tree: A connected graph with no cycles.
• Spanning Tree: A tree that includes every vertex of the original graph.

Did you know? The Handshaking Lemma states that the sum of the degrees of all vertices is equal to twice the number of edges. This means the sum of degrees is always even!

4. Types of Graphs

Sometimes graphs have special properties that make them easier to work with:

• Complete Graph (\(K_n\)): Every vertex is connected to every other vertex by exactly one edge. A complete graph with 5 vertices is called \(K_5\).
• Isomorphic Graphs: Two graphs that look different but have the same number of vertices and the same connections. They are essentially the same graph "in disguise."
• Planar Graph: A graph that can be drawn so that no edges cross each other (except at vertices).
• Subgraph: A smaller part of a larger graph.

Key Takeaway: Identifying the type of graph helps you choose the right algorithm to solve it!

5. Traversability: Can we draw it?

Can you draw a graph without lifting your pen or going over the same line twice? This is the study of Eulerian graphs.

Eulerian Graph: Every vertex has an even degree. You can start anywhere and finish at the same spot after covering every edge once.
Semi-Eulerian Graph: Exactly two vertices have an odd degree. You can cover every edge, but you must start at one odd vertex and you will finish at the other odd vertex.
Neither: If there are more than two odd vertices, the graph is not traversable in one go.

Memory Aid:
Even degrees = Eulerian (Starts/Ends at the same place).
Some odd (two) = Semi-Eulerian (Starts/Ends at different places).

Quick Review:
1. Count the degrees of every vertex.
2. If all are even -> Eulerian.
3. If two are odd -> Semi-Eulerian.
4. More than two odd -> Not traversable.

Summary: Tips for Success

• Read carefully: In Quick Sort, did the question ask for the list in ascending or descending order?
• Be systematic: Don't skip steps in algorithms. Examiners love to see every "pass" or "iteration."
• Check your math: In Bin Packing, the sum of the items divided by the bin capacity gives you the lower bound (the absolute minimum number of bins needed). It’s a great way to check if your answer is sensible!
• Don't panic: This chapter is about following rules. If you follow the steps of the algorithm exactly, you will get the right answer every time!