We closed module 2 with a promise: to stop describing systems and start building them. This lesson is the first step of that construction. Before we program how an agent finds its own way to a goal (03-02), how it decides against an opponent (03-03) or how it optimises when the solution space is unmanageable (03-04), we need to talk precisely about the tool that underlies all of it: the algorithm. We will look at exactly what an algorithm is and which properties it must satisfy, the four usual ways of expressing one, why AI can be summed up as "algorithms + data + representation", which data structures AI algorithms use over and over again, and how the cost of an algorithm is measured with big-O notation. With those tools in hand we will return to the problem formulation of 02-01 and formalise NovaMarket's routing problem as a graph: we will define the graph of districts that the Getafe van will drive around for the whole module and check, with a brute-force program, why "try every route" stops being an option as soon as Diego adds a handful of extra deliveries. That combinatorial explosion is the reason everything that follows exists.

1. What an algorithm is and which properties it must satisfy
2. Ways of expressing an algorithm: natural language, pseudocode, flowchart, code
3. AI as algorithms + data + representation
4. Basic data structures in AI: lists, queues, stacks, dictionaries and graphs
5. Complexity and big-O notation, at an intuitive level
6. The combinatorial explosion: how many routes the Getafe van can take
7. Families of AI algorithms and where they appear in the course
8. From problem to graph: CITY_GRAPH, the map the whole module will use
9. Python example: representing the graph, walking neighbours and enumerating routes by brute force

An algorithm is a finite, precise sequence of steps that, starting from some input data, produces an output result. The word comes from the Persian mathematician al-Khwarizmi (9th century), but the idea is that of any well-written recipe or set of instructions: someone (or something) that does not understand the problem can follow the steps and obtain the correct result. Marta sums it up in her meetings with Diego like this: "an algorithm is a recipe a computer can follow without asking a single question".

For a sequence of steps to deserve the name of algorithm it must satisfy five classic properties:

Two important observations for what comes next:

• An algorithm is independent of the language it is written in. The breadth-first search of 03-02 is the same algorithm in Python, in Java or explained on a whiteboard.
• Many useful "recipes" in AI do not guarantee the best result, only a good one in a reasonable time. They are still algorithms (finite, precise, effective), but they are called heuristic or approximate. Telling apart when you can demand the optimal solution and when you must settle for a good one is one of the central lessons of this module.

The same algorithm can be written with different degrees of formality. Let us express in four ways a simple rule from use case 6 (assigning orders to warehouses): deciding which warehouse an order ships from.

Natural language (how Diego would explain it): "If the warehouse nearest to the customer has the product, it ships from there. If not, it ships from the other warehouse. If neither has it, the order is put on hold for stock."

Pseudocode (more precise, with no syntax from any particular language):

Flowchart (visual; useful for validating the logic with non-technical people):

Code (executable; the only form the computer understands):

Line by line: stock is a dictionary of dictionaries (warehouse → product → units). The .get(product, 0) method returns 0 if the product does not exist in that warehouse, which avoids an error and treats "not in this warehouse's catalogue" the same as "zero units". The two if conditions follow the pseudocode order exactly. Notice that this algorithm satisfies all five properties: input (product, stock, nearest warehouse), output (a name), definiteness (no ambiguity), finiteness (at most two comparisons) and effectiveness (every step is trivial).

It is common to use all four forms in the same project: natural language to agree the rule with the business, a flowchart to review it, pseudocode to design it and code to run it. In this course we will mostly use short pseudocode, mermaid diagrams and Python code.

In 01-02 we adopted the definition of AI as "systems that act rationally", and in 02-01 we described those systems as agents. From an engineering point of view, every AI agent is built from three ingredients:

• Algorithms: the procedures that decide (find a path, choose a move, fit a model, chain rules).
• Data: the raw material of 02-03, both the data describing the problem (the map, the deliveries, the stock) and the data used for learning (order histories, reviews).
• Representation: the way we translate the world into structures an algorithm can manipulate. A district becomes a node; a street, an edge with a number; an order, a row with columns; a move, a change in a list.

Of the three, representation is the ingredient that gets underestimated most. The same search algorithm works on a city map, on a noughts-and-crosses board or on the possible causes of an incident provided we represent each of those worlds as states and transitions. That is why 02-01 insisted on problem formulation: choosing the representation is half the solution. The rule in section 2 only works because we decided to represent stock as a dictionary of dictionaries; with a different representation (a list of free-text strings) the same algorithm would be impractical.

Data structures are the "shapes" in which we store information so that algorithms can use it efficiently. Five of them will appear again and again in this module, all available in Python's standard library.

Let us see the first three in action, with a minimal example of each:

deque (double-ended queue) is the right way to build a queue in Python: popleft() is immediate, whereas some_list.pop(0) forces every element to shift and becomes slow with many orders. The stack needs nothing special: append and pop on a list already operate at the end. Keep this queue/stack pair in mind: in 03-02 you will see that swapping one for the other turns breadth-first search into depth-first search, without touching anything else.

A graph is the star structure of this module. It consists of nodes (also called vertices) and edges connecting them; if every edge carries a number (distance, time, cost) we speak of a weighted graph; if edges can be traversed in both directions, it is undirected. A city map is a weighted, undirected graph: districts as nodes, stretches of road as edges with their length.

There are two usual representations:

In AI the adjacency list is almost always used, because search algorithms keep asking "where can I go from here?". In Python it is written as a dictionary whose value is a list of (neighbour, weight) tuples. We will build it in section 8.

Two correct algorithms can differ enormously in how long they take. Time complexity describes how running time grows as the input size (n) grows, and big-O notation summarises that growth by keeping the dominant term and ignoring constants: it does not say "it takes 3 seconds", but "if I double n, the time doubles" (O(n)) or "quadruples" (O(n²)). It is the tool Marta uses to answer Diego's favourite question: "and what happens when we have twice as many orders?".

Three ideas to keep:

• Up to O(n log n) everything is "scalable": doubling the data costs little more than double.
• O(n²) is acceptable for thousands of elements, awkward for hundreds of thousands and impossible for millions.
• O(2ⁿ) and O(n!) are the boundary of the impossible: beyond a few dozen elements no computer in the world finishes. That is exactly what happens with delivery routes, as we are about to check.

There is also space complexity (how much memory is needed); in 03-02 we will see that some search algorithms are fast but devour memory, and others the other way round.

Back to the van leaving the Getafe warehouse. If it has to make n deliveries and return, how many different orders can it follow? The first stop is chosen among n, the second among the remaining n−1, and so on: n × (n−1) × … × 1 = n! (n factorial). The following table, computed with math.factorial, shows how many routes there are and how long a computer capable of evaluating one million routes per second would take to try them all:

A NovaMarket van typically makes between 30 and 60 deliveries per shift. For 30 deliveries, 30! is a 33-digit number: not even every computer on the planet running for the whole age of the universe would try every route. And that is a single vehicle in a single city; NovaMarket moves ~3,000 orders a day.

From here come the two strategies that structure the rest of the module:

• Intelligent search (03-02): do not enumerate all the solutions; build them step by step from the initial state, discarding early whatever cannot be good and using heuristics (informed estimates, such as straight-line distance) to steer the exploration towards the goal.
• Approximate optimisation (03-04): when not even that is feasible, start from any solution and keep improving it, accepting a very good route in seconds instead of the perfect route in centuries.

Diego put it his own way: "I don't need the best route in the world; I need a route 15 % better than the one my drivers do from memory, and I need it before 8 in the morning." That sentence is, at bottom, the definition of a useful heuristic.

AI algorithms can be grouped into four large families according to the question they answer. The table also serves as a map of the rest of the course:

The boundaries are not rigid: training a learning model is, on the inside, an optimisation problem (we will see it at the end of 03-04), and many modern systems combine all four families. But the classification helps choose a starting point: when Diego describes a problem, Marta's first question is always "is this finding a path, optimising an assignment, learning from a history or reasoning with rules?".

Let us pick up the formulation from 02-01 and apply it to the simplest problem of the route planner: taking the van from the Getafe warehouse to a specific district by the shortest path. The five components look like this:

With this formulation, the state space is exactly a graph: each district is a node, each road between districts is an edge and its length is the weight. Let us fix the map (fictional, with invented but plausible distances) of southern Madrid that will serve for the whole module: the Getafe warehouse and seven districts where NovaMarket runs its own deliveries.

Eight nodes, twelve edges, distances in kilometres. It is a small graph on purpose: rich enough for several paths to exist between two points (and the one with the fewest legs does not always win), and small enough for you to follow the traces of 03-02 by hand. In 03-02 we will add coordinates to each node to compute straight-line distances, and in 03-04 we will use it as the basis of the travelling salesman problem.

Each key is a node and its value is the list of (neighbour, kilometres) tuples. Because the graph is undirected, every road appears twice (in the list of each endpoint): ("Leganes", 4.5) is under Warehouse_Getafe and ("Warehouse_Getafe", 4.5) is under Leganes. It is a small duplication cost in exchange for answering "where can I go from here?" with a single dictionary lookup.

Output:

neighbours is O(1): one dictionary lookup. direct_distance scans the neighbour list of a (at most four elements here), which is the drawback of the adjacency list mentioned in section 4; on a real map, with few neighbours per junction, it is still negligible. Notice that Usera and Retiro are not directly connected (None): to get from one to the other you must go through Arganzuela or through Vallecas, and deciding which is better is precisely what the search of 03-02 will do.

Now the full delivery problem: the van leaves the warehouse, visits a list of districts (one per delivery) and returns. The most naive strategy is brute force: generate every possible order, compute the cost of each and keep the lowest. itertools.permutations generates exactly those n! orders.

To keep things simple (and because we do not yet know how to compute the shortest path between two non-adjacent districts), in this first version we require that every leg of the route be a direct road of the graph; if two consecutive stops are not connected, the route is declared impossible with infinite cost. In 03-04 we will lift that restriction using the shortest paths from 03-02.

Output:

How the code works:

• zip(route, route[1:]) pairs each stop with the next one; it is the idiomatic Python way to iterate over "legs".
• itertools.permutations(deliveries) produces every possible order as a tuple, without loading them all into memory at once (it is a generator), but it does go through all of them: 24, 120 and 5,040 iterations.
• The route is built by concatenating tuples: (origin,) + order + (origin,).
• We keep the best cost seen so far and replace it only when a lower one appears: the classic "keep the minimum" pattern.

What the output teaches is more important than the specific route:

1. The number of routes evaluated is exactly n!, regardless of what the algorithm knows about the problem. With 7 deliveries that is already 5,040 evaluations; with 12 it would be 479 million.
2. Almost every route evaluated is impossible (2 feasible out of 120): brute force knows nothing about the graph, so it spends 98 % of its effort on combinations a driver would discard instantly. The search algorithms of 03-02 avoid this by building routes step by step only along valid edges.
3. The two feasible routes in each case are the same one in both directions: brute force does not even recognise that symmetry, one more example of problem knowledge that an intelligent algorithm can exploit.

Try adding an import time and measuring how long the 7-delivery case takes (a few milliseconds on a current laptop), then work out, with the table in section 6, how long it would take with 15. That calculation is the best possible motivation for the next lesson.

• Confusing "algorithm" with "code": code is one of the ways of expressing an algorithm. Design first in pseudocode or a diagram, and program afterwards; you will save yourself many logic errors.
• Using some_list.pop(0) as a queue: it works, but it is O(n) on every extraction. Use collections.deque and popleft(); with thousands of nodes in a search frontier the difference is enormous.
• Forgetting symmetry when building an undirected graph by hand: if you add ("Leganes", 4.5) to Warehouse_Getafe but not the reciprocal, the van will be able to reach Leganes but never come back. An automatic check (go through every edge and verify the reverse exists with the same weight) saves hours of debugging.
• Trusting intuition about complexity: "it's only 12 deliveries" sounds small, and it is 479 million routes. Always work out the size of the solution space before choosing a strategy.
• Misreading big-O notation: O(n²) does not mean "slow", it means "grows quadratically". For 100 elements it may be instantaneous; the problem shows up when scaling. Conversely, an O(n log n) with huge constants can be slower than a simple O(n²) for small inputs.
• Choosing the representation without thinking about the operations: before deciding between adjacency list and matrix (or between list and dictionary), ask yourself which operation the algorithm will perform millions of times, and optimise that one.

Diego proposes this rule for choosing the next stop: "always go to the delivery that is most urgent, and if there is a tie, to whichever the driver thinks best". State which of the five properties of section 1 it fails, and rewrite it (in pseudocode) so that it satisfies them all.

Write a function is_symmetric(graph) that returns True if for every edge (a, b, d) the edge (b, a, d) exists. Check CITY_GRAPH; then suppose a new 8.0 km expressway opens directly between Warehouse_Getafe and Usera, add it (in both directions) and run brute force again with the 4 deliveries ["Leganes", "Carabanchel", "Usera", "Villaverde"]. How many feasible routes are there now, which are they and which is the best? Modify brute_force (or write a separate loop) to print every feasible route.

Using math.factorial, write a program that, for n from 5 to 20 deliveries, prints the number of routes and the estimated time assuming 10 million evaluations per second (a computer ten times faster than the one in section 6). From which n does the time exceed an 8-hour working day? Does the answer change much with a computer ten times faster?

Solution 1. It fails definiteness: "whichever the driver thinks best" is ambiguous, two drivers would do different things and a program cannot execute it. A precise version:

The final tie-break by id guarantees that no decision is ever left undefined. Note that it is now an algorithm, even if not necessarily the best one (it is a "greedy" heuristic: it picks what looks best now without looking further ahead; we will come back to that idea in 03-02).

Solution 2.

Output of the final loop:

The new road creates two more feasible routes (those leaving or returning via Usera), but the best is still the 23.0 km one: a new road widens the options, it does not necessarily improve the optimum. Remember to undo the change (or redefine CITY_GRAPH as in section 9.1) before moving on to the following lessons, which use the original 12-edge graph.

Solution 3.

At 10 million routes per second, 13 deliveries take about 10 minutes, 14 deliveries about 2.4 hours and 15 deliveries already exceed the working day (1.5 days). A computer ten times faster only shifts the boundary by one delivery (from 14 to 15), because each additional delivery multiplies the work by n: the solution is not more hardware, but a better algorithm.

In this lesson we have laid the technical foundations of the module. We have defined the algorithm as a finite, precise and effective sequence of steps with input and output, and we have seen that it can be expressed in natural language, pseudocode, flowchart or code, each form with its own use. We have summed up AI engineering as algorithms + data + representation and reviewed the data structures that will appear constantly (lists, queues, stacks, dictionaries and, above all, graphs represented with adjacency lists). With big-O notation we have learnt to reason about how an algorithm scales, and we have checked with numbers that NovaMarket's delivery problem suffers a combinatorial explosion (n! routes) that makes brute force unworkable beyond a dozen deliveries. Finally, we have picked up the problem formulation of 02-01 to turn the city map into the graph CITY_GRAPH, and we have written the code that represents it, walks it and enumerates routes by brute force.

In the next lesson, Search Algorithms, we will solve the first real problem on that same graph: finding the best path from Warehouse_Getafe to a destination district without enumerating every possibility. We will see that swapping the queue for a stack turns breadth-first search into depth-first search, that a priority queue gives us the shortest path (uniform-cost search), and that a heuristic as simple as straight-line distance lets A* reach the goal while exploring a fraction of the map.