Graphs & optimisation
Shortest paths, trees, flows, linear and dynamic programming, heuristics and metaheuristics.
The A* algorithm: pathfinding with an admissible heuristic
A* combines Dijkstra with an estimate of the remaining distance: admissible and consistent heuristics, Manhattan distance, grids and speed trade-offs.
Bellman-Ford: shortest paths with negative weights and cycles
Bellman-Ford explained: why n−1 passes, how to detect negative cycles and where negative weights really appear, from exchange rates to network routing.
Matching in bipartite graphs and the assignment problem
How to pair people and tasks in the best way: maximum matching with augmenting paths, König's theorem, weighted assignment and the Hungarian method.
Breadth-first search (BFS): levels, queues and shortest paths
How breadth-first search works: the queue, distance levels, shortest paths in unweighted graphs and practical uses, from mazes to computer networks.
Depth-first search (DFS): stack, recursion and components
Depth-first search explained step by step: recursion or an explicit stack, discovery and finish times, connected components and cycle detection in graphs.
Dijkstra's algorithm: shortest paths with non-negative weights
How Dijkstra's algorithm works: relaxation, a heap-based priority queue, why it needs non-negative weights and how to apply it to real maps and networks.
Dynamic programming: subproblems, memoization and tables
The principles of dynamic programming: optimal substructure, overlapping subproblems, memoization versus tabulation and a five-step method for applying it.
Edit distance: Levenshtein and comparing texts
How to measure how different two strings are: Levenshtein distance with dynamic programming, alignment, longest common subsequence and how diff works.
Eulerian paths and the Chinese postman problem
From Königsberg to refuse collection rounds: when a route using every edge once exists, Hierholzer's algorithm and the Chinese postman problem explained.
Floyd-Warshall: shortest distances between all pairs
Floyd-Warshall computes the shortest distance between every pair of vertices with three nested loops: idea, code, path reconstruction and alternatives.
Graph colouring: timetables, frequencies and registers without clashes
Graph colouring applied to exam timetables, radio frequencies and register allocation: chromatic number, the greedy algorithm, DSatur and practical limits.
Representing a graph: adjacency matrix and adjacency lists
Adjacency matrix, adjacency lists and edge lists compared: memory use, cost of each operation and which one to choose depending on the real-world graph.
What is a graph: vertices, edges and the main types
Vertices, edges, degree, directed, weighted and bipartite graphs: the basic vocabulary of graph theory explained with examples from real networks and maps.
Greedy algorithms: when the greedy choice is truly optimal
Greedy algorithms with examples: interval scheduling, Huffman codes, deadlines, counterexamples and how to prove that a greedy choice is really optimal.
Integer linear programming and branch and bound
When variables must be integers: why rounding fails, binary variables, the linear relaxation, branch and bound, cutting planes and the optimality gap.
The knapsack problem: dynamic programming and variants
The 0/1 knapsack problem solved with dynamic programming: the table, rebuilding the chosen items, reduced memory, the fractional version and variants.
Linear programming: how to model a real-world problem
Decision variables, objective function and constraints: how to translate a production or diet problem into a linear programming model a solver can use.
Duality in linear programming and shadow prices
Every linear program has a dual twin: how to build it, what weak and strong duality say, complementary slackness and how to read and use shadow prices.
Maximum flow and minimum cut: Ford-Fulkerson and Edmonds-Karp
Flow networks, capacities and augmenting paths: how Ford-Fulkerson and Edmonds-Karp work and why the maximum flow always equals the minimum cut.
Metaheuristics: simulated annealing, tabu search and genetics
How to escape local optima: local search, simulated annealing, tabu search and genetic algorithms, with examples, parameters to choose and common mistakes.
Minimum spanning tree: Kruskal's and Prim's algorithms
How to connect every node of a network at minimum cost: the cut property, Kruskal's algorithm with union-find, Prim's algorithm with a heap, and uses.
The simplex method explained without heavy formulas
How the simplex method solves a linear program by jumping from vertex to vertex: standard form, slack variables, the tableau, pivoting and special cases.
Strongly connected components: Kosaraju and Tarjan compared
What the strongly connected components of a directed graph are, how to find them with Kosaraju and Tarjan, and why the condensed graph helps so much.
Topological sort: putting the dependencies of a DAG in order
Topological sorting in directed acyclic graphs: Kahn's algorithm, the DFS version, cycle detection and uses in builds, course plans and project scheduling.
Travelling salesman: constructive heuristics and 2-opt
The travelling salesman problem in practice: nearest neighbour, insertion, the spanning-tree approximation, 2-opt improvement and lower bounds.