IB AI: Algorithms and Decision Mathematics

Decision mathematics provides the systematic backbone for optimizing complex real-world systems, from organizing data and scheduling surgeries to designing efficient delivery routes. In the IB AI course, you move beyond abstract theory to learn how algorithms—precise, step-by-step procedures—are designed and applied to solve concrete problems in logistics, planning, and resource management. Mastering this topic equips you with a powerful toolkit for making optimal decisions under constraints.

What is an Algorithm? From Concept to Flowchart

At its core, an algorithm is a finite sequence of unambiguous instructions designed to perform a specific task or solve a class of problems. Think of it as a recipe: if followed exactly, it reliably produces the intended outcome. In decision mathematics, we are particularly concerned with algorithms that optimize outcomes, such as minimizing time or cost.

To design or communicate an algorithm, we often use a flowchart. This is a visual diagram that uses standardized symbols (like ovals for start/end, rectangles for processes, and diamonds for decisions) to represent the flow of logic and steps. For instance, a simple algorithm to find the largest of three numbers, A, B, and C, can be clearly mapped in a flowchart: Start → Input A, B, C → Set Max = A → Is B > Max? (Yes/No) → Update Max if yes → Is C > Max? (Yes/No) → Update Max if yes → Output Max → End. This visual representation is crucial for planning, debugging, and explaining systematic procedures before they are translated into code.

Sorting Algorithms: Organizing Data Systematically

A fundamental class of algorithms deals with sorting data into a specific order, such as numerical or alphabetical. Two elementary yet important sorting algorithms are the bubble sort and the shuttle sort. Both are comparison-based, meaning they work by repeatedly comparing adjacent items and swapping them if they are in the wrong order.

Bubble sort works by making multiple passes through a list. On each pass, it compares adjacent elements from left to right, swapping them if the left element is greater than the right (for ascending order). This causes the largest unsorted element to "bubble up" to its correct position at the end of the list with each full pass. While simple to understand, it is inefficient for large lists, as it may require up to $n(n-1)/2$ comparisons for a list of $n$ items.

Shuttle sort (an insertion sort variant) is slightly more efficient. It builds a sorted section at the front of the list. Starting with the second element, you "shuttle" it backwards through the already-sorted section, comparing and swapping until it is in its correct position. You then move to the third element and repeat. The process resembles sorting a hand of playing cards. The maximum number of comparisons is also on the order of $n^2$, but it typically performs better than bubble sort on average because it stops shuttling once the correct position is found.

Priority Lists and Scheduling

Many scheduling problems are tackled using priority lists. A priority list is an ordered list of tasks (often labeled by letters or numbers) that dictates the order in which they will be assigned to available processors (people, machines, rooms). The goal is often to minimize the overall completion time, known as the makespan.

The process uses a scheduling algorithm, commonly the list processing algorithm. You work through the priority list from left to right. For each task, you assign it to the first processor that becomes free, respecting any precedence constraints (rules stating certain tasks must be completed before others can begin). For example, when scheduling construction jobs, the foundation must be poured before the walls are erected. By drawing a Gantt chart (a timeline bar chart) from the results, you can visualize the schedule, identify idle time, and experiment with different priority lists to find a more efficient sequence.

Critical Path Analysis: Managing Complex Projects

Critical Path Analysis (CPA) is a powerful algorithm for planning and managing complex projects with multiple interdependent activities. It helps identify the minimum project duration and the activities that cannot be delayed without delaying the whole project—these lie on the critical path.

You start by creating an activity network. Activities are represented by arcs (arrows), and their dependencies are shown using nodes (circles). Two key calculations are performed on this network:

1. Earliest Start Time (EST): The earliest time an activity can begin, based on the completion of all its predecessors.
2. Latest Finish Time (LFT): The latest time an activity can finish without delaying the project.

The float or total float of an activity is the amount of time it can be delayed without affecting the project deadline. It is calculated as: $Float=LFT-Duration-EST$. Activities on the critical path have zero float. Managing a project effectively involves monitoring these critical activities closely and potentially using float from non-critical activities to reallocate resources.

Network Algorithms: Solving Routing and Allocation

Network algorithms operate on structures composed of vertices (nodes, often representing locations) connected by edges (arcs, representing roads, connections, or pipelines) with associated weights (like distance, time, or cost).

Two essential algorithms are:

• Kruskal's Algorithm: Finds the minimum spanning tree—the set of edges that connects all vertices in a network with the minimum total weight, without creating any cycles. This is vital for designing cost-efficient networks like cable or road systems. The algorithm works by sorting all edges by weight and then adding the shortest edge to the tree, provided it does not create a cycle, until all vertices are connected.
• Dijkstra's Algorithm: Finds the shortest path from a specified start vertex to all other vertices in a network. Unlike Kruskal's, it finds optimal routes, not just connections. It works by iteratively labeling vertices with the shortest known distance from the start, updating these labels as shorter paths are found. This is the fundamental logic behind GPS navigation systems.

Applying these systematic procedures allows you to solve classic resource allocation problems, such as assigning workers to jobs for maximum efficiency, or routing problems, like determining the most cost-effective delivery route that visits a set of locations.

Common Pitfalls

1. Ignoring Precedence Constraints in Scheduling: A common error is assigning tasks based solely on a priority list without checking if all prerequisite tasks are complete. Always verify that all predecessors of a task are finished before assigning it to a processor.
2. Misidentifying the Critical Path: The critical path is not simply the sequence of activities with the longest individual durations. It is the longest path through the network from start to finish. You must correctly calculate all ESTs and LFTs to identify activities with zero float. An activity with a long duration may have a large float and not be critical.
3. Confusing Minimum Connectors with Shortest Path: Kruskal's algorithm (minimum spanning tree) finds the cheapest way to connect all points, which may not provide the shortest route between any two specific points. Dijkstra's algorithm (shortest path) finds the optimal route between a start point and all others. Using the wrong algorithm for the problem will lead to a suboptimal solution.
4. Incorrect Bubble Sort Implementation: When performing a bubble sort by hand, it's easy to forget that after each pass, the last $i$ elements are already in place. A classic mistake is to compare all adjacent pairs in the list on every single pass, which is unnecessary. Following the defined algorithm step-by-step prevents this.

Summary

• Algorithms are precise, step-by-step procedures for problem-solving, often visualized using flowcharts for clarity in design and communication.
• Sorting algorithms like bubble sort and shuttle sort provide systematic, though sometimes inefficient, methods for ordering data through comparison and swapping of adjacent elements.
• Priority lists combined with list processing algorithms are used to schedule tasks on processors, minimizing time while respecting precedence constraints, with results visualized on Gantt charts.
• Critical Path Analysis (CPA) uses activity networks to calculate Earliest Start Times and Latest Finish Times, identifying the critical path (zero-float activities) that determines the minimum project duration.
• Network algorithms, including Kruskal's algorithm for minimum spanning trees and Dijkstra's algorithm for shortest paths, provide optimal solutions to complex routing and resource allocation problems in interconnected systems.