Data Structures & Algorithms

Foundations: Complexity & Arrays5 lessons

Before any structure, a way to measure one: Big-O tells you how an algorithm's cost grows as the data grows. Then the workhorses — arrays, the two-pointer and sliding-window techniques, and hash tables — each one building a real piece of Tunebox's library.

Linked Lists, Stacks & Queues4 lessons

Three linear structures, each shaped by one rule. A linked list trades random access for cheap splicing; a stack only touches its top; a queue serves in arrival order. Together they drive Tunebox's player — the linked playlist, the back button and the up-next queue.

Recursion, Searching & Sorting6 lessons

Recursion first, because the best searching and sorting algorithms are built on it. Then binary search, which is only possible once data is sorted, and the sorts themselves — from the simple quadratic ones to merge sort and quick sort — each ordering Tunebox's library in a different way.

Trees, Heaps & Tries5 lessons

Data that branches. Binary trees and their traversals, binary search trees that keep things ordered, heaps that always know the biggest item, and tries that complete a word as it's typed — together powering Tunebox's discovery features.

Graphs6 lessons

The most general structure of all: nodes and edges. How to represent a graph, walk it breadth-first and depth-first, find the cheapest route through a weighted one, and merge connected groups with union-find — building Tunebox's social layer and recommendations.

Greedy, Backtracking & Dynamic Programming5 lessons

Three ways to attack a hard problem. Greedy takes the best-looking step and proves it's safe; backtracking explores choices and abandons dead ends; dynamic programming solves each subproblem once and reuses it. Each plans part of a Tunebox night — ending in a full festival lineup.

Analysis II: Recurrences, Amortisation & Randomness5 lessons

Sections 1 to 6 claimed a lot of costs: merge sort is O(n log n), append is O(1) on average, breadth-first search is O(V + E), quick sort is usually fast. This section proves them, on the code you wrote. You'll turn a recursive function into a recurrence and solve it with a recursion tree, account for the rare expensive append with a bank of saved tokens, use divide and conquer on problems that are not sorting, let a random pivot beat any input an adversary can pick — and finish with a cost lab that measures any Tunebox function, fits a curve to the counts and checks it against the bound you derived on paper.

Bits & Machine Numbers9 lessons

This section starts Quarry, the search-and-storage engine you build for the rest of the advanced course. Every record Quarry stores starts as a 32-bit header word, and building the encoder for it means working below the integer. You'll use AND, OR, XOR and shifts, pack fields behind masks, and learn the bit tricks that find the lowest set bit in one step. You'll walk every subset of a set by counting, and see why a float can't hold 0.1. The same bits give you fast modular powers and inverses from extended Euclid, and a Bloom filter that can answer "definitely not stored" without touching disk. The capstone puts it all together as Quarry's record codec.

Number Theory for Algorithms4 lessons

Quarry's hash kernel needs three things from number theory: a fast way to find primes for bucket counts and moduli, arithmetic that stays correct and in-range under a modulus instead of overflowing, and a way to count arrangements and collisions without listing them. This section builds all three — the Sieve of Eratosthenes and the linear sieve, modular addition and multiplication done the way every language actually implements them, and nCr via Pascal's triangle and the factorial-and-modular-inverse route — then closes with the hash kernel itself: a real polynomial hash, checked against the birthday bound.

Prefix Sums & Range Queries6 lessons

Quarry is the search-and-storage engine you build from here on, and its first subsystem is the analytics engine: a log of per-minute counts and a dashboard that asks, thousands of times a second, what happened between minute l and minute r. Rescanning the log for every question is O(n) each time. This section trades a little preparation for fast answers — a prefix row and its mirror, the difference array; square-root blocks; Fenwick trees; segment trees with lazy range updates; and the B-tree, which is what a range index looks like when the rows live on disk.

Monotonic Structures & Search on the Answer5 lessons

Quarry, the search-and-storage engine, needs a query planner: something that reads a latency trace and says where the spikes reach, what the worst request was in every window of the live dashboard, and how small a shard or server can be while still meeting its promise. This section builds it with two ideas. A stack or deque kept in sorted order answers every 'next bigger' or 'window maximum' question in one pass, because each item enters once and leaves once. And when the answer itself is a number you can test with a yes/no question that flips only once, you can binary search the answer instead of the data. Meet in the middle closes the section: halve an exponential search, then join the halves with the sorting and searching you already have.

String Algorithms6 lessons

Searching text is the most common thing software does to it, and the obvious way does too much work on exactly the repetitive text that logs and records are made of. Three linear-time ideas fix that: fingerprints that roll along the text in O(1), a failure function that lets a matcher never step backwards, and the Z-array's box of already-known matches. Together they build Quarry's text index.

Sorting at Scale6 lessons

Quarry's ingest sorter takes over where section 3's sorts stop. Heap sort proves you can sort in place with no extra memory. Counting, bucket and radix sort skip comparisons entirely, trading a range limit for O(n + k). Quickselect finds the kth item without sorting anything. A short proof shows why n log n is a hard floor for any sort that does compare — and why counting sort isn't a loophole. The section closes with external sorting: what happens once the data is bigger than memory, and the compactor that generates and merges runs until one sorted file remains.

Balanced Trees6 lessons

Quarry's index layer needs a search tree that stays fast no matter what order keys arrive in. A plain BST can degenerate into a linked list; this section builds the machinery that stops it. Rotations are the one move every self-balancing tree relies on. AVL trees use them after every insert to guarantee O(log n) height, red-black trees use cheaper recolouring to get a looser but still logarithmic bound, B-trees widen each node so a disk index stays a few reads deep, and treaps and skip lists reach for randomness instead of bookkeeping. The section closes with spatial trees, which split a plane instead of a line, and a capstone index layer that puts rotations and balance factors to work on a real insert/query mix.

Sequence DP: the Diff Engine5 lessons

Dynamic programming over sequences: the longest rising run in a list, the longest subsequence two versions share, the fewest edits between two strings, and how to walk a finished table backwards to recover the answer itself, even in linear space. Each one is a piece of Quarry's version history, and together they become a real diff engine that shows what changed between two revisions of a stored document.

Probabilistic & System-Scale Structures6 lessons

Quarry stops promising exact answers and starts promising fast, bounded ones. A k-cell reservoir samples a stream whose length isn't known yet, fairly, without storing it. A count-min grid counts occurrences of millions of possible keys in a fixed amount of memory, always erring upward. An LRU/LFU cache swaps exactness for a hit-rate bet, and sometimes loses to a policy that doesn't even look. A hash ring lets the cluster grow by one node without reshuffling almost everything. An LSM tree accepts paying for the same write twice — once to flush it, again to compact it — in exchange for a storage engine that never blocks on disk the way a sorted file would. The capstone wires all of it into one storage engine and measures what it actually costs.

Graph Structure & Decomposition7 lessons

Meridian is a city logistics network — depots, roads, one-way streets, vans and drivers — and this section builds its model of the city. You'll schedule the build-out so nothing starts before what it depends on, catch forwarding loops before parcels circle forever, lay the cheapest relay backbone that reaches every depot, find the districts a van can drive around freely on one-way streets, name the roads whose closure splits the city, and pair drivers with the jobs they are licensed for. It starts from the graphs section alone, so you can begin here straight after the core course.

Shortest Paths at Scale6 lessons

Meridian has a model of the city; now it has to route through it. Dijkstra alone can't: the night timetable has credits, daytime tariffs have rebates on two-way roads, dispatch wants every depot-to-depot price at once, and the live map wants an answer before the screen loads. This section builds Meridian's router one algorithm at a time: a single sweep for acyclic timetables, Bellman-Ford with an honest refusal when a loop of rebates pays forever, Floyd–Warshall's all-pairs table, A* aimed at the goal, and search from both ends at once, then ties them together in a router that picks the right one for the network in hand.

Flow & Matching5 lessons

Section 17's driver-job matching was a flow problem in disguise: every driver, every job and every licence was a pipe of capacity one. Meridian's real depot network carries real volume on pipes of real capacity, and the dispatcher needs more than a yes-or-no match. This section builds the general machinery: Edmonds-Karp pushes volume along augmenting paths and undoes a bad commitment through a backward edge, the final residual graph turns max-flow min-cut from a theorem into a picture you can count, Dinic's level graph saturates several paths per phase instead of one, and min-cost flow (leaning on section 18's Bellman-Ford) prices the cheapest way to move it — with the Hungarian assignment problem falling out as the special case where every pipe has capacity one. The capstone dispatches a fixed shift roster and reports the cut that is actually limiting it.

Planning DP6 lessons

Meridian's vans, zones, depots and drivers need a plan for the day, and every part of that plan is a dynamic program with a different shape. You'll load a van under two limits at once, cross a grid of service zones, staff a tree of depots, sequence a small tour exactly with a table indexed by sets, and make a slow transition fast with a sliding window. The capstone assembles the day planner and ends on a question that separates easy problems from hard ones: some answers are slow to find and instant to check.

Computational Geometry6 lessons

Meridian wants to know, for a depot and its delivery stops: which way does a route bend, do two routes cross, what shape is the depot's own service area, and which two stops sit closest together. Every answer here comes from one test repeated in different shapes — the sign of a cross product. You'll classify a turn, catch the collinear case a naive crossing test gets wrong, wrap a service area in a convex hull with a stack that only ever pops a bad turn, sweep a line across many routes while a sorted active set keeps the comparisons down, and split the city in half to find the closest pair of stops in O(n log n) instead of O(n²).

Hard Problems & Adversarial Search6 lessons

Every algorithm so far in this course runs in polynomial time. This section is about the problems that, as far as anyone has proved, do not: finding the cheapest tour through every bidder's stops is brute-force-or-nothing, and the brute force explodes long before checking a finished answer does. Reductions show that many of these hard problems are secretly the same problem wearing different clothes. Since exact answers do not scale, Meridian's bid desk ships a provably-bounded approximation instead of giving up. The last two lessons turn to a different kind of hardness: an opponent who is also optimising. Minimax with alpha-beta pruning searches a game tree efficiently, and impartial games like Nim turn out to have a complete theory of their own, built on XOR and Grundy numbers.

Course curriculum