Computer Science A path through The Default Library ======================================== How computers compute, what can and can't be computed, and how to build software that works. Step 1. Programming Fundamentals: Instructions, State and Taking Things Apart ----------------------------------------------------------------------------- Why: Variables, loops, functions: the grammar every program is written in. A computer can't guess what you meant. Everything in a first programming course is a way of saying it exactly enough, and of working out why you didn't. Tap "sort by price" and a list of a thousand items rearranges before you've lifted your finger. Somewhere, a person wrote down steps so exact that a machine with no judgment, no memory of yesterday and no idea what a "price" is could do it perfectly, a thousand times over. That is the whole trade. A programmer isn't someone who knows a language, they're someone who can state a task so precisely that nothing is left to guess. And since people are bad at being precise on the first try, the other half of the skill is finding out what you actually said, as opposed to what you meant. Mechanical and aerospace engineers use the same habits to simulate a wing before it's built; computer scientists use them to build every other subject on the degree. Python and MATLAB are the common first languages for engineers, and this piece uses Python-style code. The ideas carry to every language. The course in one box Who takes it: first-year students of Computer Science (usually their very first course) and Mechanical & Aerospace Engineering (often in MATLAB or Python). What it's for: telling a machine what to do exactly, and finding out when you didn't. Comes after: nothing; it has no prerequisites. Leads to: Data Structures (34/23), Computer Architecture (34/25) and Software Engineering (34/31) on the computing side; Differential Equations (34/03), Dynamics (34/12) and Control Systems (34/20) on the engineering side, all of which are solved on a computer in practice. Honest line: you won't be able to ship an app after this. You will be able to read ten lines of code, predict what they do, and make a physics model in a loop. A program is instructions plus state Strip away the syntax and a program is two things: a list of instructions, and the state, the current values of all its named boxes. Each instruction reads the state and changes it a little. Running the program is just that, one step after another, and the answer is whatever state is left (or printed) at the end. The graduate habit is to run the program in their head: keep a small table of variable values and update it line by line. Below is a tiny interpreter that does it visibly. Press Step. Then edit the program: change the 6 in the Collatz example, or write your own with =, +=, if/else, while, for … in range(…) and print. Interactive · Step through a program Add 1 to 5 Collatz steps Count down by 3 The program (edit me) StepRun to the endStart again A real mini-interpreter, written for this page. It stops after 400 steps, in case you write a loop that never ends. The first program adds 1 + 2 + 3 + 4 + 5 and prints 15. The Collatz one halves even numbers and triples-plus-one odd ones until it reaches 1: starting from 6 it takes 8 steps. Nobody knows if every starting number reaches 1, and yet the program is five lines long. That's what "simple instructions, deep behaviour" feels like. Variables and types: what a number is made of A variable is a name for a box in memory. A type says what kind of thing is in the box, and therefore what you may do with it: you can add two numbers, join two pieces of text, but adding "3" and 4 is an error or a surprise. Types exist because the machine stores everything as patterns of bits, and the pattern means nothing without the type. The box has a size too. A signed 16-bit integer holds −32,768 to 32,767, and nothing more. Decimals are stored as floating point, binary fractions of limited precision, so 0.1 can't be stored exactly and 0.1 + 0.2 gives 0.30000000000000004. On 4 June 1996 the first Ariane 5 rocket veered off course and broke up about 37 seconds after lift-off, a loss of more than US$370 million. The investigation traced it to the guidance software, reused from Ariane 4: a 64-bit floating-point value (the horizontal bias) was converted to a 16-bit signed integer, and on the faster rocket it didn't fit. The failure shut down both inertial units. A number too big for its box was enough. Interactive · Does it fit? 8 bits 16 bits 32 bits Number to store Ariane's code reportedly raised an error on overflow; some systems wrap silently instead, which is shown here. Conditionals and loops: choosing and repeating With state and instructions, only two more ideas are needed to compute anything: choose (if something is true, do this, else that) and repeat (while something is true, or for each value in a range). Together they let ten lines do work that would take ten million lines written out. The classic trap is in the edges. In Python's range(1, 10) the loop starts at 1 and stops before 10, so it runs 9 times, not 10. Off-by-one errors are the "fencepost" mistake: a fence of 10 sections needs 11 posts. Try the bounds yourself. Interactive · Edit the loop Add up i Add up i² Just count Start Stop (never reached) Step With the defaults, range(1, 11) runs 10 times and adds up to 55. Make the step negative and the start bigger than the stop to count down. Set the start above the stop with a positive step and the body never runs at all, which is perfectly legal and a common source of silent bugs. Functions and recursion: naming a piece, then calling it again A function packages some instructions under a name, takes inputs, and gives back an output. That is decomposition, the central skill of engineering of any kind: break a big problem into pieces small enough to understand and test alone, give each a name, then build on the names. The tracer above could be one function; so could braking distance. Recursion is a function that calls itself on a smaller version of its problem, until it reaches a case it can answer directly. The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, …, each the sum of the previous two) have a one-line recursive definition. Run it naively and the machine re-solves the same sub-problems again and again. Interactive · Count the calls Naive Remember answers (memo) Compute fib(n), n = Time it on this device Naively, fib(5) makes 15 calls, fib(20) makes 21,891, and fib(30), whose answer is just 832,040, makes 2,692,537. Remembering answers brings fib(30) down to 59 calls. Same answer, a different algorithm, and the course after this one (Algorithms, 34/24) is the study of exactly that difference. Data: lists and dictionaries Most programs aren't about single numbers but collections. A list is an ordered row of values, found by position (the third item). A dictionary maps a key to a value (a word to its count, a student ID to a name) and finds an entry by key without scanning. Choosing the right container is the first lesson of Data Structures (34/23). The difference is speed. To find a word in a list of n you may have to look at all n. A dictionary (usually built as a hash table) jumps almost straight to it, in roughly constant time on average, however large it is. Paste some text below and look a word up. Interactive · Count the words Textthe cat sat on the mat and the dog sat on the cat Look up a word Debugging is the scientific method Programs don't do what you meant; they do what you wrote. Finding the gap is science: look at the result, form a hypothesis ("the loop is skipping the last item"), make a prediction ("if I print the count here it will be one short"), run the experiment (print it), and revise. Guessing and changing things at random is the opposite, and it's how you add new bugs. The strongest move is bisection. If the code is a chain of steps and the result is wrong, check the value halfway along. If it's right, the fault is in the second half; if wrong, the first. Each check halves the suspects. In 1947 operators of Harvard's Mark II computer taped a moth found stuck in a relay into the logbook with the note "First actual case of bug being found" — a joke that only works because engineers already called faults "bugs". Interactive · Find the bug in as few probes as you can Start with x = 5. Slide to a step and probe the value there against what you'd get by hand. Look at x Probe hereBlame this stepNew bug Twelve suspect lines need at most four probes when you halve each time, because 2⁴ = 16 is at least 12. Checking from the top, one line at a time, can take twelve. Modelling: a physics simulation in a dozen lines Engineers model long before they build. Most physical laws give a rate of change (acceleration from forces, as in Physics I), and a computer can follow a rate forward in small steps: update the position using the velocity, update the velocity using the acceleration, repeat. That is the Euler method, and the loop is the whole simulation. x, y = 0.0, 0.0 vx, vy = 21.2, 21.2 # 30 m/s at 45 degrees dt = 0.1 # time step in seconds while y >= 0: x = x + vx * dt y = y + vy * dt vy = vy - 9.81 * dt # gravity changes vy only print(x) # about 93.9 metres Smaller time steps are more accurate and cost more. For the cannonball at 30 m/s and 45°, the exact range without air is 91.7 m. With a step of 0.5 s the simulation says 102.1 m, 0.1 s gives 93.9 m, and 0.001 s gives 91.8. Now add air drag, for which no tidy formula exists: the same loop still works, which is why engineers simulate. Interactive · A cannonball in code No air With air drag Launch speed Launch angle Time step Drag is modelled as a quadratic term with a baseball-like coefficient (0.007 per metre); a model, not a measurement. Readable code is a letter to a person A program is run by a machine once and read by people many times: the next engineer, the reviewer, you in six months. The well-known line from the preface of Structure and Interpretation of Computer Programs is: "Programs must be written for people to read, and only incidentally for machines to execute." The machine will accept either version below. Only one of them can be checked by a human. def f(a, b): return (a / 3.6) ** 2 / (2 * b * 9.81) def braking_distance(speed_kmh, friction): speed = speed_kmh / 3.6 # convert to metres per second return speed ** 2 / (2 * friction * 9.81) Both give 14.05 m for 50 km/h and a friction of 0.7, the braking distance of Physics I. Only the second tells you what it means, and so lets a reader spot a wrong constant. Good names, small functions and comments that say why are the cheapest debugging tools there are. People disagree on how much structure is enough: some teams favour heavy up-front design, others short cycles of build, test and revise; Software Engineering (34/31) covers both camps. What a graduate just sees A program is instructions plus state; to understand it, track the variables line by line. Every value has a type and a size, and a number too large for its box is a real way to lose a rocket. Loops run until their stop value, not through it: watch the edges. Break a problem into named functions you can test one at a time. A function that calls itself can be elegant and wildly wasteful; counting calls shows which. The right container (list or dictionary) can be the difference between instant and never. Debugging means hypotheses and experiments; halve the suspects each time. Simulation is a rate of change plus a loop, and smaller steps cost more for less error. Code is read far more often than it is written. Where it shows up next Data Structures (34/23) and Algorithms (34/24): the list-versus-dictionary and naive-versus-memo contrasts above, measured properly. Computer Architecture (34/25): the fixed-size boxes and overflow are the hardware's registers; instructions plus state is literally how a processor works. Software Engineering (34/31): decomposition, testing and readable code, scaled to teams and years. Differential Equations (34/03), Dynamics (34/12), Control Systems (34/20): the Euler loop is the starting point of numerical solvers, vehicle simulators and the code that runs a controller. Machine Learning (34/32): training is a loop that nudges numbers until the error falls. If you want to go deeper 📘 Standard textbook. John Guttag, Introduction to Computation and Programming Using Python (3rd ed., MIT Press, 2021), the text behind MIT's introductory course, written for engineers and scientists, with modelling and data. 📘 Gentler, free. Allen Downey, Think Python (3rd ed., Green Tea Press / O'Reilly), free to read online at greenteapress.com. For the deeper "why", Structure and Interpretation of Computer Programs by Abelson and Sussman is free online from MIT Press. 🌐 Free course. MIT OpenCourseWare 6.0001 Introduction to Computer Science and Programming in Python (Fall 2016), or Harvard's CS50x (starts in C, then Python and SQL) and CS50P (Python only), free on OpenCourseWare. The takeaway A program is instructions acting on state. Variables, types, choices, loops and functions are how you say it exactly; lists and dictionaries are how you hold data; debugging is hypothesis and experiment; and a simulation is a rate of change inside a loop. The graduate's real skill is reading code, predicting it, and taking a big problem apart. Try this: take any small thing you do by hand, like splitting a bill or converting recipe units, and write it as exact steps for a friend to follow without any judgment. Then watch where they get stuck: those are your bugs. Sources & Further Reading Sources. Ariane 5 flight 501 (4 June 1996; 64-bit floating-point to 16-bit signed integer conversion overflow; about 37 seconds; more than US$370 million): Wikipedia, "Ariane flight V88", which summarises the Inquiry Board's report. The Mark II moth (9 September 1947, logbook note "First actual case of bug being found", now at the Smithsonian) from the Computer History Museum and JSTOR Daily, "The bug in the computer bug story", which notes the term was already in use. The SICP quotation from the preface of Abelson & Sussman, Structure and Interpretation of Computer Programs (MIT Press, 1985). CS50x language order from cs50.harvard.edu/x; Think Python 3rd ed. from greenteapress.com. Computed and checked in node, including by running the page's own interpreter on its example programs: 15; 8 Collatz steps; −2; 40,000 wraps to −25,536 in 16 bits; fib call counts 15, 177, 21,891 and 2,692,537 (and 2n−1 with a memo); projectile ranges 91.74 m exact and 102.1, 93.9, 91.8 m for steps of 0.5, 0.1 and 0.001 s; 14.05 m braking distance. 🌐 MIT OpenCourseWare: 6.0001 🌐 Harvard CS50x and CS50P 📘 Think Python, 3rd edition (free online) 📘 Guttag, Introduction to Computation and Programming Using Python, 3rd ed. (MIT Press) 🌐 JSTOR Daily: the bug in the computer bug story Step 2. Discrete Mathematics: Counting, Logic and Proof ------------------------------------------------------- Why: Logic, sets, proofs and counting: the maths computers are built on. Computers cannot handle the smooth infinite; they handle countable things. This is the maths of switches, steps, networks and clocks. Your phone adds two numbers in a few billionths of a second, using nothing but switches that are either on or off. A barcode scanner knows you mistyped one digit of a book's number before it looks anything up. A map app finds the quickest route among millions of roads without trying them all. And a password check takes the same instant whether the password is long or short. None of these runs on the smooth, continuous maths of calculus. They run on things you can count: bits, steps, roads, remainders. A graduate of a discrete mathematics course carries a small set of habits for reasoning about countable things, and they are the habits that separate "it seems to work" from "it must work". This piece gives you those habits through six ideas and eight things to try: build an adder from logic, count what you cannot list, watch an induction proof grow, search a graph, wrap numbers around a clock, and see why some programs take longer than the age of the universe. The course in one box Who takes it: every computer science student in the first year, and many engineers; it is the entry ticket to the theory side of computing. What it's for: reasoning exactly about finite and countable things: logic, collections, steps, networks. Comes after: nothing but school mathematics. (Programming Fundamentals, 34/09, helps but isn't required.) Leads to: Algorithms (34/24), Computer Architecture (34/25), Databases (34/28) and Theory of Computation (34/29) all list it as a prerequisite. Honest line: you won't be able to prove a hard theorem after this. You will be able to see why a loop must stop, why a network has a shortest path, and why one algorithm will never finish. For easier first reads, see the library's Graph Theory (12/18) and Cryptography (12/09); this piece goes further into logic, proof, counting and growth. Logic: truth tables become circuits A proposition is a statement that is either true or false. Three operations build all the rest: AND (true only when both are true), OR (true when at least one is) and NOT (flips it). A truth table lists every case, and for two inputs there are only four rows. Another useful operation is XOR ("one or the other, but not both"). ABA AND BA OR BA XOR B 00000 01011 10011 11110 Boole's 1854 book treated logic as algebra; the AND/OR/NOT algebra we use today was tidied up by his successors. The leap to hardware came in 1937, when Claude Shannon's MIT thesis showed that networks of switches could carry out exactly this algebra. Every gate in a processor since is a physical truth table. Look at the XOR column: it is adding. 1 + 1 = 10 in binary, so the digit is 0 (XOR) and there is a carry of 1 (AND). Chain that into a full adder (it also takes the carry from the column on its right) and line four of them up, and you have a circuit that adds numbers up to 15. Choose two numbers and watch the carries ripple. Interactive · Add with nothing but logic gates First number Second number Without JavaScript: 7 + 9 is 0111 + 1001 in binary. The carry ripples through all four columns and the result is 10000, which is 16. sum = A XOR B XOR carry-in    carry-out = (A AND B) OR (carry-in AND (A XOR B)) That is a complete circuit for one column: five gates. Everything a processor does (comparing, jumping, multiplying) is built the same way, so Computer Architecture (34/25) is largely this idea scaled up. Engineers also use the same logic on whole systems: a fault tree in reliability analysis is AND and OR gates over "this valve fails" and "this pump fails" (Systems Engineering, 34/22). Sets, functions and counting: sorting the world and counting it A set is a collection with no repeats; a function assigns each member of one set exactly one member of another. A function is one-to-one if no two inputs share an output, and onto if every possible output is hit. Remember these words: "the hash has collisions" means "the function is not one-to-one", and a compression scheme that shrinks every file would have to be one-to-one into a smaller set, which is impossible. The first counting rule is about overlap. If you add the sizes of two sets, anything in both gets counted twice, so subtract it once. This is inclusion–exclusion: |A ∪ B| = |A| + |B| − |A ∩ B| In a class of 40, 25 take computing, 18 take maths and 9 take both: 25 + 18 − 9 = 34 take at least one, so 6 take neither. Interactive · Count the overlap Take computing Take maths Take both Without JavaScript: in a class of 40 with 25 in computing, 18 in maths and 9 in both, 34 take at least one subject and 6 take neither. Next, counting arrangements. If order matters, choose the first item in n ways, the next in n−1, and so on: choosing and ordering k of n items gives n!/(n−k)! possibilities. If order doesn't matter, divide by the k! ways to shuffle the chosen ones: that is a combination, written C(n,k). C(n,k) = n! / ( k! (n−k)! ) Worked example: a five-card poker hand from 52 cards is C(52,5) = 2,598,960 hands, while the number of orderings of a whole deck is 52! ≈ 8.07×1067. A shuffled deck has almost certainly never been in that order before in history. Interactive · Orderings versus selections Items to choose from: n Items chosen: k Without JavaScript: choosing 3 of 10 gives 720 ordered ways and 120 unordered ways; choosing 5 of 52 gives 2,598,960 hands. The sneakiest counting idea has no formula. The pigeonhole principle says that if you put more than m items into m boxes, some box holds two. It sounds trivial, and it proves strong things: among any 13 people, two share a birth month; no compression method can shrink every file; any hash function that maps many inputs to few outputs must collide. Dirichlet used it in number theory in 1834. Drop random people into the seven days of the week: you are guaranteed a repeat by the eighth, and you will usually get one sooner (most often between the 3rd and 5th drop). Interactive · Pigeons into seven boxes Drop a pigeonDrop until a doubleClear Without JavaScript: with 7 boxes, the 8th pigeon is guaranteed to share a box. With random drops the first double typically comes earlier, most often between the 3rd and the 5th pigeon. Proof: induction and contradiction You can't test infinitely many cases, so mathematicians prove. Two tools do most of the work. Induction is the domino proof: show the first domino falls (the base case), and show that if any domino falls, the next one does (the step). Then they all fall. Take the claim that the first n odd numbers add up to n². Base case: 1 = 1². Step: if the first n odd numbers make an n×n square, the next odd number, 2n+1, is exactly an L-shaped border that turns it into an (n+1)×(n+1) square. Slide n and watch the border go on. Interactive · Squares grown by odd numbers Odd numbers added: n Without JavaScript: 1 + 3 + 5 + 7 + 9 = 25 = 5². Adding the next odd number, 11, makes 36 = 6²: a border of 2×5+1 = 11 squares. Induction is how you prove a loop does what it should: the loop invariant is the claim, the first pass is the base case, and each pass is the step. It is also the heart of recursion, which is a program that calls a smaller copy of itself. Contradiction works the other way: assume the claim is false and show that this leads to nonsense. Euclid's proof that there are infinitely many primes is usually told this way: suppose the list of primes were finite, multiply them all together and add one. That number leaves remainder 1 when divided by every prime on your list, so either it is itself a new prime or it has a prime factor you didn't list. Either way the list was incomplete. (Some historians point out Euclid's own argument can be read as a direct one; the contradiction telling is the modern standard.) A programmer uses the same move when they say "suppose the algorithm returned a wrong answer; follow that and it breaks the invariant". Graphs and trees: things and their connections A graph is dots (nodes) and links (edges); the library's Graph Theory piece (12/18) introduced it. Here is a deeper habit. Count the edge ends: each edge has two, so the degrees (links at each node) always add up to exactly twice the number of edges. This handshake lemma is why the number of guests who shook an odd number of hands is always even. The workhorse algorithm is breadth-first search: visit the start, then everything one step away, then everything two steps away, using a queue. It finds the fewest-hops route to every node. The edges it used to reach each new node form a tree: a connected graph with no loops, which always has exactly one fewer edge than nodes. Pick a start and press Step. Interactive · Breadth-first search, one step at a time StepRun to endRestart Without JavaScript: in the 8-node, 11-edge graph, the degrees add to 22, twice the edge count. Breadth-first search from A reaches every node in at most 3 hops, using exactly 7 edges, one fewer than the number of nodes. Graphs appear everywhere in the two majors. A truss is a graph whose nodes are joints and edges are members (Statics, 34/10). A circuit is a graph (the loop equations you meet in Linear Algebra, 34/04, come straight from it). A road map, a network of routers, a dependency chart for building a product and a social network are all graphs, and a file system is a tree (Operating Systems, 34/26). Routers and links are a graph too (Computer Networks, 34/27). Modular arithmetic: clocks, hashes and check digits On a clock, 10 o'clock plus 5 hours is 3 o'clock, not 15. Modular arithmetic wraps numbers around: a mod m is the remainder when you divide a by m. It is used wherever a quantity cycles or has to be squeezed into a fixed number of slots. Try the clock, and below it a tiny hash table: each word is turned into a number, and that number mod the table size picks its slot. Interactive · Clock and hash table The number Clock size m (also the number of table slots) Without JavaScript: 47 mod 8 = 7, because 47 = 5×8 + 7. With 8 slots, adding up each word's letter codes and taking the remainder sends "bolt" and "cam" to the same slot, and "shaft" and "valve" to the same slot: two collisions. Slide the clock size up and the collisions mostly disappear, but by the pigeonhole principle you can't remove them while there are more words than slots. Databases (Databases, 34/28) and compilers use hash tables everywhere. Remainders also catch mistakes. The last digit of a 13-digit book number (ISBN-13) is chosen so that the digits, weighted 1, 3, 1, 3 and so on, add to a multiple of 10. Take 978-0-306-40615-7: the first twelve digits give 93, and 10 − (93 mod 10) = 7. Change any one digit and the total is no longer a multiple of 10, so a scanner rejects it. Most swaps of neighbouring digits are caught too (those that differ by 5 slip through). Cryptography (12/09) is the same arithmetic taken to huge numbers, and it underlies Computer Security (34/33). Engineers meet it in machines. A shaft encoder reports its angle modulo one turn. And gear designers sometimes choose tooth counts with no common factor, such as 20 and 21, so that each tooth meets every tooth on the other gear before any pair repeats: the pattern repeats only after lcm(20, 21) = 420 meshes, against 60 for 20 and 30 teeth, which spreads wear evenly (Machine Design, 34/19). Big-O: growth as a counting idea How long does a program take? Count its steps, as a function of the input size n, and keep only the part that grows fastest: big-O notation. Searching an unsorted list takes about n steps, O(n). Searching a sorted list by repeatedly halving takes about log2n, which is 20 steps for a million items. Comparing every pair is about n². And trying every subset of n things is 2n, which is where counting becomes a wall. Pick a size and a machine speed. The shape of the growth matters more than the speed of the machine. Interactive · How long would it take? Problem size n Machine speed: one billion steps per second (an illustrative round number). Without JavaScript: at n = 1,000,000 an O(n) job takes 0.001 seconds, an n log n job 0.02 seconds, an n² job 1,000 seconds (about 17 minutes), and a 2n job would take far longer than the age of the universe. Even at n = 60, a 2n job needs about 36.5 years at a billion steps per second. That wall is the difference between an algorithm and a method that works in principle. Algorithms (34/24) is a whole course on getting from the right side of this table to the left; Theory of Computation (34/29) asks which problems can never be moved over. What a graduate just sees Any decision, however tangled, is AND, OR and NOT; a processor is a pile of truth tables. When you count two overlapping groups, subtract the overlap once. Order matters means n!/(n−k)!; order doesn't matter means divide by k!. More items than boxes means some box holds two: collisions are guaranteed, not unlucky. Induction is dominoes: base case plus step proves infinitely many cases; a loop invariant is the same. To prove something is impossible, assume it and chase the contradiction. Graphs are dots and links; edge ends add to twice the edges; a tree has one fewer edge than nodes. A remainder is a clock: mod wraps numbers into slots, and a check digit is a remainder that catches typos. Growth shapes (log, linear, n log n, squared, exponential) decide what is feasible far more than hardware does. Where it shows up next Algorithms (34/24) and Data Structures (34/23): induction proves them correct, big-O ranks them, graphs and trees are their raw material. Computer Architecture (34/25): gates, adders and the whole processor are applied logic. Databases (34/28): sets, functions and relations are the model; hashing makes lookups fast. Theory of Computation (34/29): proofs by contradiction show some problems are unsolvable. Statics (34/10), Systems Engineering (34/22) and Machine Design (34/19): trusses as graphs, fault trees as logic, tooth counts as remainders. If you want to go deeper 📘 Kenneth Rosen, Discrete Mathematics and Its Applications (McGraw Hill; 8th edition). The most-assigned university text, with huge problem sets. 📘 Susanna Epp, Discrete Mathematics with Applications (Cengage; 5th edition). Slower and gentler on logic and proof. 📖 Richard Hammack, Book of Proof (free from the author, who is at Virginia Commonwealth University): the gentle route for learning alone, focused on how to write proofs. For a free full text aimed at computer scientists, see the open textbook for MIT's 6.042J below. 🌐 MIT OpenCourseWare 6.042J, Mathematics for Computer Science (Spring 2015): lectures, problem sets and a free textbook by Lehman, Leighton and Meyer. The takeaway Discrete mathematics is exact reasoning about things you can count. Logic turns decisions into circuits, counting tells you what is possible, proof tells you what must be true for every case, graphs model connection, remainders give clocks and check digits, and growth rates tell you what will ever finish. Try this: check an ISBN on the back of a book yourself, weighting its digits 1, 3, 1, 3 and adding them. The total should end in 0. Then in the growth widget above, set n to 40 and then to 60, and watch the 2n job go from minutes to years while the n² job barely moves. Sources & Further Reading Sources. Logic, counting, induction, graphs and modular arithmetic are standard textbook content (Rosen; Lehman, Leighton and Meyer); every number shown was recomputed in code. Boole, An Investigation of the Laws of Thought (1854), and the later history of Boolean algebra: Wikipedia, "The Laws of Thought". Shannon, "A Symbolic Analysis of Relay and Switching Circuits" (MIT master's thesis, 1937). Euclid, Elements IX.20 (D. Joyce's commentary). Dirichlet and the pigeonhole principle (1834): Wikipedia, "Pigeonhole principle". ISBN-13 check digit: Wikipedia, "Check digit" and the ISBN agency rules. Age of the universe, about 13.8 billion years: NASA, from the Planck 2018 results. Go deeper. The books and course above. Step 3. Calculus I: Slopes, Totals and the Bridge Between Them -------------------------------------------------------------- Why: Rates of change and limits, which reappear in algorithm analysis and machine learning. Your car's speedometer is a derivative. Its odometer is an integral. Everything a first calculus course teaches is a way of moving between the two. Look at a dashboard. The odometer says how far you have gone in total. The speedometer says how fast the total is changing right now. Press the accelerator and the speedometer moves first; the odometer follows, a little behind, like a patient accountant adding up what the speedometer reported. Nobody gave the speedometer a ruler or a clock to look at the whole trip. It reads one instant. Yet it reports a rate, which is a statement about change, from a single moment. How can a single moment say anything about change? That puzzle is what the course exists to answer, and the answer turned out to run most of modern engineering and computing. This is the second time the library has met calculus. Calculus: Derivatives, Integrals, and the Language of Motion (12/11) is the easier first read, with the tangent line and the rectangle sum. Here we go a step further: what the course trains you to see, how a computer gets it wrong, and where the idea is used afterwards. The course in one box Who takes it: first-year students in Mechanical & Aerospace Engineering and in Computer Science, and almost every other science or engineering degree. What it is for: turning "how much?" into "how fast?" and back, so that change can be calculated instead of guessed. Comes after: nothing in this series. Algebra and a little trigonometry are all it assumes. Leads to: Multivariable Calculus (34/02), Differential Equations (34/03), Probability & Statistics (34/05), Physics I: Mechanics (34/06), Thermodynamics (34/14), and from them nearly everything else on both majors. Honest line: you will not be able to differentiate a hard formula by hand after this. You will see why a flat spot on a curve is where the best answer hides, and why the area under a rate is a total. A limit is where a calculation settles The speedometer puzzle is this. Speed is distance divided by time, but in an instant no time passes and no distance is covered, so you seem to be dividing zero by zero. The way out is to stop asking what happens at zero and ask what a sequence of better and better answers is settling towards. Measure over one second, then a tenth, then a hundredth, and watch the average speed home in on a number. That number is the limit. speed now = limit of (distance change ÷ time change) as the time change shrinks to 0 A graduate does not carry the formal definition around, but carries the habit: if a quantity looks like 0 ÷ 0, ask what it is approaching. Take sin(x) ÷ x as x goes to zero, with x in radians. At x = 0.1 it is 0.99833; at 0.01, 0.99998; at 0.001, 0.9999998. It never "is" 1 at zero, since it is undefined there, but it settles on 1. That one limit is why the derivative of sine turns out to be cosine. Interactive · Shrink the gap until the computer gives up We estimate the slope of ex at x = 1 by (e1+h − e) ÷ h. The true slope is e = 2.718281828459045. Make the gap h smaller. Gap h = 10−k The error falls as the gap shrinks, as the limit promises, until about h = 10−8, where it bottoms out near 7 × 10−9. Shrink further and it gets worse: the two values being subtracted agree in almost all of their roughly 16 stored digits, so the subtraction wipes out the information. At 10−16 the answer is exactly 0. This is a computer-science lesson hiding in a calculus course: the limit is a mathematical idea, and a machine can only approach it so far. The derivative is a slope, and a slope is a rate Zoom in on any smooth curve and it straightens out. The steepness of that straight piece is the derivative. In plain words: how much the output moves per unit nudge of the input. If the curve is distance against time, the derivative is speed. If it is temperature against position, it is how sharply it warms as you walk. Rate and slope are one thing seen two ways. f′(x) = limit of [f(x+h) − f(x)] ÷ h as h → 0 The graduate's real asset is not computing derivatives but reading them. Where the curve is rising, the derivative is positive. Where it is flat, the derivative is zero. Where the curve is steepest, the derivative is at its peak. Try it: the lower graph is the derivative of the upper one, drawn point by point. Interactive · A curve and its slope, side by side x³ − 3x sin x bell: e^(−x²) Position x Check the three curves. Every time the top curve peaks or dips, the bottom one crosses zero. Every time the top is climbing, the bottom is above the axis. For x³ − 3x the slope is 3x² − 3, which is zero at x = −1 and x = 1: the hill top and the valley floor. The chain rule: rates multiply down a chain Rates often come in chains. A bicycle's pedals turn the chainring, the chain turns the rear wheel, the wheel moves the bike. If the wheel turns 3 times per pedal turn, and the bike moves 2 metres per wheel turn, the bike moves 6 metres per pedal turn. You multiply the ratios. That is the chain rule, and it is the most used rule in the course. d(outer)/d(input) = d(outer)/d(middle) × d(middle)/d(input) The classic worked case is a balloon. Its volume depends on its radius, and the radius depends on time. At radius r the surface has area 4πr², so one extra centimetre of radius adds a shell of volume about 4πr² cm³: that is dV/dr. Multiply by how fast the radius is growing and you have how fast the volume is growing. At r = 10 cm, growing 2 cm each second, volume grows at 4π × 100 × 2 ≈ 2,513 cm³ per second. Pull the sliders and confirm it. Interactive · Inflate a balloon Radius now Radius is growing at The picture shows why it works: the shaded shell is what one second adds, a skin of area 4πr² and thickness equal to the radius growth. The same rule runs inside every neural network, where the "chain" is dozens of layers long and the multiplication is called backpropagation (Machine Learning, 34/32; Multivariable Calculus, 34/02). Where the slope is zero, something is best At the top of a hill you stop going up and have not yet started going down. The slope is zero. So to find the biggest or smallest value of anything smooth (strongest, cheapest, lightest, fastest) look for where its derivative is zero. That is optimisation, and it is why engineers love the derivative. Take a 30 cm by 20 cm sheet of card. Cut a square of side x from each corner and fold up the sides to make an open box. Its volume is V = x(30 − 2x)(20 − 2x). Cut too little and the box is shallow. Cut too much and it is narrow. In between there is a best x, and the slope tells you where: at x ≈ 3.92 cm the volume peaks at about 1,056 cm³. Interactive · The best box Corner cut x Jump to the flat spot Notice what the slope does as you drag. To the left of the peak the slope is positive, so a bigger cut helps. To the right it is negative, so a smaller cut helps. At the peak it is zero and nothing nearby is better. Gradient descent, the algorithm that trains machine-learning models, is exactly this reasoning repeated: look at the slope, step downhill, repeat. The integral adds up a rate into a total The odometer is the speedometer added up over time. Draw speed against time; the area between the curve and the time axis is distance. That is the integral. Anywhere a rate is known and a total is wanted (litres per minute into a tank, watts into a battery, newtons over a distance) the answer is an area. Try it before you read on. A car accelerates steadily from 0 to 20 m/s in 10 seconds, cruises at 20 m/s for 30 seconds, then brakes steadily to a stop in 10 seconds. How far has it gone? Interactive · Predict, then reveal 600 m 800 m 1,000 m 1,200 m Choose an answer. The shape is two triangles and a rectangle: ½ × 10 × 20 + 30 × 20 + ½ × 10 × 20 = 100 + 600 + 100 = 800 m. The common wrong guess, 1,000 m, uses the top speed for all 50 seconds and forgets that the car spends time slower than that. The Fundamental Theorem: two jobs, one idea Here is the surprise that makes the course a single subject. Build a running total from a rate: the amount in the tank after time T. Then ask how fast that total is growing at T. The answer is just the rate at T. Accumulating and differentiating undo each other, the way the odometer and speedometer do. Newton and Leibniz, working separately in the late 1600s, each saw this. if A(T) = area under the rate up to T, then A′(T) = the rate at T Its practical power is that you can find a total without adding anything: find a function whose slope is your rate and subtract its values at the two ends. Below, water flows into a tank at a rate that wobbles: 4 + 3 sin(t/2) litres per minute. Drag the time and watch the right-hand graph, the tank's total, steepen exactly when the rate on the left is high. Interactive · The tank and its rate Time T The readout checks the theorem two ways: area by adding 600 thin slices, and the exact formula 4T + 6(1 − cos(T/2)). At T = 12 minutes both give 48.24 litres. The slope of the total at that moment is 4 + 3 sin 6 ≈ 3.16 litres per minute, the rate at that moment. Every smooth thing is nearly a straight line The last habit is the most useful in daily engineering. Close to any point, a smooth curve is almost its tangent line, so you can replace it with a straight line and be nearly right. The small-angle rule sin x ≈ x is why a pendulum swings at a steady rhythm. The rule √(1 + x) ≈ 1 + x/2 gives mental square roots: √1.1 ≈ 1.05, true value 1.0488. f(a + x) ≈ f(a) + f′(a) · x   (good when x is small) How small is small? The error shrinks faster than the step. Halve the step and the error falls about four times for √(1 + x) and ex, and about eight times for sine. Interactive · How good is the straight line? sin x ≈ x √(1+x) ≈ 1 + x/2 eˣ ≈ 1 + x Step x from the point What a graduate just sees A rate and a slope are the same thing, and "how fast?" always means a derivative. A total is an area under a rate, and adding up thin slices is a calculation, not a mystery. Rates multiply along a chain: gear ratios, units, layers of a network. The best value of a smooth quantity sits where its slope is zero. Differentiating and accumulating are inverse jobs, so a total can often be found without adding. Up close, everything smooth is a straight line, and engineers exploit that constantly. Subtracting two nearly equal numbers on a computer destroys precision, so a naive slope estimate gets worse when the gap gets too small. Where it shows up next Physics I (34/06) and Dynamics (34/12): velocity is the derivative of position, acceleration of velocity, and Newton's law ties force to the second one. Differential Equations (34/03): when a law is written as a rate, solving it means integrating, which is the whole next course. Thermodynamics (34/14) and Heat Transfer (34/16): heat added is an integral of power; temperature profiles are read from slopes. Probability & Statistics (34/05): the chance of a range of outcomes is the area under a density curve. Algorithms (34/24) and Machine Learning (34/32): growth rates of running time are compared with limits, and models are trained by following slopes downhill. If you want to go deeper 📘 Textbook: James Stewart, Daniel Clegg and Saleem Watson, Calculus: Early Transcendentals (9th ed., Cengage). The most-assigned text; best for worked examples and a huge problem bank. 📘 Textbook: Hass, Heil, Bogacki and Weir, Thomas' Calculus (15th ed., Pearson). Strong on applications, popular in engineering departments. ▶️ Gentler: Grant Sanderson's Essence of Calculus series on 3Blue1Brown, a visual tour of the same ideas. Also Steven Strogatz, Infinite Powers, for the story. 🌐 Free course: MIT OpenCourseWare 18.01SC Single Variable Calculus, with video lectures, notes and problems. Khan Academy also covers it. The takeaway Calculus I teaches two moves and one bridge. The derivative turns a total into a rate (a slope); the integral turns a rate into a total (an area); and the Fundamental Theorem says they undo each other. From that come the habits of mind: chain rates together, look for zero slope to find the best, and treat smooth things as lines up close. Our slope estimate for ex was best near a gap of 10−8 and useless at 10−16, a reminder that the ideas are exact and the machines are not. Try this: next time you are in a car or on a bike, watch the speedometer and ask what the area under its history means. Then on a hill, find the spot where the road is flat. That is a derivative equal to zero. Sources & Further Reading Sources. Every number in the interactives was computed in node: the forward-difference error of ex at x = 1 for h = 10−1 to 10−16 (best 6.6 × 10−9 at 10−8, exactly 0 at 10−16, in IEEE double precision); sin(x)/x at 0.1, 0.01, 0.001; the box V(x) = 4x³ − 100x² + 600x, zero slope at x = (50 − √700)/6 = 3.9237, V = 1,056.3 cm³; the balloon 4π × 10² × 2 = 2,513.27 cm³/s; the car, 800 m; the tank, A(12) = 48.239 L; small-step errors of the three approximations. Book editions checked against the publishers' pages (Cengage, Pearson) and the course numbers against MIT OpenCourseWare. 🌐 MIT OpenCourseWare 18.01SC Single Variable Calculus ▶️ 3Blue1Brown: Essence of Calculus 🌐 Khan Academy: Calculus 1 📘 Stewart, Clegg and Watson, Calculus: Early Transcendentals, 9th ed. (Cengage) 📘 Hass, Heil, Bogacki and Weir, Thomas' Calculus, 15th ed. (Pearson) 📘 Steven Strogatz, Infinite Powers, a popular history of calculus Step 4. Data Structures: How Arrangement Decides Speed ------------------------------------------------------ Why: How data is arranged decides how fast a program can be. A search that comes back in a fifth of a second across billions of records is not a faster computer. It is the same records, put in a better order. Type three letters into your phone's contacts and the list narrows before your thumb lifts. Your contacts are probably a few hundred names, so that is no miracle. But the same trick works when the list is a billion long: a web search, a map lookup, a spell checker that underlines a word the instant you finish typing it. Nothing in your phone got a billion times faster. The data was arranged so that the answer does not require looking at everything. That is the whole subject. A program is two things: the steps it takes, and the way it keeps its information. Change the second and the first often shrinks from "check every item" to "check a handful". A computer science graduate looks at any problem and asks, almost without noticing, what operations will I do most, and what shape of storage makes those cheap? The course in one box Who takes it: every computer science major in the first or second year, and many engineering, maths and data science students. What it is for: learning the handful of standard containers every program is built from, and what each one is fast and slow at. Comes after: Programming Fundamentals (34/09). Leads to: Algorithms (34/24), Operating Systems (34/26), Databases (34/28), Programming Languages & Compilers (34/30). What this piece gives you: you will not be able to implement a red-black tree from memory afterwards. You will see why a database index is a tree, why a dictionary lookup does not slow down as it grows, and which container to reach for first. Arrays and linked lists: one street, two ways to number it Memory is a very long street of numbered mailboxes. An array reserves a row of neighbouring boxes and stores one item per box. To find item number 500,000 you do arithmetic: start address plus 500,000 times the size of one item, and walk straight there. A linked list scatters its items anywhere, and each item carries a note saying where the next one lives. To reach item 500,000 you must read 500,000 notes in order. The rule a graduate remembersAn array is fast to get and slow to insert; a linked list is the reverse. Getting item k costs 1 step in an array and about k steps in a list. Inserting at the front costs n shifts in an array and 1 relink in a list. Worked number: a million 4-byte integers. Insert one at the front of the array and all 1,000,000 must slide along one box. In the list it is a single new node pointing at the old head. Now read the middle one: the array jumps there in one step, the list takes 500,000 hops. Interactive · Array against linked list Read the middle item Insert at the front Insert in the middle Read every item Number of items With one million items: reading the middle takes 1 step in an array and 500,000 hops in a list; inserting at the front takes 1,000,000 shifts in an array and 1 relink in a list. Assumes a list with only a head pointer, and 4-byte items on 64-byte cache lines. The bar lengths use a log scale. The last button hides the twist. Reading every item is the same number of steps either way, yet the array wins in practice. A processor does not fetch one box from memory; it fetches a whole cache line, commonly 64 bytes, which is sixteen of those integers at once. An array's neighbours arrive for free. A list's next node may sit in some unrelated line, so each hop can be a fresh trip. For a million integers that is about 62,500 trips against up to 1,000,000. This is why programmers who know the theory still reach for arrays first. Stacks and queues: restricting yourself on purpose A stack and a queue are not new storage. They are an array or list with a rule about the doors. A stack has one door: the last thing in is the first thing out, like plates in a cafeteria. A queue has two: you join at the back and leave from the front, so first in is first out. Why would anyone give up freedom? Because the restriction is the meaning. Your program's function calls form a stack: when f calls g, g must finish before f resumes. The undo button is a stack. A printer's job list, a web server's waiting requests and the order a breadth-first search visits places are queues. The rule a graduate remembersStack: last in, first out. Queue: first in, first out. Either one adds and removes in 1 step, however many items are inside. Interactive · Do the brackets match? Whether (a[b]{c}) is balanced is a stack problem: push each opener; each closer must match the one on top. Pick a text and step through. (a[b]{c}) (a[b)] {[(]} ((x) Step0 Text Stack (top on the left) Without scripts: in (a[b]{c}) each closer meets its own opener on top of the stack, so it is balanced. In (a[b)] the closer ) meets [ on top, so it is not. Interactive · Same letters, two doors Add the next letterTake one outReset Stack Queue Add A, B, C to both. Taking one out gives C from the stack (newest) and A from the queue (oldest). Hash tables: why lookup does not depend on size Suppose you want to find "maple" among a million words without scanning. The idea: do not search, compute where it must be. A hash function chews the word into a number, and the number modulo the table size picks a bucket. Looking it up later repeats the same arithmetic and goes straight to that bucket. The cost is the arithmetic, which does not care whether the table holds a hundred words or a hundred million. The catch is that different words can land in the same bucket: a collision. They are unavoidable, and surprisingly early. Drop 23 keys into 365 buckets at random and the chance that at least two share one is already 50.7%, which is the birthday paradox. The usual fix is chaining: each bucket holds a short list of everything that landed there. Another, open addressing, steps to the next free bucket. The rule a graduate remembersWith a good hash function and a table kept comfortably roomy, lookup, insert and delete take about 1 step on average, regardless of how many items are stored. The roominess is the load factor: items divided by buckets. Keep it low by rebuilding into a bigger table, typically doubling, when it climbs. The worst case, everything in one bucket, is as slow as a list. Interactive · Watch the collisions Hash: start at 0; for each letter, multiply by 31 and add the letter's code; take the remainder after dividing by the number of buckets. Add words and drag the bucket count. Add a wordAdd fiveClear Buckets Example: the first eight words (maple, river, stone, cloud, tiger, piano, lemon, bridge) in 8 buckets put maple, stone and cloud in one bucket, piano and bridge in another, and leave 3 buckets empty. In 32 buckets the longest chain is 2. Add eight words to eight buckets, then slide the bucket count up. Chains shrink and most lookups need a single glance. That trade, spending memory to buy speed, is the hash table in one sentence. It is also why Python's dict, JavaScript's objects and Maps, and the "dictionary" or "map" in nearly every language are hash tables inside. Trees: sorted order you can search in a few hops Hash tables are quick but forget order. Ask one for "the next word after maple" and it cannot say. A binary search tree keeps order. Each node holds a key; everything smaller hangs off its left side, everything larger off its right. To find a key, compare with the root, go left or right, repeat. Every comparison discards a whole branch, usually about half the remaining keys. The rule a graduate remembersSearch cost is the tree's height, not its size. A well-packed tree of n keys has height about log2 n: a million keys, about 20 comparisons. A badly shaped one has height n. That last sentence is the trap. Insert 1, 2, 3, ... 15 in order into a plain tree and every new key is larger than all before it, so it goes right, and right, and right. The "tree" is a linked list leaning sideways, 15 levels deep. Fifteen keys inserted in a smart order (8, 4, 12, ...) give height 4. Interactive · Build a tree and watch it lean Insert 1 to 15 in orderInsert in a balanced orderInsert 15 shuffledClear Self-balancing (AVL): off In order, 1 to 15 makes a tree of height 15. The balanced order makes height 4, the minimum. Fifteen shuffled keys average height about 7 (from a simulation of 20,000 shuffles; the tallest seen was 12). Now press the self-balancing button and insert 1 to 15 in order again. The height is 4. An AVL tree (named for its inventors, Adelson-Velsky and Landis, 1962) checks after each insertion whether one side has grown two levels taller than the other, and if so performs a rotation: a local re-hanging of three nodes that keeps the sorted order but shortens the tall side. Red-black trees, the kind inside many standard libraries, use a different bookkeeping for the same promise. B-trees, which have hundreds of children per node so that one disk read does a lot of narrowing, are what most database indexes and file systems use. The principle is constant: keep the height logarithmic, and search stays fast however big the data grows. Heaps: the cheapest way to always know the biggest Sometimes you do not need everything sorted, only the next most urgent thing: the next patient, the next road to explore, the next event in a simulation. That is a priority queue, and the standard way to build one is a heap. A heap is a tree with one rule only: every parent is smaller than its children (a min-heap). The smallest item is therefore always at the top, readable in 1 step. Nothing else is ordered. The trick that makes it neat: a heap can be packed into a plain array. The children of position i sit at 2i+1 and 2i+2, with no pointers at all. Insert by adding at the end and letting the new item float up past any larger parent. Remove the smallest by taking the root, moving the last item to the top and letting it sink. Each trip is at most the height of the tree. The rule a graduate remembersPeek at the minimum: 1 step. Insert or remove: about log2 n steps. A heap of a million items is only 20 levels tall, so no insert or removal makes more than about 19 swaps. Interactive · Float and sink Insert a random numberInsert fiveRemove the smallestClear The same heap stored as an array Starting from 42, 17, 63, 9, 88, 25, 51 inserted one by one, 9 ends up at the root. Removing it moves 51 to the top, which sinks 2 levels. Graphs: when everything connects to everything Roads, friendships, web links and flight routes are not lists or trees: items connect to many others and loops are normal. That shape is a graph: dots (vertices) and links (edges). (The library's Graph Theory: From Königsberg to Your GPS is an easier first read on the maths; here the question is storage.) Two standard ways to store one. An adjacency matrix is a grid with one cell for every pair of vertices, marked if they are linked. Checking "are A and B linked?" is 1 step. An adjacency list gives each vertex a short list of only its actual neighbours. "Who are A's neighbours?" is quick, and nothing is stored for links that do not exist. The rule a graduate remembersA matrix costs V² cells for V vertices, always. A list costs about V + 2E entries for E undirected edges. Real graphs are sparse: most things are not connected to most other things. So lists win, unless the graph is small or nearly complete. Worked number: a road network of one million intersections, each joining about 3 roads. The matrix needs a trillion cells, 125 gigabytes even at one bit each. The list needs about 4 million entries. Interactive · Matrix or list? Vertices Average roads per vertex One million vertices with 3 links each: a matrix has 1,000,000,000,000 cells (125 GB at one bit each); an adjacency list has 4,000,000 entries. Choosing: start from the operations There is no best structure, only the best one for the operations you do most. Programmers pick by asking questions in this order: do I look things up by key? Do I need them in order? Do I always want the biggest or most urgent? Is the data links between things? Costs below are for n items, typical case. StructureStrong atWeak at ArrayRead by position, scan in order (1 step; cache-friendly)Insert or delete in the middle (~n) Linked listInsert or delete at a known spot (1)Read by position (~n); poor cache use Stack / queueNewest-first or oldest-first handling (1)Anything else Hash tableFind by exact key (1 on average)Order; worst case ~n Balanced treeFind, insert, ordered range (~log n)Slightly slower than hashing for exact keys HeapPeek at the minimum (1), insert and remove (~log n)Searching for an arbitrary item GraphConnections: routes, networksNeeds algorithms (see 34/24) The choice often matters more than tuning code. Checking each of a million customers against a banned list of a million names, held as an array, takes about half a trillion comparisons on average. Make the banned list a hash table and it is a million lookups. What a graduate just sees Memory is a street of numbered boxes; every structure is a policy for using it. Arithmetic on an address (arrays, hashing) beats following notes (lists, trees). Neighbours in memory are cheap: the cache makes arrays faster than their step counts suggest. A hash table spends memory to buy near-constant lookup, and collisions are a certainty. A tree's speed lives in its height, so the real question is whether it stays balanced. Heaps know the extreme, not the order, and that is why they are cheap. Real graphs are sparse, so store the links that exist. Ask "which operations?" before "which structure?". Where it shows up next Algorithms (34/24) is the other half: an algorithm's speed is mostly the structure it runs on. Dijkstra's shortest path is a graph plus a heap. Databases (34/28): an index is a B-tree, and a "hash join" is a hash table. Operating Systems (34/26): process schedulers are priority queues, and the call stack is a literal stack. Compilers (34/30): your source code becomes a tree, and a compiler's symbol table is a hash table. In the world: your phone's contacts, a game's pathfinding, the autocomplete on a search box, and every "undo". If you want to go deeper 📘 Textbook: Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (MIT Press, 4th ed., 2022): the standard reference, deep and rigorous, with data structures in Part III. 📘 Textbook: Sedgewick and Wayne, Algorithms (4th ed., Addison-Wesley): code-first, with a companion site. 🌐 Free and gentle: Pat Morin, Open Data Structures (opendatastructures.org), free under a Creative Commons licence, with Java, C++ and pseudocode editions. 🌐 Free course: Harvard CS50x (cs50.harvard.edu/x) covers arrays, linked lists, hash tables and trees in Week 5, free; MIT OpenCourseWare 6.006 Introduction to Algorithms goes further. The takeaway Data structures are policies for arranging memory, and each is fast at some operations and slow at others. Arrays give direct access, lists give cheap insertion, hash tables give near-constant lookup, balanced trees give ordered search in logarithmic steps, heaps give the extreme at once, and graphs hold connections. Pick by the operations you will do most. Try this: next time an app finds something instantly in a huge list, guess what structure sits behind it: hash for "exact", tree for "starts with" or "between", heap for "top ten". Then, in the tree demo above, find the order of inserts that keeps the plain tree at height 4 without turning on balancing. Sources & Further Reading Sources. Textbook material: Cormen et al., Introduction to Algorithms, 4th ed.; Sedgewick and Wayne, Algorithms. Hashing first described by Hans Peter Luhn in an IBM memo of January 1953 (Wikipedia, "Hash table"). AVL trees: Adelson-Velsky and Landis, 1962 (Wikipedia, "AVL tree"). The 64-byte cache line is typical of current x86 processors; some chips use other sizes. The step counts and simulations in the demos were computed in code. Go deeper. 📘 Introduction to Algorithms, Cormen, Leiserson, Rivest, Stein (MIT Press, 2022) 🌐 Open Data Structures (free) 🌐 Harvard CS50x (free) 🌐 MIT OpenCourseWare 6.006, Introduction to Algorithms (free) Step 5. Algorithms: Why Growth Beats Speed ------------------------------------------ Why: The ideas that make programs fast, and the proof they are correct. A method that is a thousand times slower per step can still win, by a mile, once the problem gets big enough. That one fact is most of the subject. You ask your phone for directions across a city of a million intersections and a route appears before you have put the phone down. A naive program could check every possible route. There are more routes than atoms in the universe; it would never finish. Yours finishes in a blink, because someone found a way to be clever about which routes to even consider. That cleverness is an algorithm: a precise, step-by-step method that always finishes and always gives the right answer. The course asks of any method two questions: is it correct? and how does its work grow as the problem grows? The second question has a surprisingly sharp answer, and it is the first thing a graduate learns to see. The course in one box Who takes it: every computer science major in the second year, and many maths, engineering and data science students. What it is for: a toolkit of classic methods (search, sort, graph routes, dynamic programming) plus the habit of measuring a method by how it scales, and proving it right. Comes after: Data Structures (34/23) and Discrete Mathematics (34/08). Leads to: Theory of Computation (34/29) and Machine Learning (34/32). What this piece gives you: you will not be able to prove a graph algorithm correct afterwards. You will see why one sort is thousands of times faster than another, why a GPS is a shortest-path calculation, and where "hard" problems begin. The library's Graph Theory: From Königsberg to Your GPS is an easier first read on the maps; this goes further into the methods. Big-O: growth beats constant factors To compare methods, count steps as a function of the input size n and ignore the units. Doubling the list, how much more work? A method that does n steps doubles. One that compares every pair, n², quadruples. One that tries every subset, 2n, squares itself every time you add a single item. Big-O notation keeps only that shape: O(n), O(n log n), O(n²), O(2n). The rule a graduate remembersFor large enough n, the method with the slower-growing curve wins, whatever the constant factors. A hundred times faster hardware or a clever bit of tuning buys a fixed factor; a better growth rate buys more and more as the problem grows. Worked number: take one million items. An n log2 n method needs about 20 million steps, 0.02 seconds at a billion steps a second. An n² method needs a trillion, about 16.7 minutes. Make the first method 1,000 times slower per step and it still wins once n passes about 13,700. Slide to find out. Interactive · Growth rates, live Problem size n At n = 1,000,000 and a billion steps a second: n log n takes 0.02 seconds; n² takes 16.7 minutes. At n = 60, trying all subsets (2n) takes about 36.5 years; at n = 20, trying all orderings (n!) takes about 77 years. Look at the bottom rows. At n = 60 the "try every subset" method would need about 36 years; at 20 items, "try every ordering" about 77. No faster chip rescues those, which is why computer scientists draw a hard line between methods whose cost grows like a polynomial and those that explode. We return to that line at the end. Searching: the question that halves the world Find a name in an unsorted list and you must look at every one, in the worst case n looks. But in a sorted list you can be smarter: open the middle, see whether you are too high or too low, and throw away half. Repeat. This is binary search, and it is how you look up a word in a paper dictionary without reading from A. The rule a graduate remembersEach question halves the possibilities, so n items need at most about log2 n questions. A thousand items: 10. A million: 20. A billion: 30. Play it from the other side. Think of a number from 1 to 1,000 and tell the page "higher" or "lower". Interactive · I will guess your number LowerHigherThat is itRestart Guessing the middle each time finds any number from 1 to 1,000 in at most 10 guesses. The price of the trick is the sorting: binary search only works because the list is in order. That is the pattern of the whole subject: pay once to arrange the data, then every later question is cheap. Even simple code gets this wrong. Computing the middle as (low + high) / 2 can overflow a fixed-size integer on arrays of about a billion items. Joshua Bloch reported in 2006 that this bug had sat in the binary search he wrote for Java's library for about nine years; we come back to why proofs matter below. Sorting and divide and conquer Sorting is the classic place to see growth rates fight. Insertion sort works like sorting playing cards in your hand: take each card and slide it left past bigger ones into place. It is simple, and on a shuffled list each new card travels past about half the cards before it, so the total is around n²/4 comparisons. Merge sort uses divide and conquer: split the list in half, sort each half (by the same method, recursively), then merge the two sorted halves by repeatedly taking the smaller front card. Merging costs about n steps, and there are about log2 n levels of halving, so the total is around n log2 n. John von Neumann devised merge sort in 1945, and Timsort, the sort Python uses (and Java for objects), is a hybrid of merge and insertion sort. The rule a graduate remembersDivide and conquer turns one big problem into two half-size problems plus a cheap combine step. If the combine costs n, the total is n log n. Sorting by comparison cannot beat n log n in the worst case. Interactive · Count the comparisons List length Shuffle again Merge sort on 5 2 8 1 9 3 7 4 On a shuffled list of 1,000, insertion sort makes about 250,000 comparisons and merge sort about 8,700. At 10,000 items: about 25 million against about 120,000. Recursion and remembering: dynamic programming Merge sort called itself on smaller pieces: recursion. Recursion is natural, but it can be wasteful. The Fibonacci numbers (each is the sum of the two before: 1, 1, 2, 3, 5, 8...) are defined recursively, and a direct program computes fib(n) by calling fib(n−1) and fib(n−2). Those two calls each repeat most of each other's work, and the repetition compounds: fib(40) makes 331,160,281 calls to arrive at 102,334,155. The cure is almost embarrassingly simple: write each answer down the first time, and look it up thereafter. That is memoisation, and applying it systematically to problems built from overlapping subproblems is dynamic programming, a name Richard Bellman coined in the 1950s. With the notebook, fib(40) takes 79 calls, because each of the 40 values is computed once. The rule a graduate remembersIf a recursion keeps solving the same subproblems, store the answers. The work drops from the number of calls to the number of distinct subproblems, often from exponential to a few steps per subproblem. Interactive · The notebook Which Fibonacci number fib(40) = 102,334,155 takes 331,160,281 calls the plain way and 79 with a memory of answers. fib(50) takes about 40.7 billion calls plainly and 99 with memory. Greedy: the best move right now Sometimes you can build the best answer by always taking the best-looking step. Giving change, you hand over the biggest coin that fits, and repeat. This is a greedy algorithm: fast, simple, and sometimes exactly right. Dijkstra's shortest-path method and Kruskal's way of connecting cities with the least cable are both greedy and provably optimal. But greedy can be confidently wrong. In a currency with coins 1, 3 and 4, making 6 greedily gives 4 + 1 + 1 (three coins), while 3 + 3 (two coins) is better. The real question is never "does greedy work?" but "can I prove it works for this problem?". When it fails, dynamic programming, which tries every sub-answer and keeps the best, is the usual fix. Interactive · Greedy against best US coins 1, 5, 10, 25 Coins 1, 3, 4 Coins 1, 5, 10, 21, 25 Amount to make With coins 1, 3, 4, amount 6: greedy uses 4+1+1 (3 coins), best is 3+3 (2 coins). With US coins greedy is optimal for every amount. Graph algorithms: BFS, DFS and your GPS Take a map as a graph: intersections are dots, roads are links with lengths. Three basic explorations cover most of what you will meet. Breadth-first search (BFS) visits all neighbours, then their neighbours: it finds the route with the fewest roads, using a queue. Depth-first search (DFS) plunges down one road as far as it goes, then backs up: it uses a stack, and is how a maze solver or a dependency resolver works. Fewest roads is not shortest drive. Dijkstra's algorithm always settles the nearest not-yet-settled place by total distance, using a priority queue (the heap from the last course), and relaxes its neighbours. Edsger Dijkstra devised it in 1956, which he later called a twenty-minute invention, while sitting at a café in Amsterdam, and published it in 1959. Real route planners add speed-ups on top, such as A*. The rule a graduate remembersBFS: fewest edges. Dijkstra: least total weight (non-negative weights only). With a binary heap it takes about (V + E) log V steps, which is why it scales to a continent's roads. Interactive · Three ways to explore a map from A Breadth-first Depth-first Dijkstra Step0 On this map the fewest-roads route A to F is A, B, D, F (3 roads, total 15). Dijkstra finds A, C, B, D, E, F (5 roads, total 13), the shortest drive. Correctness and invariants Fast and wrong is worthless, and testing only shows the cases you tried. The tool for certainty is the invariant: a statement that is true before a loop starts, stays true on every pass, and so, when the loop ends, says something useful. In insertion sort the invariant is: the cards already in your left hand are sorted. It holds with one card; each step slides one more card into its place without disturbing the order; so after the last card, everything is sorted. Three sentences prove it. Binary search has an invariant too: if the target is present, it lies between low and high. Programmers who skip the proof tend to get the edges wrong, and indeed the midpoint overflow bug mentioned earlier hid for about nine years in code that looked obviously fine. A graduate does not trust a loop until they can say what stays true. A preview of P versus NP Some problems resist everything above. A salesman must visit 15 cities and return, as short as possible. The obvious method checks every order: (15 − 1)! / 2 = 43,589,145,600 round trips, which a billion-a-second machine does in about 44 seconds. At 25 cities there are about 3.1×1023 trips, roughly ten million years of computing. No known method avoids this explosion in the worst case, yet checking a proposed tour against a target length is quick. Problems like this, quick to check and apparently slow to solve, sit in a class called NP. Whether every one of them also has a fast method (P = NP?) is the most famous open question in the field; most experts believe not, and the Clay Mathematics Institute offers a million dollars for a proof either way. The next course in the path, Theory of Computation (34/29), takes this up properly. What a graduate just sees Work is a function of size; the shape of that curve matters more than any constant. Halving is powerful: a million items, 20 questions. Pay to organise once, then ask cheaply many times. Split, solve, combine: most fast methods are divide and conquer. If a recursion repeats itself, write the answers down. Greedy is a hope until it is a proof. Fewest hops is not the shortest path; use the right algorithm for the right "shortest". A loop is trusted when you can state its invariant. Some problems blow up at 60 items however fast your computer is. Where it shows up next Theory of Computation (34/29): what is hard in principle, and what is impossible. Machine Learning (34/32): training is an optimisation, and gradient descent repeats a cheap, locally best step downhill. Databases (34/28): sorting and joining billions of rows is the algorithms of this course at scale. Operating Systems (34/26) and Networks (34/27): schedulers pick the next job with a priority queue, and routers compute shortest paths across the internet. In life: a maps app, a spell-checker, a recommendation list, a delivery schedule. If you want to go deeper 📘 Textbook: Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (MIT Press, 4th ed., 2022), the standard for university courses. Sedgewick and Wayne, Algorithms (4th ed.) is code-first. 📘 Gentler and free: Jeff Erickson, Algorithms (free online at jeffe.cs.illinois.edu/teaching/algorithms/, also in print), clear and proof-friendly. 🌐 Free course: MIT OpenCourseWare 6.006, Introduction to Algorithms (Spring 2020; Demaine, Ku and Solomon), with video lectures and problem sets. 🌐 Free course: Harvard CS50x, Week 3 on algorithms. The takeaway An algorithm is judged by correctness and by how its work grows with size. Growth rate beats constant factors, so halving, divide and conquer, remembering answers and exploring graphs cleverly turn impossible jobs into instant ones. Know what stays true in each loop, and know that some problems, like the salesman's, still explode. Try this: next time something loads instantly from a huge list, ask how many halvings it took (a billion is only 30). Then, in the growth demo, find the size where the 1,000-times-slower better method overtakes the quick bad one. Sources & Further Reading Sources. Textbook material: Cormen et al., Introduction to Algorithms, 4th ed. Bloch, "Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken" (Google Research blog, 2 June 2006). Dijkstra's algorithm conceived 1956, published 1959, and Fredman and Tarjan's Fibonacci-heap bound (Wikipedia, "Dijkstra's algorithm"). Merge sort by von Neumann, 1945 (Wikipedia, "Merge sort"). Bellman and dynamic programming (Wikipedia, "Dynamic programming"). P versus NP: Cook 1971, Levin 1973, US$1,000,000 Clay prize (Wikipedia, "P versus NP problem"). Step counts and timings in the demos were computed in code, assuming a billion simple steps a second. 📘 Introduction to Algorithms, Cormen, Leiserson, Rivest, Stein 📘 Algorithms, Jeff Erickson (free) 🌐 MIT OpenCourseWare 6.006 (free) 🌐 Harvard CS50x (free) Step 6. Computer Architecture: Why Your Processor Spends Its Life Waiting ------------------------------------------------------------------------- Why: From transistors to instructions: what a processor actually does. A core can start several instructions every nanosecond, then waits hundreds of ticks for one number from memory. Caches, pipelines and extra cores are all tricks for hiding that wait, and the reason clock speeds stalled is a power bill. A modern processor core can start several instructions on every tick of a clock that ticks around four billion times a second. Then it needs one number that isn't in its cache, asks main memory for it, and waits about 60 nanoseconds. On one measured chip that is roughly 250 ticks, long enough to have started on the order of a thousand instructions. Nearly everything a computer architect does is a trick for not noticing that wait. There is a second puzzle in the same machine. The fastest Pentium 4 chips ran at 3.8 GHz, and in 2004 Intel cancelled its plans for a 4 GHz one and turned to dual-core designs. Two decades later, typical clock speeds are still only a few GHz, yet the chip in your pocket is many times faster than that desktop. Speed came from somewhere other than a faster clock. This piece is about both puzzles: why a processor spends its life waiting, and why it got faster anyway. Along the way you will build an adder out of gates, encode a real instruction by hand, and break a cache on purpose. The course in one box Who takes it: computer science and computer engineering students, usually in the second year. What it's for: showing what a processor physically does with your program, so that you can predict why some code is fast and some is slow. Comes after: Programming Fundamentals (34/09) and Discrete Mathematics (34/08). Leads to: Operating Systems (34/26), then Computer Networks (34/27) and Computer Security (34/33); it also quietly underlies Algorithms (34/24) and Programming Languages & Compilers (34/30). Honest line: you won't be able to design a chip after this piece. You will see why a loop over a table is fast one way and slow the other, and why your phone has eight cores and not one 20 GHz core. For a gentler first read on the history, see Processors: How a CPU Thinks (29/11); this piece goes into the mechanisms. GPUs (29/12) tells the graphics-chip story that appears here only as a single idea. Everything is a pattern of bits A bit is a wire that is either low or high. Eight of them in a row make a byte, and the meaning of the pattern lives in how you read it, not in the wire. The same eight bits can be a small number, a negative number, a letter or the colour of a pixel. Read as a plain number, each position counts double the one to its right: 1, 2, 4, 8 and so on. Negative numbers use two's complement: the leftmost bit counts as minus its weight instead of plus. In eight bits that makes the top bit worth −128, so 1111 1111 is −128 + 127 = −1. value = Σ bitk × 2k    (top bit counts as −27 in two's complement) Interactive · Flip the bits Add 1Flip all (NOT)Clear Tap to make 0111 1111 (127), then press Add 1. The answer is −128. The hardware did nothing wrong: the counter ran out of room and wrapped, the way a car odometer rolls over. Programs that forget this have real bugs, and a 64-bit register simply moves the cliff a long way off: it holds 264, about 1.8 × 1019, different patterns. Gates add numbers Adding is the first thing a processor learns to do with bits, and it needs no new idea. Add two bits and you get a sum bit and a carry bit. The sum is 1 when exactly one input is 1 (an XOR gate); the carry is 1 when both are (an AND gate). Chain one such unit per column, passing each carry into the next column, and you have a ripple-carry adder. sum = A ⊕ B ⊕ carry-in   ·   carry-out = (A · B) + (carry-in · (A ⊕ B)) Interactive · A clickable adder Tap the A and B bits. Watch the carry travel left, one gate stage at a time. Each column is a full adder: five gates (two XOR, two AND, one OR). Sixty-four columns need 64 × 5 = 320 gates. Try 0111 + 0001: the carry ripples through three columns before the answer settles at 1000. The carry's path through each column is two gates long, so a 64-bit ripple adder has a path of 128 gate delays, which is slow. Real processors use carry-lookahead and cleverer variants that compute many carries at once, trading more gates for less waiting. That trade (spend hardware, save time) comes back in every idea below. Subtraction costs almost nothing extra. To compute A − B, flip every bit of B and add 1 (that is two's complement negation), and use the same adder. One circuit does both. Multiplication, comparison and the rest of the arithmetic unit are built in the same way, from the same few gates. A program is numbers in memory: the instruction set The processor's loop is short enough to say in four steps. Fetch the instruction whose address is in the program counter. Decode it: which operation, which registers. Execute it in the arithmetic unit, memory or branch logic. Write back the result and move the counter on. Then repeat, billions of times a second. If you want to watch that loop run, the toy CPU in Processors (29/11) steps through it. Here is the part that is easy to miss: the instruction itself is just a number. The list of instructions a chip understands, and how each is written as bits, is its instruction set architecture (ISA). It is the contract between hardware and software: x86-64 (most PCs and servers), ARM (most phones) and RISC-V (open and growing) are different contracts. A register is one of a small number of named slots inside the core, typically 16 to 32 general ones, that instructions read and write directly. Registers are the fastest storage there is, and the compiler's main job is to keep the hot values in them. Interactive · Hand-assemble a RISC-V instruction Result into x  from x  and x With the defaults, add x5, x6, x7 ("put x6 + x7 into x5") becomes the 32-bit pattern whose hex is 0x007302B3. The fields are fixed-width slices: a 7-bit opcode, three 5-bit register numbers, and 10 bits that pick which arithmetic. Because the fields are always in the same place, decoding is mostly wiring, not thinking. That regularity is the RISC idea: keep instructions simple and uniform so the hardware can be fast. x86 instead has instructions from 1 to 15 bytes long and decodes them into simpler internal steps first. Both work; they are different bets. Memory is a hierarchy, and distance is time Fast memory is small and expensive; big memory is slow and cheap. So computers stack them. A few registers, then a small L1 cache, bigger and slower L2 and L3 caches, then main memory (RAM), then an SSD or hard disk. Each level holds copies of the most recently used pieces of the level below. Numbers make the gap real. Here are measured latencies on one desktop chip (an Intel Core i7-6700 at 4.0 GHz), with the disk figures from the widely quoted "latency numbers" list. The last column scales one clock tick to one second so the gaps are human-sized. LevelTimeTicks at 4 GHzIf a tick were 1 s L1 cache1 ns44 seconds L2 cache3 ns1212 seconds L3 cache10.5 ns4242 seconds Main memory~62 ns~250about 4 minutes SSD random read (2012-era figure)150 µs600,000about 7 days Hard-disk seek10 ms40,000,000about 1.3 years Caches work because programs are lazy in a predictable way: after touching a byte they usually touch its neighbours (spatial locality) and touch the same byte again soon (temporal locality). A cache therefore never loads one byte; it loads a whole line of 64 bytes. The rule a graduate remembers is the average-time formula, with hits cheap and misses expensive: average access time = hit time + miss rate × miss penalty Worked: with a 1 ns hit and a 62 ns miss, a 1% miss rate averages 1 + 0.01 × 62 ≈ 1.6 ns; a 10% miss rate averages about 7.2 ns, more than four times worse. The following simulator makes the point with real code. A 32 × 32 table of 4-byte numbers sits in memory row after row. Sum it in two orders. Interactive · Break the cache Cache size (64-byte lines) Red = miss, green = hit. Simplified: a direct-mapped cache (each line has exactly one possible slot), no prefetcher, hit 1 ns, miss 62 ns. Real caches are set-associative and prefetch, which softens these cliffs but does not remove them. Row by row, only 64 of the 1,024 accesses miss, because one load brings in 16 numbers. Column by column with 64 lines it is the same 64, but with 32 or fewer lines it collapses to 1,024 misses out of 1,024 (the two halves of the table fight for the same slots) and the run is roughly thirteen times slower. Same arithmetic, same answer. Choose "In 8×8 tiles" and even a 16-line cache gets back to 64 misses, because each small block of the table is finished while it is still cached. This is why programmers who know architecture tile their loops, and why linked lists scattered around memory lose to arrays. Pipelining: an assembly line for instructions Doing one instruction fully before starting the next wastes the hardware, as if a laundromat ran one load through wash, dry and fold before touching the next. A pipeline overlaps them. The textbook design has five stages: fetch, decode, execute, memory, write-back. When the line is full, one instruction finishes per tick even though each takes five. cycles ≈ instructions + (stages − 1) + stall cycles For 100 instructions that is about 104 ticks instead of 500: nearly a 5× gain from the same parts. The catch is hazards. If an instruction needs a result the one ahead of it hasn't finished, the line must wait, and the empty slot is called a bubble. A branch is worse: until the processor knows which way it goes, it guesses (branch prediction) and starts fetching down that path. On a wrong guess the half-done work is thrown away, which on a modern deep pipeline costs roughly 15 to 20 ticks. Interactive · Bubbles in the pipeline A hazard hits every Each hazard costs Blue = the instruction is in a stage (F D X M W), red = a bubble. First 8 instructions drawn; the numbers use 100. Slide the cost to 2 ticks every 4th instruction: the 100 instructions take 152 ticks, about 1.5 ticks each, and the gain over no pipeline falls from nearly 5× to about 3.3×. Push the cost to 16 ticks, like a mispredicted branch, and a hazard every 12th instruction cuts the gain to about 2.2×. That is why predictors are among the most elaborate parts of a modern core. Parallelism helps, up to the part you can't split When one core can't go faster, use more of them. Four cores can run four programs at once, or one program split in four. The limit was written down by Gene Amdahl in 1967: whatever part of the job must run in sequence caps the gain, however many workers you add. In its usual form, with p the fraction of the work that can be parallelised and N the number of cores: speedup = 1 ÷ ( (1 − p) + p ÷ N ) Interactive · Amdahl's wall Fraction that can run in parallel With 95% parallel work, 16 cores give 9.1×, not 16×, and no number of cores can ever beat 20×, because the 5% serial part is still there. Even at 99.9% parallel, 1,024 cores give only about 506×. A GPU is the extreme version of the bet: thousands of simple lanes running the same instruction on different data. It shines on graphics and matrix maths, where p is nearly 1, and is poor at code full of branches and dependencies. See GPUs (29/12) for how that bet turned into the AI hardware industry. Amdahl's pessimism has a famous rebuttal (Gustafson, 1988): bigger machines are usually given bigger problems, which keeps p high. Both are true, in different jobs. The power wall: why the clock stopped Every time a transistor switches it charges and discharges a tiny capacitor, which burns energy. Add up billions of them, thousands of millions of times a second, and you get heat that has to leave a chip the size of a postage stamp. The dynamic power of a chip is: P ≈ C × V2 × f Capacitance, voltage squared, frequency. For decades, shrinking transistors cut C and V so fast that you could raise f for free in power-per-area terms: this is Dennard scaling, from a 1974 paper by Robert Dennard and colleagues. Around 2005 to 2007 it broke, because leakage current and the threshold voltage stopped shrinking with the transistor, so voltage could no longer fall. Intel's Prescott Pentium 4 already drew up to 103 watts, and on 7 May 2004 Intel cancelled its successors, Tejas and Jayhawk, and pivoted to dual-core. Herb Sutter's 2005 article "The Free Lunch Is Over" told software developers what followed: programs would stop getting faster for free and would have to use several cores. Interactive · Spend your power budget Clock speed per core Number of cores Model: voltage rises in proportion to clock speed, so one core's power grows as the cube of the clock; throughput assumes perfectly parallel work (see Amdahl above). Power 1.0 = one core at 3 GHz. Real chips can't lower voltage below a floor, so the cube law flattens at low clocks. Under that model, doubling the clock from 3 to 6 GHz needs 23 = 8 times the power. Two cores at 3 GHz give the same ideal throughput for 2 times the power, and four cores at 1.5 GHz for half a unit. The modern chip is the answer: many modest cores, some specialised units, and parts switched off when idle, because a chip can now hold more transistors than it can power at once. What a graduate just sees Bits have no meaning until you choose how to read them; overflow is the odometer rolling over. Arithmetic is a few gates, and the slow part of an adder is the carry travelling across it. An instruction is a number, and a program is a list of them in memory. Distance is time: a trip to RAM costs hundreds of ticks, so access patterns matter more than operation counts. Walking memory in order is nearly free; jumping around it is not. A pipeline is full only if the code lets it be, and every branch is a bet. More cores help only as far as the work can be split (Amdahl). Power rises with the square of voltage and the cube of speed, so wide and slow beats narrow and fast. Where it shows up next Operating Systems (34/26) rests on hardware features introduced here: interrupts, the user/kernel privilege split, and the address-translation hardware behind virtual memory. Computer Security (34/33): the Spectre and Meltdown flaws, disclosed in January 2018, came from speculative execution (the guessing described under pipelining) leaking data through the cache. Algorithms (34/24) and Data Structures (34/23): two algorithms with the same operation count can differ tenfold in speed because of locality. Compilers (34/30): a compiler's whole output is instructions in one ISA, and its hardest job is choosing registers. Machine Learning (34/32): training is matrix multiplication on GPUs and similar chips, where Amdahl's p is nearly 1. If you want to go deeper 📘 Textbook: David Patterson and John Hennessy, Computer Organization and Design: RISC-V Edition (2nd ed., 2020). The standard first course; builds a processor step by step. 📘 Textbook: Hennessy and Patterson, Computer Architecture: A Quantitative Approach (7th ed., late 2025, with Christos Kozyrakis). The graduate-level reference for caches, parallelism and accelerators. 📘 Programmer's view: Randal Bryant and David O'Hallaron, Computer Systems: A Programmer's Perspective (3rd ed.). Best for locality and for how code becomes machine instructions. 📘 Gentler: Charles Petzold, Code: The Hidden Language of Computer Hardware and Software (2nd ed., 2022). Builds from a flashlight signal to a CPU with no maths beyond arithmetic. 🌐 Free, hands-on: Nand2Tetris (Nisan and Schocken, The Elements of Computing Systems): build a working computer from a NAND gate up, free in a non-profit setting. 🌐 Free course: MIT OpenCourseWare 6.004 Computation Structures (Spring 2017): lectures and problem sets from gates to a pipelined processor. The takeaway A processor is gates arranged to follow a list of numbers, and almost all of its cleverness goes into hiding two limits: memory is hundreds of ticks away, and power grows with the cube of speed. Caches, pipelines and extra cores are three ways of spending transistors to hide them, each with a cliff (misses, hazards, the serial fraction). Try this: write a loop that sums a big two-dimensional array (a spreadsheet-sized grid in Python with NumPy, or any language), once row by row and once column by column, and time both. The gap you find is the memory hierarchy. Sources & Further Reading Sources. Cache and memory latencies for the i7-6700 (4.0 GHz): 7-cpu.com, "Intel Core i7-6700 Skylake"; disk and SSD figures: the "Latency Numbers Every Programmer Should Know" list (Jeff Dean's figures as circulated, c. 2012). Dennard scaling and the power wall: Dennard et al., IEEE JSSC (1974); Wikipedia, "Dennard scaling". Tejas and Jayhawk cancellation (7 May 2004) and Prescott power: The Register, EE Times and Wikipedia, "Tejas and Jayhawk"; Pentium 4 top speed 3.8 GHz and cancelled 4 GHz part: Wikipedia, "Pentium 4". Branch mispredict penalty of 15 to 20 cycles (Skylake): Agner Fog's measurements as cited by Chips and Cheese. Sutter, "The Free Lunch Is Over", Dr. Dobb's Journal 30(3), March 2005. Amdahl, AFIPS Spring Joint Computer Conference (1967); Gustafson, Communications of the ACM (1988). RISC-V R-type encoding: The RISC-V Instruction Set Manual, Volume I. All interactive numbers were recomputed in code. 🌐 nand2tetris.org 🌐 MIT OpenCourseWare: 6.004 Computation Structures 🌐 Herb Sutter: The Free Lunch Is Over 📘 Code, Charles Petzold (Microsoft Press, 2nd ed., 2022) Step 7. Linear Algebra: Machines That Move Space ------------------------------------------------ Why: Graphics, search engines and AI are linear algebra underneath. A grid of numbers is really a machine that moves all of space at once. Learn to see it, and circuits, bridges, search engines and AI all start to look alike. You pinch two fingers on a photo and it rotates and zooms smoothly under them. A game character turns to face you and every corner of its face swings round together. A search for "best pizza near me" ranks millions of pages in a fraction of a second. A bridge designer presses "solve" and a screen of colour shows how every beam is being squeezed. Underneath all four is the same object: a grid of numbers, and one habit of thought about what a grid of numbers does. A graduate of a linear algebra course no longer sees a table of numbers. They see a machine that grabs the whole plane, or the whole of space, and moves it. This piece builds that picture with seven things you can drag. You will not come out able to compute a determinant of a 5×5 by hand (nobody does that on purpose). You will come out seeing why a system of equations sometimes has no answer, why a bridge hums at particular pitches, and why the chips that run AI are built for one operation only. The course in one box Who takes it: nearly every engineering and computer science student, usually in the first or second year. It is the single most reused maths course in both majors. What it's for: handling many unknowns and many dimensions at once, with one set of tools. Comes after: only school algebra and a little geometry. (Calculus helps but is not required.) Leads to: Statics (34/10), Control Systems (34/20) and Machine Learning (34/32) list it as a prerequisite; Vibrations (34/17), Computer Architecture (34/25) and Multivariable Calculus (34/02) lean on it constantly. Honest line: you won't be able to run a finite element program after this piece. You will see why it spends nearly all its time solving one equation, Ax = b. If you want an easier first read, try the library's Vectors, Matrices and Linear Transformation (12/14); this one goes further into solving, eigenvectors, fitting and why hardware cares. A matrix moves all of space at once Start with the picture a graduate keeps. A 2×2 matrix is not four numbers. It is two arrows. The first column says where the arrow pointing one step right (call it i) ends up. The second column says where the arrow pointing one step up (j) ends up. Once you know where those two land, you know where everything lands, because every point is some amount of i plus some amount of j, and the machine is straight and even: grid lines stay straight, and evenly spaced lines stay evenly spaced. Ax = x1(column 1) + x2(column 2) Read that in words: the matrix times a point is "that many of the first column, plus that many of the second". Try it. The grey grid is the original plane; the blue grid is where the matrix sends it. Interactive · Move the plane Do nothing Rotate 30° Stretch Shear Mirror Column 1, right part (a) Column 2, right part (b) Column 1, up part (c) Column 2, up part (d) Without JavaScript: the rotate-30° matrix sends the arrow (1, 0) to (0.87, 0.5) and (0, 1) to (−0.5, 0.87). Every grid line turns 30° and the unit square keeps area 1. Notice what the shaded unit square does. In "Rotate" it keeps its size. In "Stretch" it doubles. In "Shear" it leans over but keeps its area. That area change is the next idea. The determinant is how much area gets scaled The determinant is one number that says how much the machine scales area. If the unit square becomes a shape with area 5, the determinant is 5. If it becomes a mirror image, the determinant is negative: area is kept (or scaled) but orientation is flipped. For a 2×2 matrix with columns (a, c) and (b, d) the rule is short: det = ad − bc Worked number: the matrix with columns (2, 1) and (1, 3) has det = 2×3 − 1×1 = 5, so it stretches every area in the plane by a factor of five. In three dimensions the determinant scales volume. The interesting case is zero. A determinant of zero means the machine flattens space: the plane is squashed onto a line (or a point), and the area becomes nothing. Squashing cannot be undone, because many different starting points land on the same spot. Drag the slider until the determinant reaches zero. Interactive · Squash the plane flat Tilt the second arrow: s Without JavaScript: the matrix with columns (1, 0.5) and (s, 1) has determinant 1 − 0.5s. At s = 2 the determinant is 0, the whole plane lands on one line, and the points (0, 0) and (2, −1) both land on the origin. The orange dot is a probe at (2, −1). At s = 2 it lands exactly on the origin, the same place as the point (0, 0). Two different inputs, one output: no machine could tell you which one you started from. That is the whole meaning of "this matrix has no inverse", and it is why a zero determinant is the alarm bell in every solver you will ever meet. Solving many equations at once: Ax = b Now use the machine backwards. Given the output b, which input x did the machine start from? That is the equation Ax = b, and it is the most common problem in applied mathematics. Every time you have several unknowns that are tied together by several straight-line relationships, you have one. A circuit is the cleanest example. Two loops share a resistor. Kirchhoff's voltage law says the voltage gained around each loop equals the voltage lost, which gives one equation per loop. With a 10 V battery, R1 = 2 Ω, R2 = 3 Ω (shared) and R3 = 4 Ω: 5I1 − 3I2 = 10−3I1 + 7I2 = 0 The determinant is 5×7 − 3×3 = 26, so there is exactly one answer: I1 = 2.69 A and I2 = 1.15 A. Change the resistors below and watch the matrix and the answer change together. Interactive · Solve a circuit with a matrix Battery V R1 (loop 1 only) R2 (shared) R3 (loop 2 only) Without JavaScript: with 10 V, 2 Ω, 3 Ω and 4 Ω the equations are 5I1 − 3I2 = 10 and −3I1 + 7I2 = 0, its determinant is 26, and the loop currents are 2.69 A and 1.15 A. The reason an engineer cares: nothing about this method knows it is a circuit. A truss is the same. At each joint of a bridge, the horizontal forces must add to zero and so must the vertical ones: two equations per joint. A simple triangle truss has three joints and so six equations, for three member forces and three support reactions, and the answer is one solve of Ax = b. A real structure has thousands of joints. Finite element programs routinely solve systems of many thousands of equations, and research codes have reported solving over a million unknowns at once. The method is the same one you just used; only the size has changed. (Statics, 34/10, is this idea applied to forces.) A zero determinant in a structure's equations is a warning: the structure may be able to move without any member pushing back. Eigenvectors: the directions a transformation only stretches Most arrows are turned by a matrix as well as stretched. But for many matrices there are special directions where the arrow comes out pointing the same way (or exactly backwards), only longer or shorter. Those are the eigenvectors, and the stretch factor along each is its eigenvalue. (Eigen is German for "own": the matrix's own directions.) Av = λv In words: feed the matrix the special arrow v and it hands back the same arrow multiplied by a plain number λ. For the matrix with columns (2, 1) and (1, 2) the special directions are 45° (stretched by 3) and 135° (stretched by 1). Every other arrow gets bent towards the stretchy one. Turn the dial and look for the moments the two arrows line up. Interactive · Find the directions that only stretch Stretch & mix Shear Rotation Two springs Direction of the input arrow Without JavaScript: for the matrix with columns (2, 1) and (1, 2), an arrow at 45° comes out at 45° three times longer, and an arrow at 135° comes out at 135° unchanged. A pure rotation has no such direction at all. Three things to notice. The shear has only one special direction (along the x-axis, where nothing happens at all). The rotation has none, because every arrow turns. And "Two springs" has two special directions with different stretch factors, 1 and 3; hold that thought. Eigenvectors at work: bridges that hum, pages that rank Vibration. Picture two equal masses on springs between two walls. Push them any way you like and the motion looks messy. But there are exactly two clean patterns: both swing together, or they swing in opposite directions. These are the modes, and they are the eigenvectors of the "two springs" matrix above, (1, 1) and (1, −1). The eigenvalues 1 and 3 fix how fast each mode vibrates: the squared frequency is the eigenvalue times k/m, so the opposite-motion mode vibrates √3 ≈ 1.73 times faster. Any messy motion is just a mix of the modes. That is how engineers find which pitches will shake a wing, a bridge deck or a drive shaft (Vibrations, 34/17). Ranking pages. Google's founders modelled a web surfer who follows a random link from each page, and now and then jumps to a random page instead. The long-run share of time spent on each page is its PageRank, and it is the eigenvector (with eigenvalue 1) of the matrix describing one step of that surfer. In their 1998 paper Brin and Page used a "damping" probability of 0.85 for following links. You can find the eigenvector without solving anything fancy: start with equal scores and apply the machine over and over. Press Step. Interactive · A four-page web finds its eigenvector Step onceRun 20 stepsReset Without JavaScript: A links to B and C, B links to C, C links to A, D links to C. After many steps with damping 0.85 the ranks settle to A 0.373, B 0.196, C 0.394, D 0.038. D, which nobody links to, keeps only the base share. After about twenty steps the numbers stop changing: the vector has become an eigenvector, because applying the machine again returns the same vector. Page C wins because two pages point at it and one of them (A) is itself well-ranked. Least squares: the best answer when there is no exact one Real data is never perfect. Six measurements that "should" lie on a straight line will not, so the equations Ax = b have more equations than unknowns and no exact solution. Do you give up? No. You choose the line whose total mistake is smallest. Measure each miss vertically, square it, and add up the squares. The least squares line makes that total as small as possible. In pictures: each squared miss is literally a square. Drag the line and watch the squares shrink and grow. Interactive · Make the squares as small as possible Slope Height at x = 0 Snap to the least-squares line Without JavaScript: for the six points (1, 1.2), (2, 2.9), (3, 3.1), (4, 4.8), (5, 5.2), (6, 7.1) the best line is y = 1.089x + 0.24, with total squared miss 0.798. The guess y = x gives 2.75. The graduate's picture is geometric: the right-hand side b is a point outside the flat sheet of everything the matrix can reach, and the best answer is the point on the sheet closest to it, found by dropping a perpendicular. That perpendicular condition gives the one equation to remember: ATA x̂ = ATb In words: multiply both sides by the matrix flipped on its side and you get a square system you can solve. The history is a priority fight: Legendre published the method in 1805, Gauss said he had used it since 1795 and published in 1809, and Gauss's use of it to predict where the asteroid Ceres would reappear in 1801 made it famous. Today it sits under every trend line, every calibration of a sensor, and the first model most machine-learning students ever train. Why GPUs and AI are matrix multiplication Multiplying two matrices is just many dot products: every cell of the answer is one row of the first matrix paired with one column of the second, multiplied and added. Click a cell below and see the row and column that make it. Interactive · Build a product cell by cell Tap a cell of C = A × B. Matrix size n (n × n times n × n) 1 billion multiplies per second 100 billion per second 10 trillion per second The speeds are round illustrative numbers, not any particular chip. Without JavaScript: multiplying two n×n matrices takes n×n×n multiplications. For n = 1,000 that is 1,000,000,000, and the 1,000,000 cells of the answer can all be computed independently. Two facts follow. First, the work is huge: n×n matrices need n³ multiplications, so 1,000×1,000 is a billion. Second, the cells are independent, so a thousand workers (or a million) can each take cells at the same time. That is exactly the shape of work a graphics chip was built for, because drawing a 3D scene means pushing every corner of every triangle through a matrix that rotates, moves and projects it. Modern neural networks turned out to be the same shape. A layer of a network is a matrix of learned numbers times a vector (or a matrix) of inputs. In their scaling-law paper, Kaplan and colleagues estimate that a transformer language model with N parameters needs roughly 2N arithmetic operations to process one token. GPT-3, with 175 billion parameters, therefore needs about 3.5×1011 operations for each token, nearly all of them inside matrix products. NVIDIA's Volta GPUs (2017) put dedicated "tensor core" circuits on the chip that do nothing but a small matrix multiply-and-add (4×4) per clock tick. When people say AI runs on GPUs, they mean it runs on hardware shaped like linear algebra. (Computer Architecture, 34/25, and Machine Learning, 34/32.) What a graduate just sees A matrix is a machine that moves all of space; its columns say where the basis arrows go. The determinant is the area (or volume) scale factor, and zero means the machine flattens space and cannot be undone. "Solve Ax = b" is the same question for a circuit, a truss, a fitted line and a game physics step. If there are as many independent equations as unknowns there is one answer; fewer, many answers; contradictory, none. Eigenvectors are the directions a machine only stretches; they simplify any problem the machine drives. A vibrating structure is a mix of modes, one per eigenvector; the eigenvalues are the pitches. When there is no exact answer, take the closest one: project onto what you can reach. Matrix multiplication is many independent dot products, which is why it parallelises and why hardware is built around it. Where it shows up next Statics (34/10) and Mechanics of Materials (34/11): joint and member forces are a linear system; stiffness matrices tie loads to deflections. Vibrations (34/17) and Dynamics (34/12): mode shapes and natural frequencies are eigenvectors and eigenvalues of mass and stiffness matrices. Control Systems (34/20): the eigenvalues of a system's matrix say whether a drone's wobble dies away or grows. Machine Learning (34/32): data is a matrix, a layer is a matrix, and training adjusts matrices; least squares is the model you meet first. Computer Architecture (34/25) and graphics: GPUs and tensor cores exist to multiply matrices fast. If you want to go deeper 📘 Gilbert Strang, Introduction to Linear Algebra (Wellesley-Cambridge Press; 6th edition, 2023). The standard first course for engineers; best for the four fundamental subspaces and for application. 📘 David C. Lay, Steven R. Lay and Judi J. McDonald, Linear Algebra and Its Applications (Pearson; 6th edition, 2021). Gentle, example-heavy, widely assigned. For proofs, Sheldon Axler's Linear Algebra Done Right (Springer; 4th edition, free to read online at linear.axler.net) is the elegant theoretical route. ▶️ 3Blue1Brown, Essence of Linear Algebra: the best visual series for learning alone; it builds exactly the "matrix as moving space" picture used here. 🌐 MIT OpenCourseWare 18.06, Linear Algebra (Gilbert Strang): full video lectures, free. The takeaway Linear algebra is the study of machines that move all of space at once. Read a matrix by its columns, read its determinant as the area scale, solve Ax = b when you need to run the machine backwards, look for the eigenvector directions when you want it to be simple, and project onto what you can reach when there is no exact answer. Try this: next time an app zooms, rotates or recolours a photo, picture the two column arrows moving. And for the fun of it, in the circuit widget raise R2 to 10: the shared resistor starts to decide what both loops do. Sources & Further Reading Sources. Strang, Introduction to Linear Algebra (6th ed., 2023) and MIT 18.06 for the standard course content. Kirchhoff loop equations and the spring-mass modes are textbook derivations; every number above was recomputed in code. Legendre's 1805 publication and Gauss's priority claim and Ceres prediction: Wikipedia, "Least squares"; MacTutor biography of Legendre. PageRank and the 0.85 damping factor: Brin and Page, "The Anatomy of a Large-Scale Hypertextual Web Search Engine" (1998). Volta tensor cores (4×4 matrix multiply-accumulate): Markidis et al., "NVIDIA Tensor Core Programmability, Performance & Precision" (2018). About 2N operations per token: Kaplan et al., "Scaling Laws for Neural Language Models" (2020); GPT-3 at 175 billion parameters: Brown et al. (2020). Million-unknown structural solves: NASA Technical Reports Server and OSTI conference papers on parallel sparse solvers. Go deeper. The books and courses above. Step 8. Probability & Statistics: Reasoning with Uncertainty ------------------------------------------------------------ Why: Randomness, data and uncertainty, which every real system deals with. Nothing you measure is exact, and no part comes out the same twice. Statistics is the discipline of knowing how much to trust a number. A machinist turns a hundred steel shafts to "10 millimetres". Measure them with a good micrometer and no two are the same: 9.981, 10.012, 10.004. Nothing is wrong. That scatter is a fact of every process, every material and every sensor. Now stack five of those parts end to end in a gearbox. Will the stack still fit the housing? A pollster calls a thousand people and says 52% will vote yes, give or take three. A drug trial says "significant". A forecast says 30% chance of rain. Every one of these is the same question: given scatter, how much should I trust this number? A graduate of probability and statistics doesn't see a single number any more. They see the shape of the scatter behind it. This piece builds that sight with eight things you can run: dice, tolerances, polls, a drug-trial trap, a belief that updates, and a gearbox stack. The course in one box Who takes it: almost every engineering and science student, usually in the second year; computer scientists meet it again before machine learning. What it's for: deciding what to believe, and how far to trust a measurement, when outcomes are uncertain. Comes after: Calculus I (34/01), which helps with continuous distributions, though the ideas here need little more than arithmetic. Leads to: Machine Learning (34/32) needs it directly. It also shows up in Materials Science & Manufacturing (34/13: process control and defects), Systems Engineering (34/22: reliability) and Computer Security (34/33: randomness and guessing). Honest line: you won't be able to design a clinical trial after this. You will see why "significant" doesn't mean "important", why a bigger sample beats a cleverer guess, and why most real quantities look like a bell curve. For easier first reads, see the library's Probability: How to Not Fool Yourself (12/03), Statistics for Reading the World (12/05) and Bayes' Theorem (12/17); this piece goes further into the engineering side. Random variables: a shape with a centre and a spread A random variable is a number that comes out of a process you can't predict one run at a time. The key move is to stop asking "what will it be?" and ask "what is the shape of what it could be?" Roll two dice and add them: 7 is six times as likely as 2 or 12, so the shape is a tent. Roll many times and the tent appears. Interactive · Roll dice, grow a shape Dice added together Roll 10 timesRoll 1,000 timesClear Without JavaScript: two dice add to 7 with probability 6/36 and to 2 or 12 with probability 1/36 each. The mean total is 7 and the standard deviation is about 2.42. Two numbers summarise a shape. The mean is its balance point: 7 for two dice. The standard deviation (the "spread") says how far values typically stray from the mean: about 2.4 for two dice, which means totals usually land between roughly 5 and 9. The variance is the standard deviation squared, and it is the one that adds up neatly when you combine independent things. standard deviation = √( average of (value − mean)² ) Now the shape that matters most. Measured quantities (shaft diameters, heights, sensor noise) tend to form the normal curve, the bell. Its great convenience is a fixed rule: about 68.3% of values fall within one standard deviation of the mean, 95.4% within two, and 99.7% within three. Engineers use it every day. Say the shaft's spec is 10.00 mm ± 0.05 mm. Slide the process around and see what share of parts get thrown away. Interactive · How many parts fail the spec? Average diameter Spread (standard deviation) Without JavaScript: a centred process with standard deviation 0.025 mm (the spec limits are exactly ±2 standard deviations) scraps about 4.55% of parts. Cut the spread to 0.01 mm and about 0.00006% are scrapped. Shift the average 0.02 mm off-centre with spread 0.02 mm and about 6.7% are scrapped. Two lessons graduates keep. First, spread, not average, decides quality: a process centred perfectly but wide still scraps parts. Second, being off-centre costs a lot even when the spread is fine. That is why factories track both. The central limit theorem: why the bell keeps appearing Why should so many things be bell-shaped? The answer is one of the most useful theorems in mathematics. Take almost any random process, however lopsided, and average a few dozen independent draws. The averages pile up in a bell, centred on the true mean, with spread shrinking like 1/√n. Early forms are due to de Moivre in 1733 (for coin flips) and Laplace, whose general version dates from about 1810. Pick a lopsided source and drag the sample size. Interactive · Average anything, get a bell Flat (0 to 1) Very lopsided Coin (0 or 1) Draws averaged together: n Without JavaScript: for the lopsided source (mean 1, standard deviation 1) the average of n = 30 draws has standard deviation 1/√30 = 0.183, and the 3,000 averages form a close-to-normal bell around 1. At n = 1 you see the raw source. By n = 30 even the lopsided one is a near-bell. The prediction (the curve) uses only two numbers from the source, its mean and its standard deviation. The shape of the source is forgotten. That is why a measurement made of many small independent errors is normal, and why so much of statistics can pretend things are bell-shaped. standard error of an average = σ / √n In words: the average of n draws wobbles less than one draw, by the square root of n. To halve the wobble you need four times the data, not twice. It is the quietest expensive fact in all of experimental science. Sampling and confidence intervals: how sure is a poll? You can't ask everyone, so you ask n people and treat the share saying yes as an estimate. How far off might it be? The standard error from the last section gives the answer. For a share p the wobble is √(p(1−p)/n), and a 95% confidence interval is the estimate plus and minus about two of those. For n = 1,000 and a share near half, that is ±3.1 percentage points: the familiar "margin of error". The wording is subtle, and the interactive makes it concrete. "95% confidence" is a statement about the method, not about one interval: if you ran the procedure again and again, about 95 intervals in 100 would capture the true value. Here the truth is secretly 52%. Run 100 polls. Interactive · 100 polls, one truth People asked in each poll Run 100 polls Without JavaScript: with 1,000 people per poll the margin of error is about 3.1 points; run 100 polls and about 95 of the intervals cover the true value. With 4,000 people the margin halves to about 1.5 points. Watch two things. Roughly five in a hundred intervals miss the truth even when everything is done correctly. And quadrupling the sample from 1,000 to 4,000 only halves the interval. A poll of a country and a poll of a town need the same sample size for the same precision, as long as the sample is random. The real danger is not the margin of error; it is a sample that isn't random at all, which no formula fixes. P-values and Bayes: two ways to weigh evidence A hypothesis test asks whether data are surprising if nothing is going on. The p-value is the probability, assuming nothing is going on, of seeing a result at least as extreme as yours. Flip a coin 100 times and get 60 heads: for a fair coin the chance of a split at least that lopsided in either direction is about 5.7%. It is not the probability that the coin is fair, and it is not the probability that the result was "due to chance". The American Statistical Association issued a rare formal statement on this in 2016, with six principles. Two of them: p-values do not measure the probability that a hypothesis is true, and a p-value does not measure the size or importance of an effect. The classic trap is testing many things. At the usual cut-off of 0.05, a test of a true "nothing" comes out "significant" one time in 20 by luck. Test twenty unrelated things and the chance that at least one lights up is 1 − 0.9520, about 64%. Try it: each press tests twenty effects that are, by construction, nothing. Interactive · Test twenty things that do nothing Run 20 testsReset the tally Without JavaScript: twenty tests of pure noise at the 0.05 level give at least one false "discovery" about 64% of the time, and one in 20 tests on average. If you report only the one that lit up, you have a headline and no finding. This is part of why many published results fail to repeat: in the Open Science Collaboration's 2015 attempt to replicate 100 psychology studies, 97% of the originals had statistically significant results but only 36% of the replications did. Bayes' rule answers a different question: given the data, how should my belief move? Start with a prior belief, multiply by how well each possibility explains the data, and renormalise. Say you test parts and want the defect rate. Know nothing at first (any rate from 0% to 100% equally likely) and add parts one at a time. Interactive · Learn a defect rate from parts Add a good partAdd 10 good partsAdd a defective partReset Without JavaScript: after 20 good parts and no defects, a flat starting belief gives a most-plausible defect rate near 0%, an average of 4.5%, and a 90% credible range of roughly a quarter of a percent to 13%. Twenty clean parts cannot rule out a defect rate near one in eight. Frequentists and Bayesians disagree about the philosophy: one treats probability as long-run frequency and never assigns it to a hypothesis, the other as degrees of belief that data update. In practice both are used, often on the same project, and on big data sets they usually agree. The Bayesian version has one practical advantage here: after twenty clean parts it honestly says "we still can't rule out one in eight". Correlation, regression and the trap of causation Correlation (called r) measures how tightly two quantities move together along a straight line, from −1 to +1. Regression fits the best line through the cloud (by least squares, as in Linear Algebra, 34/04). Both are summaries, and any summary can hide the story. In 1973 the statistician Francis Anscombe made four data sets with, to two decimals, the same mean, the same spread, the same r (0.82) and the same line (y = 3 + 0.5x). Look at each. Interactive · Four data sets, one set of numbers Set 1Set 2Set 3Set 4 Without JavaScript: all four Anscombe sets have mean x = 9, mean y = 7.50, correlation 0.816 and line y = 3.00 + 0.50x. Set 1 is a noisy line, set 2 a curve, set 3 a line with one outlier, and set 4 a single far point that creates the whole slope. The numbers agree and the stories do not: one noisy line, one curve, one line with a rogue point, one vertical stack held up by a single point. Always plot first. The other trap is the famous one. Ice-cream sales and drownings rise together, because summer heat drives both. A confounder (a hidden third factor) makes two things move together without either causing the other. The remedy graduates know is randomised assignment: if a coin decides who gets the treatment, nothing else can be systematically linked to it. Where you can't randomise, causal claims need much more than a line through a cloud. Engineering: tolerance stacks, reliability and Monte Carlo Five parts, each 10 mm ± 0.1 mm, line up in an assembly. What is the worst the total can be out? Worst-case stacking adds the tolerances: ±0.5 mm. It is safe and expensive, because it assumes every part is at its extreme in the same direction at once. If the parts vary independently, variances add, so the standard deviations add in quadrature: root-sum-square, √5 × 0.1 = ±0.224 mm. For five parts that is under half the worst-case figure. When the formulas get hard, engineers use Monte Carlo: let the computer build the assembly ten thousand times with random parts and count how often it fails. Here each part's tolerance is treated as three standard deviations. Choose how many parts are stacked. Interactive · Monte Carlo tolerance stack Parts in the stack Build 10,000 assemblies again Without JavaScript: five parts at ±0.1 mm (three standard deviations) give a worst-case limit of ±0.5 mm, a root-sum-square limit of ±0.224 mm, and in simulation only about 0.3% of assemblies exceed the root-sum-square limit; none come close to 0.5 mm. The honest caveat is that root-sum-square assumes the parts vary independently and are centred. A tool wearing in the same direction on every part breaks that assumption, and so does one supplier's batch. Engineers disagree about when to trust statistical stacking over worst-case; safety-critical designs often insist on worst-case. Reliability follows the same arithmetic. A system that needs all of its parts is a series system, and probabilities multiply: ten components that each work 99% of the time give 0.9910 ≈ 90.4% for the whole. Add a backup in parallel and failure needs both to fail: two units that each work 90% of the time give 1 − 0.1² = 99%. The two rules drive why aircraft duplicate systems and why complicated machines need very reliable components. What a graduate just sees Every number has a spread behind it; the first question is "how scattered?", not "what is it?". Spread, not the average, decides how many parts are scrapped, and centring matters too. Averages of many independent things are bell-shaped, whatever the source looked like. Halving the uncertainty costs four times the data. A 95% interval is a claim about a method: it misses one time in twenty by design. A p-value is "how surprising is this if nothing is going on", not "how likely is it true". Test twenty things and one will look significant; ask how many were tried. Plot the data; correlation is not causation, and only randomising breaks a confounder. Independent errors add in quadrature; series reliabilities multiply. Where it shows up next Machine Learning (34/32): training is fitting a model to noisy data; ideas of overfitting, error bars and Bayes are this course made bigger. Materials Science & Manufacturing (34/13): process capability and scrap rates are the normal curve against a spec limit. Mechanics of Materials (34/11) and Machine Design (34/19): safety factors exist because loads and strengths are distributions, not numbers. Systems Engineering (34/22): reliability budgets multiply series probabilities and add redundancy to push them back up. Computer Security (34/33) and Algorithms (34/24): good random numbers, randomised algorithms, and the odds of guessing a secret. If you want to go deeper 📘 Douglas Montgomery and George Runger, Applied Statistics and Probability for Engineers (Wiley; 7th edition). The standard engineering course text, with plenty of tolerance, quality and reliability problems. 📘 Joseph Blitzstein and Jessica Hwang, Introduction to Probability (CRC Press; 2nd edition, 2019). Best for deep intuition about probability itself, from Harvard's Stat 110. 📖 David Spiegelhalter, The Art of Statistics (2019): the most readable route for learning alone, built around real cases and honest about uncertainty. 🌐 MIT OpenCourseWare 18.05, Introduction to Probability and Statistics (Spring 2022): free notes and problem sets, with Bayesian and classical statistics side by side. The takeaway Nothing you measure is exact, so every number is a shape. Summarise a shape by its centre and its spread, trust averages more as the square root of the sample, read a confidence interval as a promise about a method, treat a p-value as a measure of surprise, and plot before you believe a correlation. Try this: next time you see a poll or a "significant" headline, find the sample size and ask how many things were tested. Then, in the dice widget above, add four dice and watch the tent turn into a bell. Sources & Further Reading Sources. The normal-curve rule (68.3%, 95.4%, 99.7%), the central limit theorem, confidence intervals, the binomial test, the Beta posterior, root-sum-square stacking and series/parallel reliability are standard textbook results (Montgomery and Runger; MIT 18.05); every number shown was recomputed in code. Wasserstein and Lazar, "The ASA's Statement on p-Values: Context, Process, and Purpose", The American Statistician (2016). Open Science Collaboration, "Estimating the reproducibility of psychological science", Science (2015): 97% of originals significant against 36% of replications. Anscombe, "Graphs in Statistical Analysis", The American Statistician (1973). Early forms of the central limit theorem: de Moivre (1733) and Laplace (c. 1810), as surveyed in recent histories such as Ulyanov, "From classical to modern central limit theorems" (arXiv 2405.19828). Go deeper. The books and course above; Wasserstein and Lazar's statement is free and short (doi.org/10.1080/00031305.2016.1154108). Step 9. Software Engineering: How Teams Change Code for Years ------------------------------------------------------------- Why: Real software is written by teams, over years; that changes everything. Real software is written by teams, over years. That changes everything: how you design, merge, test, estimate and learn from failure. You have never used the same app twice. The icon is the same, but last Tuesday it had a bug, on Wednesday somebody fixed it, and on Thursday a change meant for something else broke it again. Behind the single button you tap sits a team that has been changing the same code for years, often with nobody left who wrote the first version. Writing a program that works on your laptop is one skill. Keeping a program working while dozens of people change it for a decade is another, and it is mostly not about code. It is about arguments settled in advance: what the thing should do, who may change what, how you know a change is safe, and what you do at 3 a.m. when it isn't. That second skill is called software engineering. It is the one subject on the Computer Science map whose main material is people, time and mistakes. The course in one box Who takes it: computer science and software engineering students, usually in the second or third year; electrical and mechanical engineers often take a version because their products now contain software. What it is for: making software that many people can change safely over a long time. Comes after: Programming Fundamentals (34/09). Leads to: Systems Engineering & the Capstone (34/22), where software meets hardware; and it shapes how you work in Operating Systems (34/26), Databases (34/28) and Computer Security (34/33), since every real system there is a team project. What this piece gives you, and what it doesn't: you won't be able to run an engineering organisation after this. You will see why teams use version control, why a passing test suite proves less than you hope, and why every software schedule is wrong in the same direction. Software is built by teams, for years A student program is written once, by one person, and thrown away. A real program is read far more than it is written. Its first version may be a small part of its life; most of the work is changing it: new features, new phones, new laws, bugs nobody knew about. The people who change it did not write it. So the central problem is not "can I make the computer do this?" It is "can a stranger understand and safely change this next year?" This turns the usual priorities upside down. Clever code is a liability if only its author understands it. Plain names, small functions and clear structure are not decoration; they are how knowledge survives when people leave. Frederick Brooks, who managed the development of IBM's OS/360 in the 1960s, wrote the classic account of building such a system in The Mythical Man-Month (1975), and most of its observations are about people and communication rather than programming. Requirements, design and the art of hiding things Before code comes a question: what should it do? Requirements are the answer, and they are always incomplete, because users often don't know what they need until they see something working. Design is how you split the work so that people can build it in parallel. The key idea in design is abstraction: using something through a simple description without needing to know how it works inside. You drive a car without knowing the engine. A module is a chunk of code with a small, stable public face and a hidden inside. The classic paper is David Parnas's 1972 "On the Criteria to Be Used in Decomposing Systems into Modules". Its argument: don't cut a system into modules by the order of the steps it performs. Cut it so that each module hides one decision that is likely to change, such as how data is stored. Then, when that decision changes, only one module has to. Good design is deciding in advance what you will be able to change without telling anyone. Parnas's idea sits underneath nearly everything later: libraries, classes, services, even the interface idea in Systems Engineering (34/22). Brooks, who argued against the idea in 1975, later wrote in the 1995 edition of his own book that this was one of the few places he'd been wrong. Version control: many people, one history If five people edit the same files, how do you combine their work, and how do you undo a mistake from three weeks ago? Version control is the answer: a system that records every change, who made it and why, and lets people work in parallel on separate branches that are later merged. The dominant tool is Git, created by Linus Torvalds in April 2005 for the Linux kernel, after the proprietary tool the kernel team had used was no longer available to them. Every developer holds a complete copy of the history. Each commit is a snapshot of the whole project, identified by a hash of its contents and linked to the commit before it, so history cannot be quietly rewritten without everyone noticing. When two people changed the same file, Git merges line by line. If the changes are in different places, it just combines them. If they touch the same lines, or lines right next to each other, it stops and asks a human, by marking a conflict. Try it: pick lines for Alice and Bob to change. Interactive · Merge two people's work Starting file: a five-line recipe. Tap the lines each person changes. This follows Git's rule: separate changes combine, changes to the same or neighbouring lines conflict. Alice changes: Bob changes: With the starting choice (Alice edits line 1, Bob line 3) the merge is silent and clean. Move Bob to line 2 and Git, correctly, stops: it cannot know whether the title and the flour belong together. This is also why teams make small changes and merge often. Long-lived branches are where conflicts, and bad surprises, pile up. The testing pyramid, and what a passing test proves You cannot check by hand that a million-line program still works after every change, so teams write programs that test the program. There are three layers. Unit tests check one small piece in isolation and run in milliseconds. Integration tests check that pieces work together. End-to-end tests drive the whole product as a user would; they are the most realistic and the slowest and most fragile. The testing pyramid, popularised by Mike Cohn in his 2009 book Succeeding with Agile, says to have many tests at the bottom and few at the top, because the fast ones give quick, precise answers. The hard truth about tests is that a test only checks the inputs someone thought of. Here is a leap-year function with a bug: it says a year is a leap year if it divides by 4. Real rule: divisible by 4, except years divisible by 100, unless also divisible by 400. Interactive · Does your test suite catch the bug? Choose which years to test. The code runs for real, in your browser. function isLeap(year) { if (year % 4 !== 0) return false; return true; } The suite {2023, 2024} runs every line and every branch (100% coverage), and all tests pass. The bug is still there. Add 1900 and the test fails. Coverage tells you which code ran, not whether you asked the right questions. That is why engineers pair tests with code review, where a second person reads each change before it merges. Review catches design problems, spreads knowledge, and is the cheapest second pair of eyes a team has. Technical debt: borrowing against the future Ward Cunningham, who built the WyCash portfolio system, used a money metaphor in a 1992 conference report: shipping first-time code is like going into debt. A little speeds you up, provided you pay it back by cleaning up soon. If you don't, the interest piles up, because every later change has to work around the mess. He later said that he never meant the metaphor as a licence to write bad code on purpose. A toy model shows the shape. Each release has capacity for 10 units of work. Taking shortcuts delivers up to 40% more features now, but every release adds debt, and each unit of debt steals 3% of the capacity of every future release. You can spend a share of each release on paying the debt back. Interactive · Shortcuts and interest A toy model with the rules above, run over 20 releases. The line is features delivered so far. How hard you cut corners Share of each release spent paying debt With full shortcuts and no repayment you are ahead for the first eight releases, and behind from the ninth; by release 20 the careful team has delivered 200 units to your 132. Spend a fifth of each release on repayment and you finish at 188, close behind. The numbers are invented, but the shape is real: speed borrowed now is repaid with interest, and the interest is paid by people who weren't there when the choice was made. Sometimes borrowing is right (a demo next week). The mistake is not knowing you borrowed. Estimation, and Brooks's law Every software schedule is wrong, and nearly always in the same direction. Part of the reason is psychological: Kahneman and Tversky named the planning fallacy in 1979, the habit of planning from the best-case story of this project instead of the record of similar ones. Part is mathematical, and you can see it. Suppose every task estimate is honest: the median, a coin-flip guess of how long it takes. Task durations are skewed, because a task can take twice as long but not half as short as nothing. The toy below simulates ten tasks, each estimated at 3 days. Interactive · Honest estimates, late project Each task's real time is random and skewed, with the estimate as its median. 6,000 simulated projects, same random numbers each time. Number of tasks Uncertainty per task With ten tasks and moderate uncertainty, the chance of finishing by the sum of the estimates (30 days) is only about one in four. A date with an 80% chance is nearer 39 days. Each estimate was fair; the total isn't, because the delays do not cancel out the early finishes. This is also why one number ("done in 30 days") is worth less than a range. Now the famous law. When a project is late, the tempting fix is to add people. Brooks (1975): "Adding manpower to a late software project makes it later." His reasons: newcomers need time to learn and take veterans' time to teach them; and communication grows faster than headcount, with n people having n(n-1)/2 pairs (45 pairs for ten people, 1,225 for fifty). Some work also cannot be split: "nine women can't make a baby in one month." Interactive · Add people to a late project? A toy: a team of 8. Newcomers produce nothing for 4 weeks and each takes a quarter of a veteran's time to train. Every pair of people costs a slice of a person-week, every week. Work left (person-weeks) People added today Cost of each pair per week With 30 person-weeks left, adding people slows the project; with 120 left, it helps. Brooks himself later called his law an oversimplification, and later writers such as Steve McConnell argued that late projects are usually ones that started with an over-optimistic estimate. The robust lesson is narrower: adding people near the end costs more than it seems; adding good people early, or on work that splits cleanly, can pay. Agile and waterfall, fairly The waterfall approach does the phases in order: requirements, design, build, test, release. It is easy to plan, to contract for and to audit, which is why it survives where requirements are stable and the cost of error is high. Defenders point out that mistakes caught early are much cheaper than late ones, and that documentation helps new people. A fact often missed: Winston Royce's 1970 paper, usually credited as the source of the picture, called a purely sequential process risky and inviting failure, and went on to propose feedback loops. The word "waterfall" seems to have come later. Agile grew out of a meeting of seventeen practitioners at the Snowbird resort in Utah in February 2001. Their Manifesto prefers individuals and interactions over processes and tools, working software over comprehensive documentation, customer collaboration over contract negotiation, and responding to change over following a plan. Teams work in short cycles of a few weeks, show something working each time, and adjust. Its critics say the evidence for its benefits is limited, that it can neglect documentation and architecture, and that in large safety-critical systems you can't skip planning. Its defenders reply that waterfall's "plan" is a guess that gets more wrong the longer it runs. WaterfallAgile Best whenRequirements are stable, errors are costly (safety, hardware)Needs are unclear and change fast StrengthClear plan, contract, paper trailEarly feedback, fast correction RiskFinding the wrong thing lateDrift, thin documentation Most real teams mix the two. Hardware-heavy projects, as in Systems Engineering (34/22), lean toward the V; app teams lean agile. The honest position is that the choice depends on how well you know what to build, and how much a mistake costs. Reliability, incidents and blameless postmortems Every system that runs long enough fails. What separates teams is what they do afterwards. In August 2012 the trading firm Knight Capital installed new software on eight servers, but one was missed. The new release reused a flag that, on the server still running the old code, switched on a function retired years before. In about 45 minutes it sent millions of unintended orders. The SEC described losses of more than $460 million (the firm reported a pre-tax loss of about $440 million). A missed copy, a reused flag and old code nobody had deleted: none of these was one person's mistake. They were gaps in a process. That is the idea behind the blameless postmortem, as the Google SRE book puts it: find the contributing causes of an incident without blaming any individual or team, on the assumption that everyone acted reasonably on what they knew. The reason is practical. When people fear punishment, they hide problems and stop reporting near-misses, and the next incident is worse. A good postmortem asks what in the system made the mistake easy to make, and what will make it harder next time: a check, an alarm, a staged rollout, a deleted dead function. Blame asks who. A postmortem asks how the system let it happen. What a graduate just sees Code is read and changed far more than it is written, so write it for the next stranger. A module should hide one decision likely to change; if a change ripples everywhere, the cuts were in the wrong places. Small, frequent merges beat big, rare ones. A green test suite means the questions someone asked passed, not that the code is right. Technical debt is a loan; the danger is borrowing without knowing it. An estimate is a distribution, so ask for a range and the chance of hitting it. Adding people to a late project costs more than it looks. Methods like agile and waterfall are bets about how well you know what to build. After a failure, ask what in the system allowed it, not who to blame. Where it shows up next Systems Engineering & the Capstone (34/22): the same ideas (interfaces, verification, margins) applied where software meets hardware. The Ariane 5 failure there is a software engineering story too. Computer Security (34/33): most breaches are engineering failures, such as unpatched software and missed review, and security is built on the same code review, tests and postmortems. Operating Systems (34/26) and Databases (34/28): the largest codebases you will read, built with these tools. In the real world: every app, every website, a car's firmware, a hospital's records. The job titles are software engineer, site reliability engineer and engineering manager. If you want to go deeper 📘 Software Engineering, Ian Sommerville (Pearson, 10th ed., 2015): the standard university textbook, broad and methodical. 📘 Software Engineering at Google, edited by Titus Winters, Tom Manshreck and Hyrum Wright (O'Reilly, 2020): how a very large company does it, free to read online. 📘 The Mythical Man-Month, Frederick P. Brooks Jr. (1975; anniversary edition 1995): the gentle classic, short essays you can read in a weekend. 🌐 MIT OpenCourseWare 6.005, Elements of Software Construction (Fall 2008): free lectures and readings on abstraction, specifications and testing. The takeaway Software engineering is the craft of letting many people change one program for years without breaking it. It rests on hiding decisions behind interfaces, recording history in version control, testing (and knowing what tests can't prove), managing debt, estimating with honest ranges, choosing a process that fits how much you know, and learning from failures without blame. Try this: open any app you use and look for the last update note. Then think about what the team must have had in place (tests, review, a safe way to ship) for you to receive it without noticing. Which of them might have been missing the last time the app broke? Sources & Further Reading Sources. Brooks, The Mythical Man-Month (Addison-Wesley, 1975; 1995 anniversary edition) and Wikipedia, "Brooks's law" (his later comment, McConnell's critique). Parnas, "On the Criteria to Be Used in Decomposing Systems into Modules", Communications of the ACM 15(12), 1972. Git: Wikipedia, "Git" (Torvalds, April 2005, BitKeeper). The merge rule was checked against git merge-file. Test pyramid: Martin Fowler, "The Practical Test Pyramid" (attributing it to Mike Cohn, 2009). Technical debt: Cunningham, OOPSLA '92 experience report on WyCash, and his later clarification. Planning fallacy: Kahneman and Tversky, 1979. Waterfall and Royce: Wikipedia, "Waterfall model". Agile: agilemanifesto.org history (Snowbird, February 2001, seventeen signatories). Knight Capital: SEC findings as reported by secondary sources; Wikipedia, "Knight Capital Group". Blameless postmortems: Google SRE book, "Postmortem Culture". The simulations are toy models; their results were computed in node: debt (200, 132, 188 features after 20 releases), estimation (24.6% chance, 80% date 38.6 days, seeded), Brooks (arithmetic of the toy). 🌐 Software Engineering at Google (free online) 🌐 MIT OpenCourseWare 6.005: Elements of Software Construction 🌐 Google SRE book: Postmortem Culture 🌐 Martin Fowler: The Practical Test Pyramid 📘 The Mythical Man-Month, Frederick P. Brooks Jr. Step 10. Operating Systems: How One Machine Safely Pretends to Be Many ---------------------------------------------------------------------- Why: How one machine runs hundreds of programs at once without chaos. Dozens of programs share a few cores and one pool of memory, and none can read another's secrets or take the machine down. That is the operating system's whole job, done with a few hardware tricks. Right now your phone is running dozens of programs on a handful of cores. A game, a music player, a browser with twenty tabs and the software that keeps your clock right all believe they have the machine to themselves. One of them crashes and the rest carry on. None of them can read the others' passwords out of memory. A file you save survives a battery dying a moment later. None of this comes free from the hardware. It is the work of one special program, the operating system, whose central job is not to be clever but to be a referee: to share one machine among many programs that do not trust each other, safely and fairly. Nearly every idea in the subject is a way of keeping that promise cheaply. The course in one box Who takes it: computer science and computer engineering students, usually in the third year. What it's for: understanding the program underneath every other program: how it divides the CPU, memory and disk among everything that wants them. Comes after: Computer Architecture (34/25) and Data Structures (34/23). Leads to: Computer Networks (34/27) and Computer Security (34/33); Databases (34/28) borrows its locking, caching and logging ideas. Honest line: you won't be able to write a kernel after this piece. You will see why a crash in one app does not take down another, why your computer slows to a crawl when it runs out of memory, and why concurrency bugs appear only occasionally. The free textbook Operating Systems: Three Easy Pieces (OSTEP) is the natural next step, and the piece you are reading is arranged around its main ideas. An OS exists to share one machine safely Picture a shared flat with one kitchen and no rules. Anyone can use the oven, move anyone's food, or lock the door and never leave. Programs are like that unless something enforces order. The enforcement is built into the hardware, which has (at least) two modes. In user mode a program can do arithmetic and touch its own memory, and nothing else. In kernel mode the code may do anything: talk to the disk, change the memory map, switch off interrupts. Only the operating system's core, the kernel, runs in kernel mode. A user program that wants anything real, such as reading a file, opening a network connection or getting more memory, has to ask. It executes a special instruction, a system call, which makes the CPU jump to a fixed entry point inside the kernel and switch to kernel mode. The kernel checks the request, does the work, and returns to user mode. The program cannot choose where in the kernel it lands, which is the point: a door with one guarded entrance, not a wall with holes. A second piece of hardware makes the rule enforceable. A timer interrupt forces the CPU back into the kernel many times a second, so no program can hog the machine by refusing to give it back. Together these give the OS its three duties: virtualise the machine so each program sees its own CPU and memory, manage concurrency so they can overlap without corrupting each other, and make data persist. Those are OSTEP's three "easy pieces" and the plan of what follows. Interactive · Predict what the kernel does Pick something a program might do, guess, then see what really happens. Choose a scenario. Processes and threads: programs in motion A program on disk is just a file. A process is that program running: its code, its memory (the address space), its open files, and the CPU registers where it currently is. The OS keeps one record per process, and the process is the unit of protection: one process cannot touch another's memory. That is why a crashed browser tab, run as its own process, does not take the others with it. On Unix-like systems a new process is made by fork, which clones the caller, and exec, which swaps the clone's program for another. A thread is a path of execution inside a process. Threads of the same process share its memory but each has its own registers and stack. That sharing is the attraction (cheap to create, easy to cooperate) and the danger, as the sections on races and deadlock show. At any moment a process is in one of three states: running on a core, ready and waiting for a core, or blocked waiting for something slow like the disk. The OS moves processes between these states constantly. Swapping the running process for another is a context switch: save the old one's registers, load the new one's and switch to its address space. Nothing useful is computed while it happens, so it is pure overhead, and the next idea is about how often to pay it. Scheduling: who runs next? If three programs are ready and there is one core, the scheduler must choose. The choice is a trade-off between measurements. Turnaround time is finish time minus arrival time. Waiting time is the time spent ready but not running. Response time is how long until the job first gets the CPU. Interactive programs care about response, batch jobs about turnaround. The simplest policy is first come, first served. Its flaw is the convoy effect: with three jobs needing 24, 3 and 3 time units arriving in that order, the short ones wait 24 and 27 units behind the long one, for an average wait of 17. Run the shortest job first and the average wait drops to 3, which is provably the best possible average, but it needs to know job lengths in advance and can starve long jobs. Round robin is the compromise: give each job a short time slice, the quantum, then send it to the back of the line. With a quantum of 4, the same three jobs wait 6, 4 and 7 units, about 5.7 on average, and nobody waits long for a first turn. worst-case wait for a first turn in round robin ≤ (jobs − 1) × quantum Interactive · A live scheduler Round-robin quantum Cost of each context switch Set the policy to round robin on the mixed job set and drag the quantum down to 1. Response time becomes excellent, but with a switch cost of 1 the machine spends nearly half its time switching and the average turnaround is about 38 units, against about 15 for first come, first served. Raise the quantum and the policy turns back into first come, first served. Real schedulers sit in the middle: Linux used the Completely Fair Scheduler from 2007, and since version 6.6 (late 2023) uses a newer design called EEVDF, still built on the same trade-off. Virtual memory: a private address space for everyone If every program used real memory addresses, one program's bug could scribble on another's data, and no program could be placed in memory without knowing what was already there. So the OS gives each process virtual addresses that start at zero, as though it owned all of memory, and the hardware's memory-management unit translates every access into a real physical address. Translation works on fixed-size blocks called pages, usually 4 KiB. A virtual address splits into a page number and an offset within the page. The page table, one per process, maps each page number to a physical frame; the offset is copied unchanged. If the page is not in memory, the access raises a page fault and the kernel steps in: it may fetch the page from disk, or stop a program that was never allowed to touch it. physical address = frame number × 4096 + offset Interactive · Translate an address Virtual address The default address, 0x2A5C, is page 2, offset 0xA5C. Page 2 lives in frame 7, so the physical address is 0x7A5C. Drag into page 1 or page 5 and you get a page fault. On a modern 64-bit PC a virtual address has 48 usable bits: a 12-bit offset plus four levels of 9-bit page-table indexes (9 × 4 + 12 = 48), for 248 bytes, or 256 TiB, of address space per process. The tables are sparse, so only the parts in use cost memory. Because a translation would otherwise add several memory reads to every access, a small cache of recent translations, the TLB, sits in the CPU; this is the hardware from Computer Architecture doing the OS a favour. The costly case is a page fault that goes to disk. Using the figures from the architecture piece (RAM about 100 ns, an SSD read about 150 µs), if just one access in a thousand faults, the average access time is 100 + 0.001 × 150,000 = 250 ns, 2.5 times slower than RAM alone. When there are too few frames, the system spends its time swapping pages in and out and gets nothing done, called thrashing. Choosing which page to evict is a policy question you can try: Interactive · Which page to throw out? Frames of memory Red = page fault. FIFO evicts the oldest page, LRU the least recently used, Optimal the one needed furthest in the future (it needs a crystal ball, so it is a yardstick, not an algorithm anyone can run). On the first string, FIFO with 3 frames faults 9 times and with more memory (4 frames) faults 10 times. This is Belady's anomaly: for FIFO, extra memory can hurt. LRU never does that, and tracks Optimal better because programs show locality, as the cache section of the architecture piece described. Real systems approximate LRU cheaply. Races and locks: when two threads touch one thing Two threads each run counter = counter + 1. It looks like one step but is three: load the value into a register, add one, store it back. If the threads interleave, both can load 0, both compute 1, and both store 1. The counter is 1 instead of 2: one update is lost. This is a race condition: the result depends on the timing, and the timing is outside your control. The cure is a lock (mutex). A thread must hold the lock to enter the critical section, and only one thread can at a time, so the three steps can no longer be torn apart. Locks themselves rest on a hardware atomic instruction, such as compare-and-swap, which reads and changes a value in one indivisible step. Interactive · Schedule the threads yourself Step thread 1Step thread 2Reset Step thread 1 once (load), then thread 2 through all three steps, then thread 1 to the end: the final counter is 1. With the lock switched on, thread 2 is blocked until thread 1 lets go, and no ordering gives the wrong answer. If each step were given to either thread by a coin flip, an unlocked run would lose an update three times in four. Real threads run long stretches between switches, so the bug is far rarer and shows up only occasionally, under load, on someone else's machine. That is what makes races so hard to debug. The worst version of this story is the Therac-25, a radiation-therapy machine. Between June 1985 and January 1987 it gave at least six patients massive overdoses. In their 1993 investigation, Nancy Leveson and Clark Turner traced one failure to a race: if an operator edited the treatment settings quickly enough, the machine could be left configured differently from what the screen showed. They also stressed that this was not the only cause: earlier models had hardware safety interlocks that the Therac-25 replaced with software, and the investigators blamed overconfidence in software and poor follow-up of accident reports as much as the bug. Deadlock: waiting in a circle Locks fix races and create a new problem. Suppose thread 1 locks A and then wants B, while thread 2 has locked B and now wants A. Each holds what the other needs, and neither will let go. Nothing crashes; the program simply stops. This is deadlock. It needs four conditions, listed in a 1971 survey by Coffman, Elphick and Shoshani: mutual exclusion (locks are exclusive), hold and wait (a thread holds one lock while asking for another), no preemption (locks can't be taken away) and circular wait (a loop of threads each waiting for the next). Break any one and deadlock cannot happen. The cheapest fix is to break circular wait: always take locks in the same global order. Dijkstra posed the classic version in 1965 and Tony Hoare retold it as five philosophers sharing five forks, each needing two to eat; if all grab their left fork at once, all starve. Interactive · Walk into a deadlock Step thread 1Step thread 2Reset With opposite orders, step thread 1 once and thread 2 once: both are now stuck. With a coin-flip scheduler half of all runs end this way. With the same order, 0% do, however the steps interleave. The bug is again timing-dependent, which is why it can lie dormant for months. File systems: names and blocks that survive a crash A disk offers only numbered blocks. A file system turns that into files with names and directories. The key structure is the inode, a small record per file holding its size, permissions and the locations of its data blocks. A directory is just a file mapping names to inode numbers. To save space for small files while still allowing huge ones, an inode holds a few direct block pointers and then pointers to blocks of pointers, indirect blocks, nested up to three levels. Interactive · How big can a file be? Size of the file Model: 12 direct pointers, then single, double and triple indirect, 4-byte pointers, in the style of the classic Unix design (ext2 has this shape). Real file systems add extents, caching and other limits. With 4 KiB blocks one block holds 1,024 pointers. The 12 direct pointers cover 48 KiB, one single-indirect block covers 4 MiB more, double indirect 4 GiB, triple indirect 4 TiB, for a layout limit of about 4 TiB. A small file needs one block read after the inode; the end of a huge file needs four. The shape is a tree that is shallow for the common case, a pattern you will meet again in databases. The hard problem is the crash. Appending to a file changes several blocks: the data, the inode, the free-space map. If power fails after one is written and before the others, the disk contradicts itself. The first remedy was a slow repair scan on reboot. The modern one is journaling: first write a note of what you are about to do into a log, then do it, so after a crash the system replays or discards the log. It is the same idea as a bank writing a transaction ledger before moving the money. What a graduate just sees The OS is a referee: the hardware's user/kernel split is what lets mutually distrustful programs share one machine. Every request for anything real, whether file, network or memory, is a system call through one guarded door. A process owns an address space; a thread only owns a path through someone else's. Scheduling is a trade-off between waiting, finishing and switching, and there is no best policy. Memory addresses are fiction: a table translates them, and a missing page costs a disk trip. A bug that depends on timing will hide in testing and appear in production. x = x + 1 is three steps, and any shared state needs a lock. Take locks in a fixed order, or two of them will eventually wait for each other forever. A file is an inode plus pointers, and crash safety means writing down your intentions first. Where it shows up next Computer Networks (34/27): a network connection is a file-like handle from a system call, and the kernel's network stack and its interrupts deliver every packet. Computer Security (34/33): the user/kernel boundary, permissions and address-space isolation are the foundation of every defence, and race conditions between a check and a use are a classic attack. Databases (34/28): a database re-implements this subject: its buffer pool is paging, its transactions use locks and deadlock detection, and its write-ahead log is a journal. The cloud: containers are ordinary processes fenced off by kernel features, and virtual machines extend the virtual-memory trick to a whole computer. Software Engineering (34/31): every multithreaded program inherits the race and deadlock problems here, and most advice about concurrency exists to avoid them. If you want to go deeper 📘 Free and the best first book: Remzi and Andrea Arpaci-Dusseau, Operating Systems: Three Easy Pieces (OSTEP), free online: virtualisation, concurrency and persistence, widely praised for its clear treatment of scheduling and paging. 📘 Textbook: Silberschatz, Galvin and Gagne, Operating System Concepts (10th ed.). The most widely assigned survey; strong on the tables of algorithms. 📘 Textbook: Andrew Tanenbaum and Herbert Bos, Modern Operating Systems (5th ed., 2022). A more narrative alternative with case studies of Linux, Windows and Android. ▶️ Gentler: Crash Course Computer Science, episode 18, "Operating Systems" (about 14 minutes), a first look at the same ideas. 🌐 Free course: MIT OpenCourseWare 6.1810 Operating System Engineering: you read and extend a small teaching kernel, xv6, whose free book is by Cox, Kaashoek and Morris. The takeaway An operating system makes one machine look like many private ones, using hardware modes, timer interrupts and address translation to keep programs apart. Its policies, from scheduling to page replacement, are trade-offs, and its hardest problems, races, deadlocks and crashes, are all about timing, which is why they hide. Try this: open your computer's activity monitor or task manager and sort by memory. Note how many processes exist and how many threads each uses. Then ask which of them could harm the others, and why they can't. Sources & Further Reading Sources. OSTEP, Arpaci-Dusseau and Arpaci-Dusseau (version 1.10, November 2023). Round-robin and shortest-job-first examples are the standard textbook ones (24, 3, 3), recomputed in code here. Belady's anomaly reference string 1 2 3 4 1 2 5 1 2 3 4 5 (FIFO: 9 faults with 3 frames, 10 with 4), recomputed here. Therac-25: Leveson and Turner, "An Investigation of the Therac-25 Accidents", IEEE Computer 26(7), July 1993. Deadlock conditions: Coffman, Elphick and Shoshani, "System Deadlocks", Computing Surveys 3(2), 1971. Dining philosophers: Dijkstra, 1965, retold by Hoare. Linux scheduler change: CFS since 2.6.23 (2007), replaced by EEVDF in Linux 6.6 (merged August 2023, released October 2023), per Phoronix and Linux Magazine. RAM and SSD figures: the widely quoted "latency numbers" list (c. 2012). All numbers in the simulators were computed and checked in code. 🌐 OSTEP: Operating Systems: Three Easy Pieces 🌐 MIT OpenCourseWare: 6.1810 Operating System Engineering 🌐 xv6, a simple Unix-like teaching operating system ▶️ Crash Course Computer Science #18: Operating Systems (YouTube) Step 11. Computer Networks: Why Latency, Not Bandwidth, Rules ------------------------------------------------------------- Why: How a message crosses the planet in a fraction of a second. The network between you and a web server is unreliable on purpose, and the number that decides how fast anything feels is not on your internet bill. It is the number of round trips, multiplied by the speed of light. You type a web address and press enter. A fraction of a second later a page has arrived from a machine you have never seen, perhaps on another continent, through dozens of devices owned by companies that don't know each other. No one planned your route. If a cable on the way fails, the page still comes. It rarely arrives scrambled, and it never asks you which wires to use. One thing about this is stranger than it looks: the network is unreliable on purpose. Individual packets get lost, duplicated and delayed all the time. Reliability is rebuilt on top, at the two ends, out of cheap, dumb parts in the middle. Once you see how, the number that governs everything you feel as "speed" turns out not to be the one on your internet bill. The course in one box Who takes it: computer science and computer engineering students, usually in the third year. What it's for: understanding how independent machines exchange data across an unreliable, shared, planet-sized network. Comes after: Operating Systems (34/26), because sockets, buffers and timers are all kernel services. Leads to: Computer Security (34/33), which is mostly about attacking and defending what this subject builds. Databases (34/28) meets the same problems when data is spread over many machines. Honest line: you won't be able to configure a carrier router after this piece. You will see why a call to Sydney has a delay no money can remove, and what really happens in the 0.2 seconds before a page appears. The Internet (29/04) tells the history; this piece explains the mechanisms. Packets, not circuits The old telephone network used circuit switching: a call reserved a path, and the capacity on it stayed yours, used or not. The internet uses packet switching: chop every message into small pieces, label each with its destination, and let them share links first come, first served. Silence costs nothing, because there are no reserved slots to waste. Traffic from people is bursty, so sharing wins. The classic example: a 1 Mbps link, users who each need 100 kbps while active, and each active only 10% of the time. Circuits can serve exactly 10 users. Packets can serve far more, because they are seldom all active at once. The chance that more than 10 of N users are active at the same moment is a binomial tail. Interactive · Sharing a link Number of users sharing the link Each user is active At 35 users and 10% activity, the chance that more than 10 want to send at once is about 0.04%: 4 times in 10,000 moments. Packet switching has served 3.5 times as many users and almost never makes anyone wait. Push the activity to 20% and the overload chance jumps to about 7%: the price of sharing is occasional queues, and when a queue overflows, packets are simply dropped. Hold that thought; congestion control exists because of it. Layers: each one trusts the one below No one program does all this. The work is split into layers, each with one job and each hiding the layer below. The common four-layer picture goes like this. The link layer (Ethernet, Wi-Fi) moves a frame across one hop. The network layer (IP) carries a packet host to host across many hops, with no promises. The transport layer (TCP or UDP) connects one program to another using port numbers, and TCP adds reliability. The application layer (HTTP, DNS, email) is what programs actually say. The seven-layer OSI model is the textbook's finer version of the same idea. Layers cooperate by encapsulation: each wraps what it receives from above in its own header, like envelopes inside envelopes. The rule that justifies this design is the end-to-end principle (Saltzer, Reed and Clark, 1984): put the smart functions at the ends, because only the ends know what "correct" means. Interactive · Wrap a message Message size Ethernet 14 bytes + IPv4 20 + TCP 20 (no options) = 54 bytes of headers per packet; the largest TCP payload in an ordinary 1,500-byte Ethernet packet is 1,460 bytes. Trailers, preamble and gaps are ignored. A single keystroke, one byte, travels as 55 bytes, so only 1.8% of what is sent is yours. A big transfer approaches 96.4%, since each 1,460 bytes of payload carries 54 of headers. Layers cost a little and buy an enormous amount: Wi-Fi can be swapped for fibre under TCP without TCP noticing. Names and addresses: IP and DNS Every interface on the internet has an IP address: 32 bits in IPv4 (4,294,967,296 possible), written as four numbers, and 128 bits in IPv6. The address has two parts: a network prefix and a host number within it. A suffix like /26 says the first 26 bits are the network. Everything with the same prefix is "on the same network" and reachable directly; anything else is sent to a router. IANA handed out the last free IPv4 blocks to the regional registries on 3 February 2011, which is why IPv6 exists and why many networks share one address through address translation. Interactive · Which network is this? Your address Prefix length Talk to With the defaults, 192.168.1.130/26 sits in the network 192.168.1.128 to 192.168.1.191, with 62 usable hosts. 192.168.1.200 is outside it, so your computer would send that traffic to its router instead of straight to the machine. People don't remember numbers, so the Domain Name System (DNS) translates names to addresses. It is a distributed, cached database arranged as a tree. To find www.example.com, a resolver asks a root server where the .com servers are, asks those where example.com's own servers are, and asks them for the answer, then caches it for the time the owner allows (the TTL). The root has 13 named identities (A to M) run by 12 organisations; as of 1 November 2026 root-servers.org counted 2,049 operational instances of them spread around the world. Routing: each router only knows the next hop A router does not know the path to anywhere. It holds a forwarding table of prefixes and the next hop for each, and for every packet it finds the entry that matches the destination. If several match, the longest prefix wins, since it is the most specific. Routers across the internet learn the table from each other: inside a network with protocols such as OSPF, and between the roughly tens of thousands of independent networks (autonomous systems) with BGP, which spreads "I can reach this prefix" announcements. Interactive · Longest prefix wins Destination Routing is fragile in a way worth knowing. On 4 October 2021, Facebook, Instagram and WhatsApp vanished for about six hours. By Meta's own account, a command run during routine maintenance accidentally took down its backbone connections; its DNS servers, built to withdraw their BGP announcements when they cannot reach the data centres, then withdrew them, so the rest of the internet no longer had a route to Meta's name servers. Nothing was hacked. The network did what it was told. TCP: a reliable pipe built from an unreliable network IP just tries its best. TCP turns that into a dependable stream of bytes. It opens with a three-way handshake (SYN, SYN-ACK, ACK), numbers every byte, has the receiver acknowledge what arrived, and resends what is not acknowledged in time. It also holds back so as not to drown the receiver (flow control) and, more subtly, so as not to drown the network (congestion control). The need for the second was discovered the hard way: in October 1986 the throughput on a path between Lawrence Berkeley Laboratory and UC Berkeley, about 400 yards apart, fell from 32 kbit/s to 40 bit/s. Van Jacobson's "Congestion Avoidance and Control" (1988) is the repair that every TCP since has built on. The idea: the sender keeps a congestion window (cwnd), the number of packets allowed in flight. It starts small and doubles every round trip (slow start; the initial window of 10 packets is allowed by RFC 6928). Once it finds the limit, it grows by one packet per round trip and, on a loss, halves its window. This is additive increase, multiplicative decrease (AIMD), and the window traces a sawtooth. Interactive · The TCP sawtooth Packets the path can hold A second flow joins at round 30 Idealised: no buffer, synchronised losses, one round per step. Blue = flow 1, orange = flow 2, dashed = capacity. One flow settles into a sawtooth between roughly half the capacity and full, averaging roughly three-quarters to four-fifths of it. Add a second flow and the two converge to the same share, though one started far behind. That is why AIMD is fair without anyone coordinating: the bigger flow loses more on each halving, and both gain equally on each increase. Modern stacks use refinements (Linux defaults to CUBIC; Google's BBR estimates bandwidth and delay instead of waiting for loss), but they all answer the same question: how fast is it safe to go? UDP is the opposite choice: no reliability, no waiting, which suits video calls and games that prefer a late packet dropped to an old one resent. Latency versus bandwidth: you can't beat the speed of light Bandwidth is how many bits per second a link can carry. Latency is how long one bit takes to get there. A highway analogy: bandwidth is the number of lanes, latency is the length of the road at the speed limit. Lanes can be added; the speed limit is physics. Light in vacuum covers 299,792 km every second; in glass fibre, with a refractive index of about 1.47, only about 204,000 km/s. round-trip time ≥ 2 × distance ÷ signal speed Interactive · The speed-of-light floor One-way path length Link bandwidth Page or file size New York to London is about 5,570 km along the great circle. Light in fibre needs 27 ms each way, a round-trip floor of about 55 ms; in practice a cable that is not a straight line adds more. Hibernia Express, built to be fast, reported a tested round trip of under 58.95 ms between data centres in New Jersey and Slough. London to Sydney is a floor of about 167 ms. A satellite in geostationary orbit, 35,786 km up, makes a request-and-reply cover about 143,000 km: at least 477 ms, and measured median latency for such services in early 2025 was around 680 ms. Low-orbit constellations fly about 550 km up, which is why Starlink reports a median near 25 ms (SpaceX, June 2025) and Ookla measured about 45 ms for US users in early 2025. The practical rule: a transfer takes about one round trip plus size divided by bandwidth. For a 100 KB page on a 100 Mbps link with a 50 ms round trip, the transfer itself takes 8 ms and the round trip 50 ms, so 86% of the wait is latency, and more bandwidth hardly helps. Also, a sender can only have a bandwidth-delay product of data in flight: a 1 Gbps path with 50 ms of round trip holds 6.25 MB, and a sender limited to a 64 KiB window on it moves just 10.5 Mbps. A page load, round trip by round trip Here is what happens when you open a secure web page. The browser checks its caches. If it has no address for the name, it asks DNS. It opens a TCP connection (one round trip for the handshake). It runs a TLS handshake, in which the two ends agree on secret keys using public-key cryptography, and the server proves its identity with a certificate signed by an authority your device trusts. After that all traffic is encrypted and tamper-evident. Only then does it send the HTTP request, "GET /", and wait one more round trip for the first byte. The browser parses the HTML, finds more files (style sheets, scripts, images) and fetches them, often from a nearby content delivery network precisely to shorten the round trips. TLS 1.2 needed two round trips to set up; TLS 1.3 (RFC 8446, August 2018) needs one, and can sometimes send data in zero for a returning visitor, at some cost to replay protection. HTTP/3 (RFC 9114, June 2022) runs over QUIC, which runs over UDP and folds the transport and encryption handshakes into one. The padlock means the channel to that domain is private; it does not say the site is trustworthy. Computer Security (34/33) takes up the rest. Interactive · Round trips before the first byte DNS answer cachedReturning visitor Round-trip time to the server Idealised: DNS counted as one 20 ms trip to your resolver, no server think time, no packet loss. "Returning visitor" means TLS session resumption (0-RTT where the protocol allows it). At 100 ms, the old stack (TCP plus TLS 1.2) needs 4 round trips, 400 ms, before the first byte, plus DNS. TLS 1.3 takes 3, QUIC takes 2, and a returning QUIC visitor takes 1. The server's speed never appears in these numbers: the wait is geography. That is why every large site puts copies of its content near you. What a graduate just sees The network is deliberately unreliable and dumb; reliability lives at the ends. Packet switching wins because traffic is bursty, and its cost is occasional queues and drops. Each layer wraps the one above with a header, and each header costs bytes. A prefix says who is local; a router forwards on the longest matching prefix, one hop at a time. Names are looked up through a cached tree, which is why changing DNS records takes time to spread. Latency, not bandwidth, usually decides how fast something feels, and its floor is the speed of light. Congestion control is a sawtooth: probe for more, halve on loss. Every setup handshake is a round trip, so fewer handshakes make a page faster. Where it shows up next Computer Security (34/33): TLS, certificates, DNS spoofing, BGP hijacks and denial-of-service floods are attacks on exactly the layers described here. Operating Systems (34/26), looking back: a socket is a file-like handle, and every packet arrival is an interrupt the kernel must schedule. Databases (34/28): replicating data between continents runs into the latency floor here, which is why distributed databases have to choose between speed and consistency. Real jobs: network engineers, site-reliability engineers, anyone tuning a web site's load time, and anyone building video calls, games or trading systems where milliseconds matter. If you want to go deeper 📘 Textbook: James Kurose and Keith Ross, Computer Networking: A Top-Down Approach (9th ed.). The most widely assigned text; starts with the web and works down the layers. 📘 Textbook: Larry Peterson and Bruce Davie, Computer Networks: A Systems Approach (6th ed.), readable free online at book.systemsapproach.org. Best on how the pieces fit together. 📘 Gentler and free: Ilya Grigorik, High Performance Browser Networking. Latency, TCP, TLS and HTTP/2 explained for people who build web pages. 🌐 Free course: Stanford CS 144, Introduction to Computer Networking: lecture notes, slides, congestion-control videos and the labs in which students write their own TCP. The takeaway The internet is a pile of simple parts: unreliable packets, layered headers, prefixes and next hops. Reliability, fairness and security are added at the ends. How fast it feels depends mostly on the number of round trips multiplied by the speed of light, so reducing handshakes beats buying bandwidth. Try this: run ping to a site on another continent and note the time. Then divide the distance in km by 100: that is the round-trip floor in milliseconds through fibre. See how close the real figure comes. Sources & Further Reading Sources. Statistical-multiplexing example (1 Mbps link, 100 kbps users, 10% activity, 35 users): Kurose and Ross; exact binomial tail computed here (0.042%). IANA IPv4 depletion (3 February 2011): ARIN. Root servers: root-servers.org (13 identities, 12 organisations, 2,049 instances as of 1 November 2026). Facebook outage of 4 October 2021: Meta Engineering, "More details about the Oct. 4 Facebook outage". Congestion collapse of October 1986 (32 kbit/s to 40 bit/s): Jacobson, "Congestion Avoidance and Control", SIGCOMM 1988. RFC 6928 (initial window of 10, April 2013); RFC 8446 (TLS 1.3, August 2018); RFC 9114 (HTTP/3 over QUIC, June 2022). End-to-end arguments: Saltzer, Reed and Clark, ACM TOCS 2(4), 1984. Hibernia Express round trip under 58.95 ms: Equinix and Hibernia Networks announcements (2015). Satellite figures: Ookla, Q1 2025 (GEO medians about 680 ms; Starlink US about 45 ms) and SpaceX, June 2025 (25.7 ms median peak-hour, US). Distances: great-circle (haversine) calculations, fibre index 1.47. Every number in the simulators was computed in code. 🌐 Stanford CS 144: Introduction to Computer Networking 🌐 High Performance Browser Networking (free online) 🌐 Computer Networks: A Systems Approach (online edition) 🌐 Meta Engineering: More details about the Oct. 4 Facebook outage Step 12. Databases: Why Your Data Survives a Power Cut ------------------------------------------------------ Why: How data is stored, queried and kept consistent when everyone writes at once. Behind every balance, booking and search box is a small set of ideas: tables, keys, an index, and a promise that a transfer either happens completely or not at all. You move 30 euros from savings to your current account. Halfway through, the bank's server loses power. When it comes back, your savings show 30 euros less, and your current account shows nothing extra. Money has vanished. You would, rightly, never use that bank again, and yet the bank's systems are running on ordinary computers that crash all the time. The reason you have never seen this happen is a field of computer science that most people never hear about. A database is the layer that keeps a company's facts: who owns what, who booked which seat, what you ordered. It has to answer questions about millions of records in a fraction of a second, let thousands of people change the same records at once, and survive crashes without losing a cent. This piece gives you the handful of ideas a graduate of a databases course still sees everywhere: why data lives in tables, why a lookup in a billion rows takes about four steps, what "transaction" really promises, and what you give up when you leave the traditional model behind. The course in one box Who takes it: Computer Science majors, usually in year 3, and anyone in data science or information systems. What it's for: how to store facts so they stay correct, can be found fast, and survive crashes and crowds. Comes after: Data Structures (34/23) and Discrete Mathematics (34/08). Leads to: no later subject in this series lists it as a prerequisite, but it leans on and feeds Operating Systems (34/26: locks and logs), Computer Networks (34/27: the CAP trade-off), Software Engineering (34/31) and Computer Security (34/33: SQL injection). Honest line: you won't be able to tune a production database after this; you will see why a search over a billion rows is quick and why a bank transfer is safe. Tables, keys and joins Why not just keep files? A spreadsheet or a text file works for one person and a few thousand rows. It stops working when two people edit at once, when the file is too big to scan, when a crash leaves it half-written, and when the same fact (a customer's address) is copied into twenty places and the copies drift apart. A database management system exists to fix those four problems. In 1970, Edgar F. Codd, a researcher at IBM, proposed the relational model in the journal Communications of the ACM: keep facts in plain tables and let programs ask questions without knowing how the data is laid out on disk. A table is a set of rows. Each row has a primary key, a column whose value is unique and names the row (a customer number). A different table refers to a row by storing its key as a foreign key (each order stores the customer number it belongs to). An order stores a customer id, not the customer's details. To see both together, join: pair every order with the customer whose id matches. The join is the move that makes the model powerful, and it is simple. Imagine pairing every customer with every order (that's the "cross product"), then throwing away every pair where the keys do not match. What's left is the join. Try it: join two tables Four customers, five orders. Choose what to pair, and watch how many rows survive. With no condition there are 4 × 5 = 20 pairings; matching on the key leaves 5 rows; a left join keeps customers with no orders (Dev) and adds a sixth row with blanks (NULL). customers orders No condition INNER JOIN LEFT JOIN SQL: say what you want, not how to get it Before relational databases, programmers wrote loops that walked through records one by one, following pointers. If the storage changed, the program broke. Codd's model came with a different idea: the programmer describes the result, and the system works out the method. The language that grew from this, SQL (first called SEQUEL, developed at IBM in the 1970s by Donald Chamberlin and Raymond Boyce), became an ANSI standard in 1986 and an ISO standard in 1987, and it is still how the world asks databases questions. SELECT SUM(total) FROM orders WHERE city = 'Lisbon' AND total >= 300; That sentence says nothing about loops, order, or files. The engine has a query planner that picks a plan: scan every row, or jump straight to the Lisbon rows using an index, whichever it estimates to be cheaper. The answer is the same either way; only the cost differs. This is called declarative programming, and it is the reason a query written in 1995 can run faster today without a single change. Try it: same question, two plans A table of 1,000 orders, made up for this demo. Pick a city and a minimum total. For Lisbon with a minimum of 300 there are 59 matching orders worth 23,486 in all; a full scan reads 1,000 rows and an index on city reads only the 144 Lisbon rows. Minimum total: 300 No index: scan every row Index on city Indexes: why a billion rows takes four steps An index is the back-of-the-book index of a table: a sorted structure that says "Lisbon: rows here". Without one, the only plan is to read everything. With one, you navigate. The standard structure is the B-tree, invented in the early 1970s by Rudolf Bayer and Edward McCreight. Each node holds hundreds of sorted keys, so each step discards all but one of hundreds of branches, and the tree stays only a few levels deep. This is the same idea as the binary search you know from Data Structures (34/23), widened. Binary search halves the range each step. A B-tree divides it by the fanout f, the number of branches per node, because disks and SSDs read data in pages, and one page may as well hold hundreds of keys. levels needed = the smallest h with fh ≥ N   (about logf N) Worked number: with N = 1,000,000,000 rows and a fanout of 200, 2004 = 1.6 × 109 is enough, so a lookup reads about four pages. A full scan of the same table would read, on average, half a billion rows if you were searching for one record. Try it: how deep is the tree? Slide the table size and the fanout. At a billion rows and a fanout of 200 the tree is 4 levels deep. Rows: 109 (1,000,000,000) Fanout (keys per page): 200 The price: every index must be updated on each write, and it takes space. Indexing everything makes reads fast and writes slow. Choosing what to index is half of a database engineer's craft. Transactions: all or nothing, and not tripping over each other A transaction is a group of steps the database treats as one. In 1983, Theo Härder and Andreas Reuter gave the group of guarantees a name that stuck: ACID, building on earlier work by Jim Gray. Atomicity: all the steps happen or none do. Consistency: rules you declared (a balance can't go below zero) are never broken by a committed transaction. Isolation: transactions running together behave as if they had run one after another. Durability: once the database says "committed", the change survives a crash, because it was first written to a log on disk. Try it: the bank transfer Account A holds 100 and B holds 50. Move money, and sometimes crash the server between the two steps. Without a transaction a crash after the debit leaves A = 70 and B = 50, so 30 are lost; with one, the debit is undone and the total stays at 150. Move 30 Move 130 No transaction Inside a transaction No crash Crash in the middle Run the transfer Isolation is the subtle one. Suppose Alice deposits 10 and Bob deposits 20 into an account holding 100, at the same moment. Each reads the balance, adds, and writes it back. If their steps interleave, one deposit is lost: the classic lost update. Databases prevent it with locks (or with versioned copies of the data), which makes the second transaction wait or retry. Stronger isolation means safer answers and less speed. The SQL standard defines several levels, and databases such as PostgreSQL document which anomalies each level allows, so that you can choose a cheaper level when you know the risk is acceptable. Try it: two deposits at once Starting balance 100; Alice adds 10, Bob adds 20; the right answer is 130. With interleaved steps and no lock the final balance is 120, so Alice's 10 vanishes; with a lock it is 130. No lock Lock the row Next stepStart over Normalisation: store each fact once The last relational habit a graduate keeps is normalisation: design the tables so that each fact is stored in exactly one place. If Ana's city is copied onto each of her orders, then when she moves, you must find and change every copy. Miss one and the database now holds two contradictory "truths". Splitting the data into customers and orders, joined by key, means her city is changed in one row. Normalisation is a trade, not a law. Joins cost time; some systems deliberately copy data (denormalise) to make reads fast, and then must work harder to keep the copies in step. Try it: Ana moves to Porto The same five orders, stored two ways. In the flat table Ana's city appears in 2 rows; in the split design it appears in 1. Flat: city on every order Split into two tables Update Ana's cityUpdate, but forget a rowReset NoSQL, and what CAP really says In the 2000s, companies such as Google and Amazon needed to spread data over thousands of machines. Splitting a relational database with strong guarantees across so many machines was hard, and a family of systems nicknamed NoSQL arose: key-value stores, document stores, wide-column stores, graph databases. They usually relax some of the relational model (joins, rigid schemas, sometimes strict isolation) in exchange for scale, flexible data shapes or speed. They are tools with trade-offs, not a replacement; many mature systems now offer both styles. The most quoted trade-off is the CAP theorem. Eric Brewer conjectured it in a 2000 talk and Seth Gilbert and Nancy Lynch proved a formal version in 2002. Stated in plain words: when the network splits a system into parts that cannot talk to each other (a partition), each part must choose between answering requests and giving answers that agree with the other part. You can't have both during the split. The real choice is therefore not "pick two of three": networks do fail, so partition tolerance isn't optional for a distributed system; the choice is what to give up while one is happening. Two cautions from the literature. Daniel Abadi pointed out in 2012 that CAP only describes behaviour during a partition, while the everyday trade-off is between consistency and latency (waiting for other machines to confirm); he called the fuller picture PACELC. And Martin Kleppmann argued in 2015 that CAP's definitions are narrow and often misapplied, so labelling a whole product "CP" or "AP" is usually too crude. Try it: split the network Two replicas hold the value x. Cut the link, write to the left one, then read from the right one. If the system refuses writes during the split, readers never see a wrong answer but the write fails; if it accepts writes, the write succeeds but the right replica returns a stale value until the link heals. Prefer agreement (refuse) Prefer answering (accept) Cut the linkWrite x = 2 at leftRead at rightReset leftrightx = 1x = 1 What a graduate just sees A table is a set of facts, and a join is "pair rows whose keys match", nothing more. A query says what, and the planner decides how. Same answer, very different cost. An index turns "read everything" into "walk a few levels"; each extra level multiplies capacity by the fanout. Any multi-step change that must not be half-done belongs inside a transaction. Two people reading, thinking and writing the same value will lose an update unless something prevents it. A fact stored twice will one day disagree with itself. When a network splits, you choose between refusing and possibly being wrong; there is no free third option. Never build SQL by gluing user text into a string; that is how injection attacks happen. Where it shows up next Operating Systems (34/26): the log that makes commits durable and the locks that give isolation are the same ideas an operating system uses for files and processes. Computer Networks (34/27): CAP is a statement about unreliable networks; replication is a networking problem. Computer Security (34/33): SQL injection is a database bug in the application, and one of the most famous web attacks. Machine Learning (34/32): training data lives in tables, and getting it out correctly is most of the real work. In the world: every payment, booking, inventory and login system, and most "apps", are a user interface on top of a database. If you want to go deeper 📘 Database System Concepts, 7th edition (2019), Avi Silberschatz, Henry Korth and S. Sudarshan: the standard university text, best for the full tour from relational algebra to recovery. Its companion site db-book.com has slides and an in-browser SQL lab. 📘 Designing Data-Intensive Applications, Martin Kleppmann; a second edition (with Chris Riccomini) appeared in 2026. Best for how real systems handle replication, partitions and consistency. ▶️ Gentler: the lectures of CMU 15-445, Intro to Database Systems (Andy Pavlo), are free on YouTube and clear about how engines really work. 🌐 Free course: CMU 15-445/645 (slides, notes, projects); or MIT OpenCourseWare 6.830 Database Systems. The takeaway A database is a promise-keeping machine. Tables and keys keep facts in one place, SQL lets you ask for results without caring how, indexes make lookups take a handful of steps, and transactions make a multi-step change safe against crashes and crowds. Everything past that, from NoSQL to CAP, is choosing which promise to loosen when scale or distance makes the full set too expensive. Try this: the next time an app shows you something stale (a "sold out" seat that was available, a count that lags), ask which promise it loosened, and why: speed, availability, or simply a cache. Sources: E. F. Codd, "A Relational Model of Data for Large Shared Data Banks", Communications of the ACM 13(6), 1970. T. Härder and A. Reuter, "Principles of Transaction-Oriented Database Recovery", ACM Computing Surveys 15(4), 1983. S. Gilbert and N. Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services", ACM SIGACT News 33(2), 2002. D. Abadi, "Consistency Tradeoffs in Modern Distributed Database System Design", IEEE Computer, February 2012. M. Kleppmann, "A Critique of the CAP Theorem", arXiv:1509.05393, 2015. D. Chamberlin, "Early History of SQL", IEEE Annals of the History of Computing, 2012. R. Bayer and E. McCreight, B-trees, early 1970s. PostgreSQL documentation, "Transaction Isolation". The tables and the 1,000-row dataset in the demos are invented for illustration. Go deeper: 📘 Database System Concepts — Silberschatz, Korth, Sudarshan (db-book.com) 📘 Designing Data-Intensive Applications — Martin Kleppmann 🌐 CMU 15-445 Intro to Database Systems (free) 🌐 PostgreSQL docs: Transaction Isolation Step 13. Programming Languages & Compilers: How Text Becomes a Machine ---------------------------------------------------------------------- Why: How code you write becomes code a machine runs. You type words and symbols; a chip does arithmetic on voltages. In between is a translator, and everything it does is a small idea you can hold in your head. You make a typo in a program, say you forget a closing bracket. Within a second, before anything has run, an editor underlines the line and says expected ')'. Something has read your text, understood its structure well enough to know a bracket is missing, and told you where. Nobody sat down and wrote a rule for your particular typo. Later you write 7 / 2 and get 3.5 in one language and 3 in another. Same symbols, different answers. And you hear, in the same week, that one language "has no garbage collector", another "checks everything at compile time", and a third "is just interpreted". These phrases are the vocabulary of a course that most programmers pick up in pieces. This piece puts the pieces together. The course in one box Who takes it: Computer Science majors, usually in year 3; also anyone building tools, frameworks or developer platforms. What it's for: how a programming language is defined, how its programs are translated to run on a machine, and what design choices (types, memory, style) trade against each other. Comes after: Data Structures (34/23) and Theory of Computation (34/29). Leads to: no later subject in this series lists it as a prerequisite, but it underlies Software Engineering (34/31), tells you what Computer Architecture (34/25) runs, and shows up in Computer Security (34/33), where many exploits are memory bugs. Honest line: you won't write a production compiler after this; you will see what a compiler does to your code and why languages differ the way they do. For what the machine does with the instructions at the end, Processors: How a CPU Thinks (29/11) is the easier first read. A language is syntax plus semantics Every programming language has two layers. Syntax is which strings of characters count as a program: where the brackets go, which words are reserved. Semantics is what a valid program means: what it does when it runs. Syntax is the spelling and grammar; semantics is the sense. The two come apart more than newcomers expect. The same syntax can have different semantics in different languages, and most arguments about "which language is better" are really about semantics. Try it: same symbols, different meaning Guess first, then reveal. The JavaScript column is computed live by your browser; the C and Python columns were run for this piece. 7 / 2 gives 3 in C, 3.5 in Python 3 and 3.5 in JavaScript. The text "5" + 3 gives "53" in JavaScript and a TypeError in Python. 7 / 2 -7 / 2 (integers) "5" + 3 Reveal the answers Languages also differ in how they are defined. Some have a long formal specification; some are defined by their main implementation; many are defined by a standard that a committee maintains. The notation used to write down a language's grammar, with rules like "an expression is a term, optionally followed by plus or minus and another term", is the first tool the rest of this piece uses. Interpreters and compilers A processor understands only its own machine instructions. A program in a human-friendly language must be translated. There are two basic ways: A compiler translates the whole program ahead of time into another form, usually machine code, which you then run. You pay once, and the result runs fast. An interpreter reads the program and carries out its meaning directly, step by step, while it runs. There is no separate translation step, which makes it easy to try things and easy to build. Real systems blur the line. Python compiles your source into bytecode for a virtual machine, and runs that (its documentation includes a disassembler for the bytecode). Java compiles to bytecode for the Java Virtual Machine, and the JVM can compile hot parts to machine code while the program runs, a technique called just-in-time (JIT) compilation; modern JavaScript engines do the same. So "is language X compiled or interpreted?" is usually a question about one implementation, not about the language. The idea of a compiler is old. Grace Hopper's A-0 system (1951–52) is often called an early compiler-related tool, and IBM's FORTRAN, led by John Backus, shipped in 1957 with a compiler good enough to convince working programmers that they no longer needed to write machine code by hand. The pipeline: text to tokens to tree to code A classical compiler is a pipeline, and each stage has one job. Lexing chops the character stream into tokens: numbers, names, operators, brackets. 12+x becomes the tokens 12, +, x. Parsing arranges the tokens into a tree that reflects the grammar. The tree is where precedence lives: in 2+3*4, the multiplication sits below the addition, so it happens first. Type checking and other analysis walk the tree and reject nonsense, like adding a number to a list. Optimisation rewrites the tree (or a later form) into an equivalent but cheaper one: computing 2*3 now rather than every time the program runs (constant folding). Code generation turns the tree into instructions for the target. Here we use a simple stack machine: push numbers, then apply operations to the top of the stack. The tree is the most important idea. Once the program is a tree, an interpreter can walk it to compute the answer, and a compiler can walk it to print instructions. Same tree, two different walks. Try it: a tiny compiler Type an arithmetic expression using numbers, x, + - * / and brackets. Every stage is real code running in this page. For example, 2*3+x*(4+5) becomes the tree (+ (* 2 3) (* x (+ 4 5))); with x = 2 it evaluates to 24; constant folding rewrites it as (+ 6 (* x 9)), shortening the generated code from 9 instructions to 5. 2+3*4 (2+3)*4 2*3+x*(4+5) 10-4-3 Your expression x = 2 Optimiser off Constant folding on Notice what the type-checking and optimisation stages buy. Without a tree there is nowhere to ask "is this part constant?" or "does this add a number to text?". Real compilers do hundreds of such rewrites and work over several intermediate forms, but each is the same move: walk the structure, change it, keep the meaning. Types: catching mistakes before they run A type is a label on a value that says what you may do with it: you can add numbers, you cannot add a number to a calendar. Languages split by when they check. Static typing (Java, Rust, C, Go): types are checked before the program runs. A wrong combination is a compile error. Dynamic typing (Python, JavaScript, Ruby): values carry types, and the check happens when the line actually runs. A wrong combination is a runtime error, only if that line is reached. The debate is real, and both camps have a case. Static advocates point out that a whole class of mistakes disappears before shipping, that types document the code and make large refactors safer, and that tools can offer better autocompletion. Dynamic advocates point to quick experiments, shorter code and flexibility, and say good tests catch most of what types would. Evidence is mixed: one widely cited study (Gao, Bird and Barr, 2017) took real public JavaScript bugs and found that adding TypeScript or Flow annotations would have detected about 15% of them. The authors present that as a lower bound, because these were bugs that had survived testing and review; critics note it still means most bugs are not type errors. Both camps now converge somewhat: Python has optional type hints and JavaScript has TypeScript, an approach called gradual typing. The sharp way to see the difference is in how a bug hides. A static check looks at every line. A dynamic check, or a test, sees only the lines that run. chance a test run reaches the buggy line = 1/N   →   chance that k runs find it = 1 − (1 − 1/N)k Try it: where does the bug get caught? A type mistake sits on a line that only 1 run in N reaches. How likely is it that k test runs trigger it? If one run in 100 reaches the line, 50 test runs find it only about 39% of the time; a static type check finds it every time, before anything runs. The line runs on 1 in 100 runs Test runs: 50 This is the whole case for static types in one line: they check the rare path too. And the whole case against them: they only check the kinds of mistakes the type system can express, and they add ceremony. Neither replaces tests for logic errors. Memory: who cleans up? Programs make objects in memory and must give the space back. Languages have three broad answers. Manual: the programmer frees memory (C's malloc and free). It is fast and predictable, and the mistakes are costly: forget and you leak; free twice or use after freeing and you get crashes and security holes. Garbage collection: the runtime finds unreachable objects and reclaims them. John McCarthy introduced garbage collection around 1959 for Lisp. It is used by Java, Python, JavaScript, Go and many others. The costs are occasional pauses and some extra memory use, which good collectors work hard to hide. Ownership (Rust): each value has exactly one owner, and when the owner goes out of scope the value is dropped. The compiler checks this, so the program has no garbage collector and no manual free. Rust 1.0 was announced in May 2015. Rust's trick is that assignment moves a value, and the old name stops working: let s1 = String::from("hello"); let s2 = s1; // ownership moves to s2 println!("{}", s1); // compile error: borrow of moved value `s1` That error appears at compile time, not at 3 a.m. in production, and it is the price of Rust's guarantees: you must learn to think about who owns what. Garbage collectors come in flavours too. The simplest idea, reference counting, frees an object when nothing points at it. But two objects that point at each other keep each other alive forever. Tracing collectors instead start from the live variables (the roots), mark everything reachable, and sweep away the rest. Try it: who frees what? Two variables, list and cache, point into a small heap. Drop one, then see what each strategy reclaims. E and F point at each other. Reference counting frees D when cache is dropped but leaks the E-F cycle; a tracing collector frees D, E and F. Reference counting Tracing (mark and sweep) Drop listDrop cacheRun the collectorReset Paradigms: three ways to say the same thing A paradigm is a style of organising a program. Most languages support more than one. Imperative: a sequence of commands that change state. Variables are boxes you update. It maps directly onto how hardware works. Functional: build results by composing functions that take inputs and return outputs without changing anything else. Fewer surprises, and easier to run in parallel; state changes become explicit. Object-oriented: bundle data with the operations on it into objects that send each other messages. Good for modelling things that have identity and changing state, such as accounts and windows. None of them wins everywhere. Many large systems mix all three, and a graduate learns to pick the style that fits the problem and to recognise it in whatever language they meet. Try it: sum of the squares of the even numbers up to n Three programs, one answer. Each runs live. For n = 10 all three give 4 + 16 + 36 + 64 + 100 = 220. n = 10 Imperative Functional Object-oriented What a graduate just sees Every program is a tree before it is anything else; precedence and meaning live in the tree. "Compiled or interpreted" describes an implementation, and most real systems do some of each. A compiler error is a gift: a mistake found on the rare path, before a user finds it. Same syntax does not mean same semantics; 7 / 2 depends on the language. Memory has to be freed by someone: you, the runtime, or the compiler's ownership rules, and each choice has a price. Two objects pointing at each other defeat naive reference counting. Static versus dynamic typing is a trade-off argued by serious people, not a right answer. Imperative, functional and object-oriented are styles you can write in almost any language. Where it shows up next Theory of Computation (34/29): the grammars that parsers use are the same objects studied in that course (regular expressions for lexing, context-free grammars for parsing). Computer Architecture (34/25): the code generator's target is the instruction set; registers and the stack are real hardware. Software Engineering (34/31): type systems, linters and static analysers are how teams catch mistakes at scale. Computer Security (34/33): memory-safety bugs in manual-memory languages are a major source of vulnerabilities, which is one reason ownership-based languages exist. In the world: your editor's squiggles, a database's query planner, a spreadsheet's formulas and a browser's JavaScript engine are all small compilers. If you want to go deeper 📘 Compilers: Principles, Techniques, and Tools (the "Dragon Book", 2nd edition 2006), Aho, Lam, Sethi and Ullman: the classic university text, best for parsing theory. 📘 Engineering a Compiler, 3rd edition (2022), Keith Cooper and Linda Torczon: more modern, best for optimisation and code generation. 📘 Gentler: Crafting Interpreters by Robert Nystrom, free to read online. You build two complete interpreters, step by step. 🌐 Free courses: Stanford CS143 Compilers and MIT OpenCourseWare 6.035 Computer Language Engineering. The takeaway A programming language is syntax plus meaning, and a translator turns it into something a machine can run by lexing it, parsing it into a tree, checking it, improving it and generating code. The big design choices, when types are checked, who frees memory, how code is organised, are trade-offs with real costs on each side. Try this: next time your editor or a build tool shows an error, name the stage that found it: a bad character (lexing), a missing bracket (parsing), a wrong type (checking). Then see how often you can guess before you read the message. Sources: Aho, Lam, Sethi, Ullman, Compilers: Principles, Techniques, and Tools, 2nd ed., Pearson, 2006. K. Cooper and L. Torczon, Engineering a Compiler, 3rd ed., Morgan Kaufmann, 2022. R. Nystrom, Crafting Interpreters, 2021. Z. Gao, C. Bird and E. T. Barr, "To Type or Not to Type: Quantifying Detectable Bugs in JavaScript", ICSE 2017. The Rust Programming Language, chapter 4 "Understanding Ownership"; the Rust 1.0 announcement, 15 May 2015, on the Rust blog. Python documentation, "dis — Disassembler for Python bytecode". J. McCarthy, "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I", Communications of the ACM 3(4), 1960. Wikipedia entries on FORTRAN (first appeared 1957, John Backus and IBM) and the A-0 System (Grace Hopper, 1951–52) for dating. The C and Python outputs were run on the author's machine for this piece. Go deeper: 📘 Crafting Interpreters — Robert Nystrom (craftinginterpreters.com, free) 📘 Structure and Interpretation of Computer Programs — Abelson and Sussman (free online from MIT Press) 🌐 Stanford CS143 Compilers 🌐 The Rust Book: What is Ownership? Step 14. Theory of Computation: What Can and Cannot Be Computed --------------------------------------------------------------- Why: The limits: what no computer can ever do, and what is merely hard. Some questions no program can ever answer, and others it can answer only after the sun has burned out. Proving which is which is one of the strangest achievements of the twentieth century. Your code editor will warn you about an unused variable. It will not reliably warn you that your program never stops. For some loops it can tell; for others it cannot, and the surprise is that this is not a failing of today's editors. In 1936 it was proved that no program, however clever and however much time it is given, can look at every program and say whether it will finish. That is the opening of the theory of computation: a mathematical map of what machines can do at all, what they can do only slowly, and what they can never do. A graduate keeps the map for life. It tells them when to stop trying to build a perfect bug finder, and when a problem is "hard" in the specific, technical sense that decades of the best minds have not cracked it. The course in one box Who takes it: computer science majors in the third or fourth year, and many mathematics majors. What it is for: drawing the exact boundaries of computation: machines of increasing power, problems no machine can solve, and problems that are solvable but apparently very costly. Comes after: Discrete Mathematics (34/08) and Algorithms (34/24). Leads to: Programming Languages & Compilers (34/30), where automata and grammars become the front end of every compiler. What this piece gives you: you will not be able to prove a language is not context-free afterwards. You will see what a finite machine cannot count, why one proof ends the dream of a perfect bug detector, and what a quantum computer really does to all this. The library's Alan Turing: The Machine That Defined Computing (History-Makers 04) is the easier first read on the Turing machine, with an adding machine to step through; in Spanish, La máquina universal de Turing (es/21/15). This piece goes further. What "computable" means The theory starts by shrinking every question to a yes/no one: is this number prime? Does this string match? Does this program halt? A question is decidable if some program answers it correctly, always, in finite time, for every input. Not fast; just finishing and right. (If speed matters, that is the later half of the course.) But "some program" in which language? Here comes the quiet miracle. In 1936 Alonzo Church (with the lambda calculus) and Alan Turing (with his machines) gave two completely different definitions of "effectively calculable", and they turned out to describe exactly the same set of functions. Many later formalisms agree. The Church-Turing thesis says this set is what any step-by-step method can compute. It cannot be formally proved, because "any method" is an informal idea, but it has stood for ninety years, and some theorists simply treat it as the definition of computable. The rule a graduate remembers"Computable" means a Turing machine can do it. Your laptop, your phone and a supercomputer are all, in this sense, equivalent: they differ in speed, not in what they can ever compute. Finite automata and regular expressions: machines with no memory Start with the weakest useful computer: a finite automaton. It has a fixed handful of states (think of lights on a panel), reads its input one symbol at a time, and on each symbol moves to a state determined only by where it is and what it read. No tape, no counter, no scratch paper. At the end it says accept or reject. That is already more useful than it sounds. A turnstile, a vending machine's coin logic and the text matcher in your search box are automata. Stephen Kleene showed in 1951 that the languages such machines accept are exactly the ones you can describe with regular expressions: patterns built from letters, "or", "followed by" and "repeat". Ken Thompson built them into text editors in the late 1960s (first QED, then Unix's ed), which is where grep comes from. Interactive · Run a machine, compare with its regex Divisible by 3 (binary) Contains ab Even number of 1s Input Letters read0 States (the current one is filled; a tick means accepting) Example: the machine for "divisible by 3" keeps only the remainder so far, reading each new bit b as remainder = (2 × remainder + b) mod 3. On 110 (six) it ends at remainder 0 and accepts; on 101 (five) it ends at 2 and rejects. The regular expression ^(0|1(01*0)*1)*$ gives the same verdicts. The "divisible by 3" machine shows the trick of automata: it does not remember the number, only the remainder, three possible values. The limit is just as clear. A machine with k states can never tell apart more than k different histories. Ask it to check that a string has as many as as bs, anbn, and it would have to remember n, an unbounded number. No fixed number of states suffices. A practical footnote: the regex engines in programming languages are stronger than the theory's regular expressions (they add "backreferences"), and that extra power has a price. Some patterns can make a backtracking engine take exponential time, a real attack vector known as ReDoS. Grammars: nesting needs a stack To handle anbn or matching brackets, add one thing: a counter or, more generally, a stack. A machine with a stack (a pushdown automaton) recognises exactly what a context-free grammar generates. A grammar is a list of rewriting rules. For balanced brackets: S → ( S ) S or S → ε (the empty string). Start from S and keep rewriting. Interactive · Write a sentence with rules S → ( S ) SS → (nothing)Random derivationReset Now the other direction: how much must a checker remember? Example derivation: S ⇒ (S)S ⇒ ((S)S)S ⇒ (()S)S ... Every string it makes is balanced, and the string (()(())) needs a counter that reaches 3. Noam Chomsky described this ladder in 1956, and it has four rungs: regular (finite automata), context-free (stack), context-sensitive (a bounded tape) and unrestricted (a full Turing machine). Each contains the one below. anbn is context-free but not regular; anbncn is beyond context-free. Programming languages are specified by context-free grammars, which is why the compiler course (34/30) begins with them: parsing your code is turning a flat string back into the tree the grammar generated. Turing machines: adding a tape Give the machine an endless tape it can read, write and move along, and it stops being limited. That is a Turing machine, and the thesis above says it is as powerful as any computer can be. Nothing else is added: states, a tape, a head, a table of rules. Here is the proof that the tape matters. The machine below decides anbn, the language that defeats every finite automaton. Its method is what a person would do with a pencil: cross off the first a (mark it X), run right to the first unpaired b (mark it Y), return left to the X, and repeat. If every a and b are crossed off together, accept. Interactive · A Turing machine that counts aabbaaabbbaabbbabab Step0 Run on aabb, the machine accepts after 13 steps; on aaabbb after 25; on aabbb it rejects after 12; on abab it rejects after 4. Steps grow roughly with the square of n, because it re-walks the tape for every pair. A Turing machine can also read another machine's rule table off its own tape and imitate it. Turing called this the universal machine; it is the idea of a stored program, and every phone is one. The same fact sets up the next result. The halting problem: a proof you can say out loud Claim: no program H exists that, given any program P and input, always correctly answers "halts" or "loops forever". Here is the proof in words, in the style of Cantor's diagonal argument. Suppose H existed. Build a mischievous program D that takes a program as its input and asks H what that program does when fed its own text. If H says "halts", D loops forever. If H says "loops", D halts at once. Now run D on D. If it halts, then H said it loops, so H was wrong. If it loops, H said it halts, wrong again. Either way H is wrong about D, so no correct H exists. Interactive · The contrarian row Each row is a program, each column an input. Tap any cell to flip it between halts and loops, then watch the contrarian row. The contrarian does the opposite of program k on input k, so it differs from every row on the diagonal. A list of all programs therefore cannot contain it, yet it would be a program: a contradiction. Turing proved this in a paper that went to press in 1936 and appeared in 1937; he did not use the word "halting", which came from Martin Davis later. Church reached a closely related result for his own system a little earlier in 1936. The deeper consequence is Rice's theorem: every non-trivial question about what a program does (will it ever crash, will it ever print this word, does it compute the same thing as that other program?) is undecidable in general. What this does not say matters. Particular programs can be analysed, and good tools prove many programs terminate. And a computer with strictly finite memory does eventually repeat a state, so for it halting is decidable in principle, though the number of states is so astronomical that the fact is of no practical use. The result says: no one method handles all programs. P, NP and NP-completeness: easy to check, hard to find Now suppose the answer is computable, and the question is cost. P is the class of yes/no problems solvable in polynomial time (like n, n log n, n²): sorting, shortest paths, is this number prime. NP is the class where a proposed "yes" answer can be checked in polynomial time: the "N" is for "nondeterministic", an old way of saying "if you were handed a certificate". Every problem in P is in NP. The open question, P = NP?, asks whether checking is really easier than finding. Interactive · Checking against searching A formula over six true/false variables: 12 clauses, each needing at least one true literal. Set the variables to satisfy every clause. Search by brute force Variables in a bigger formula This formula has exactly 2 of its 64 assignments that work; trying them in order finds the first on the 34th try. At 60 variables brute force would need 260 tries, about 36.5 years at a billion a second. That formula is an instance of SAT, satisfiability: is there a setting of the variables that makes the whole formula true? Stephen Cook showed in 1971 (and Leonid Levin independently, in work published in 1973) that SAT is NP-complete: every problem in NP can be translated into it in polynomial time. That translation is called a reduction, and it is the theory's most useful move. If problem A reduces to problem B, then a fast method for B would give a fast method for A. A small reduction you can feel: in a friendship graph, a group of people who all know each other (a clique) is exactly a group of strangers in the opposite graph (an independent set). Solve one problem and you have solved the other. In 1972 Richard Karp used reductions to show that 21 well-known problems, including clique, vertex cover, the Hamiltonian circuit and knapsack, are all NP-complete. Many hundreds more have followed. The rule a graduate remembersNP-complete problems are the hardest in NP in the sense that all of NP reduces to them. One fast algorithm for any of them would give a fast algorithm for all of them, so P would equal NP. Nobody has found one, and nobody has proved none exists; the Clay Mathematics Institute offers US$1,000,000 for a proof either way. Opinion is lopsided but it is opinion. In a poll of researchers by William Gasarch in 2018, about 88% believed P is not equal to NP. Practically, NP-complete does not mean hopeless: industrial SAT solvers handle enormous real instances, and heuristics give good answers. It means no known method is fast on every instance, so engineers stop hunting for a perfect one and settle for good enough. What quantum computers do and do not change It is tempting to say a quantum computer tries every answer at once. That is wrong, and it matters. A quantum computer works on qubits, whose states combine as amplitudes that can cancel or reinforce. A clever algorithm arranges the cancellation so that wrong answers fade and the right one is likely when you finally measure. A measurement returns a single result, so there is no free "all at once". Interactive · How big is Grover's speed-up? Searching an unstructured space of 2n possibilities for the one that works. Bits of search space n For n = 64: about 9.2×1018 classical tries on average against about 3.4×109 quantum queries. The speed-up is large but the quantum count is still the square root. QuestionWhat quantum changes Is more computable than before?No. A classical computer can simulate a quantum one, just exponentially slowly. The halting problem stays undecidable. Factoring large numbersShor's algorithm (1994) does it in polynomial time, which would break RSA and Diffie-Hellman. It needs a large, error-corrected machine that does not yet exist. Unstructured searchGrover's algorithm (1996): a square-root speed-up, proven the best possible for this kind of search. Big, not magical. NP-complete problemsNo known efficient quantum method. Whether one exists is open; most researchers suspect not. So the honest summary: quantum computers do not change what is computable, only how fast certain problems can be solved, and the problems with large known gains (factoring, simulating quantum physics) are specific, not "everything". The classical definition of efficient computing, the "extended" Church-Turing thesis, is the part under threat, not the original. On the hardware, Craig Gidney estimated in 2025 that factoring a 2048-bit RSA number would need fewer than a million noisy qubits running for under a week, noting that today's devices have at most a few thousand noisy qubits and none is fully error-corrected. That is an estimate, and the engineering is hard. What a graduate just sees Every computer, big or small, can compute the same set of things; only speed differs. A machine with finite memory cannot count without bound; nesting needs a stack. Languages form a ladder: regular, context-free, context-sensitive, unrestricted. Self-reference can be turned into a proof: the halting problem is undecidable. Any non-trivial question about what a program does is undecidable in general (Rice). Easy to check does not mean easy to find; that gap is P versus NP. A reduction transfers difficulty: "if I could solve B, I could solve A". Quantum computers are fast at some structured problems, not at everything, and they compute nothing new. Where it shows up next Compilers (34/30): regular expressions tokenise your code and context-free grammars parse it. Algorithms (34/24) looks back: the salesman's tour and 2n blow-ups are exactly NP-hard territory. Security (34/33): modern cryptography leans on problems believed to be hard, which is why Shor's algorithm is such news. Software engineering (34/31): static analysers and type checkers are deliberately approximate, because Rice's theorem forbids exactness. In life: the search box, the spell-checker, logistics planners and chip designers all use SAT solvers or heuristics for NP-complete problems. If you want to go deeper 📘 Textbook: Michael Sipser, Introduction to the Theory of Computation (Cengage, 3rd ed.): the standard text, famous for its clarity. 📘 Textbook: Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (4th ed.), the NP-completeness chapter. 📘 Gentler: Scott Aaronson, Quantum Computing since Democritus (Cambridge University Press, 2013): an entertaining tour from Turing to quantum. 🌐 Free course: MIT OpenCourseWare 6.045J / 18.400J, Automata, Computability, and Complexity (Spring 2011, taught by Scott Aaronson), with lecture notes and problem sets. The takeaway Computation has exact limits. Finite automata cannot count, a stack handles nesting, and a tape gives everything computable. Self-reference proves the halting problem has no solution, which rules out perfect program checkers. Among solvable problems, P versus NP asks whether finding is ever as easy as checking, and quantum computers speed up special cases without making the impossible possible. Try this: next time a tool says "could not determine", remember it may be a case of Rice's theorem, not laziness. Then in the SAT demo, set the six switches to the working answer, and slide the variable count to find the size where brute force takes longer than a human life. Sources & Further Reading Sources. Textbook material: Sipser, Introduction to the Theory of Computation. Kleene's regular events (1951) and Thompson's use in QED/ed (1968): Wikipedia, "Regular expression". Chomsky, "Three models for the description of language" (1956): Wikipedia, "Chomsky hierarchy". Church-Turing thesis cannot be formally proven: Wikipedia, "Church-Turing thesis". Halting problem dates and the term's origin with Martin Davis: Wikipedia, "Halting problem". Cook 1971, Levin 1973, Clay prize US$1,000,000 and the Gasarch poll (88% in 2018): Wikipedia, "P versus NP problem". Karp, "Reducibility Among Combinatorial Problems" (1972): Wikipedia, "Karp's 21 NP-complete problems". Shor (1994) and Grover (1996): Wikipedia, "Quantum computing". BQP contained in PSPACE, relation to NP unknown: Wikipedia, "BQP". Gidney, "How to factor 2048 bit RSA integers with less than a million noisy qubits", arXiv:2505.15917 (May 2025). All machine runs and counts in the demos were computed and cross-checked in code. 📘 Introduction to the Theory of Computation, Michael Sipser (author's page) 🌐 MIT OpenCourseWare 6.045J (free) 📘 Quantum Computing since Democritus, Scott Aaronson 🌐 Clay Mathematics Institute: P vs NP Step 15. Machine Learning: Programs That Write Their Own Rules -------------------------------------------------------------- Why: Programs that learn their behaviour from data. Nobody wrote the rule that tells a spam message from your mother's email. A program found it by looking at examples, and everything in the field is about whether you can trust what it found. Your phone groups your photos by person. Your inbox hides the lottery scams. A bank flags a card payment at 3 a.m. from another continent. Try to write the rules for any of these by hand and you hit a wall within an hour: what, exactly, makes a face a face, or a message spam? Machine learning gives up on writing the rules. Instead you show a program thousands of labelled examples and let it adjust itself until it gets them right. This is powerful, and it quietly changes the questions you have to ask. The hard part is no longer "what is the rule?" but "how do I know the rule it found will work tomorrow, on people it has never seen?" That question, and a handful of simple tools for answering it, are what a graduate of a machine-learning course keeps for life. The course in one box Who takes it: Computer Science majors, usually in year 4; also statistics, data science and engineering students. What it's for: building programs that learn their behaviour from data, and judging honestly whether they work. Comes after: Linear Algebra (34/04), Probability & Statistics (34/05), Multivariable Calculus (34/02) and Algorithms (34/24). Leads to: no later subject in this series lists it as a prerequisite; it feeds research and careers in AI, and touches Computer Security (34/33), where learning systems are both tools and targets, and Databases (34/28), where the training data lives. Honest line: you won't train a modern language model after this; you will understand the training loop all of them share. For the AI story and a tour of language models, read Artificial Intelligence (29/01) and How Large Language Models Actually Work (29/02) first; this piece goes underneath them. Learning from data, and the data you hold back Take a toy problem. Each email gets a "suspicious words" score, and you must decide spam or not. You could write a rule by hand: spam if the score is above 3. But why 3? Better: try every threshold on a set of labelled examples and keep the one that gets the most right. That, in miniature, is training: a rule with an adjustable knob, a way to score the rule on data, and a search for the best setting of the knob. Here is the trap. The setting that fits the examples you used will almost always look better on those examples than on fresh ones, because you tuned it to them. So practitioners split their data three ways: Training set: the examples the model adjusts itself on. Validation set: held back to compare choices (which model, which settings). Test set: touched once, at the very end, to estimate how it will do in the real world. If you keep tuning against it, it stops being a test. Try it: pick the threshold, then meet fresh data Filled dots are 30 training emails (orange = spam, blue = not spam); hollow squares are 20 held-back ones the rule never saw. All the data are made up for this demo. The best threshold on the training emails is 3.3, which gets 93% of them right, but only 85% of the 20 held-back emails. Threshold: spam if score > 3.0 Let the data choose Linear regression and gradient descent Many problems are about predicting a number. The simplest model is a straight line: prediction = w × input + b. The two knobs are the slope w and the intercept b. To score a line, measure how far it misses each point, square the misses so that over and under both count, and average them: the mean squared error (MSE). The method of least squares was first published by Adrien-Marie Legendre in 1805; Carl Friedrich Gauss claimed to have used it earlier, which started a priority dispute. For a line there is a formula for the best w and b. For huge models there is not, and we use the idea that carries the whole field: gradient descent. Stand on the error surface, feel which way is steepest downhill (the gradient, from Multivariable Calculus 34/02), and take a small step that way. Repeat. Augustin-Louis Cauchy suggested the method in 1847. new w = w − η × (slope of the error with respect to w)    same for bη ("eta") is the learning rate, the size of each step The learning rate is a real trade-off: too small and you crawl; too large and you overshoot the valley and bounce out of it. Try it. The 12 points below are made up around a line; the least-squares answer is w = 2.465, b = 8.289, with MSE 2.58. Try it: fit a line by rolling downhill Start from w = 0, b = 0 and press Step. Choose a learning rate. With η = 0.01, 200 steps reach w = 2.89, b = 5.79 and MSE 4.37, still on the way down; with η = 0.04 the steps are too big and the error explodes instead of shrinking. η = 0.001 η = 0.01 η = 0.03 η = 0.04 StepRun 20 stepsReset Overfitting and underfitting A line is a rigid model. A more flexible one, say a polynomial with more bends, can follow the data more closely. Flexibility is a dial, and both ends of it fail: Underfitting: the model is too simple to capture the pattern. It is wrong on the training data and wrong on new data. Overfitting: the model is so flexible that it memorises the noise in the training data. It is nearly perfect there and bad on new data. This is why the validation set exists. Training error only ever goes down as you add flexibility. Validation error goes down, then comes back up, and the bottom of that U is where you stop. Training error tells you how well the model remembers. Validation error tells you how well it learned. Try it: turn the complexity dial The true pattern is a smooth wave; the 12 filled dots are noisy samples of it, and the 40 hollow dots are fresh noisy samples used only to judge. The curve is a polynomial fitted to the filled dots. A degree-1 line misses the wave (errors 0.54 and 0.43), degree 3 does best on fresh data (0.28 train, 0.35 validation), degree 9 hugs the 12 dots (0.14) but is far worse on fresh ones (1.02). Polynomial degree: 3 Classification and neural networks as layered functions Classification predicts a label rather than a number: spam or not, which digit, which animal. A simple classifier computes a weighted sum of the inputs and squashes it into a probability between 0 and 1, and its decision boundary is a straight line (or plane). That is enough when the classes can be separated by a line. Some problems cannot. The classic example is XOR: the answer is 1 when exactly one of the two inputs is 1. No single straight line separates the four cases correctly. In the late 1960s Marvin Minsky and Seymour Papert's book Perceptrons analysed exactly this kind of limit for single-layer networks, and is often credited with helping to cool interest in neural networks for years (historians debate how much). The escape is to stack models. A neural network is a chain of simple functions: each layer takes a weighted sum of its inputs, applies a bend (a non-linear function such as tanh), and hands the result to the next layer. One layer draws a line; a layer built on top of lines can carve out regions that no single line can. Training a network means finding good weights, and the tool is backpropagation, which in words goes: Run an example forward through the layers and get a prediction. Measure how wrong it was. Walk backwards, layer by layer, asking each weight "how much of this error was your fault?", using the chain rule from calculus. Nudge every weight a little in the direction that reduces the error. Repeat on the next example. The idea was derived several times; the 1986 Nature paper by David Rumelhart, Geoffrey Hinton and Ronald Williams is the one that made it popular. Gradient descent plus backpropagation, run at scale, is still how neural networks are trained, including the large language models in 29/02. Try it: teach a network XOR Four training cases. Choose how many hidden units the network has, then slide through training steps (always the same starting weights). The picture shows the network's output over the plane. With no hidden layer, the best the model can do is output about 0.5 for every case (loss 0.693) and it stays stuck; with 4 hidden units, 500 steps already get all four right (loss 0.010). No hidden layer 2 hidden units 4 hidden units Training steps: 500 Evaluation: accuracy is not enough "The model is 99% accurate" can be meaningless. Imagine a rare disease affecting 1% of 10,000 people. A model that always says "healthy" is 99% accurate and finds nobody. Count outcomes instead: true positives (TP), false positives (FP), true negatives (TN), false negatives (FN). precision = TP / (TP + FP): of those flagged, how many were rightrecall = TP / (TP + FN): of those who were sick, how many were found The two pull against each other. A model that flags only when it is certain has high precision and low recall; one that flags at the slightest hint has high recall and swamps you with false alarms. Where to set the threshold depends on what each error costs: missing a cancer is not like sending a good email to the spam folder. And when the real condition is rare, even a decent test produces mostly false alarms. Try it: a test with a threshold 10,000 people. The test gives a score; sick people score on average 2 standard deviations higher than healthy ones (a decent test, invented for this demo). Move the threshold and the prevalence. At 1% prevalence and a threshold of 1.0, the test finds 84 of 100 sick people (recall 84%) but raises 1,571 false alarms, so only 5% of those flagged are actually sick. 1% are sick 10% 50% Flag when score > 1.0 Bias: the model learns the data you gave it A model has no opinion about fairness. It finds whatever pattern best fits the examples it was shown, including patterns in who is in the examples. If one group is a small part of the training data, the model's single rule is tuned to the majority and does worse on the rest. This is not hypothetical. In the 2018 Gender Shades study, Joy Buolamwini and Timnit Gebru found that the two benchmark face datasets they examined were 79.6% (IJB-A) and 86.2% (Adience) lighter-skinned subjects, and that three commercial gender-classification systems misclassified darker-skinned women at error rates of up to 34.7%, against at most 0.8% for lighter-skinned men. Try it: who is in the training data? Two groups, A and B, whose scores sit on different scales (an invented example). The model picks the one threshold that gets the most training cases right. Change how much of the training data is group B. With 2% of the data from group B the model is 84% accurate for A but 74% for B; at 50% both groups get 81%. Group B share of training data: 2% More data from the same source does not fix this; different data, or a model checked group by group, can. Bias can also come from the labels (past human decisions the model copies) and from how a system is used. Checking performance for each group, not just on average, is the habit to keep. The same discipline applies to the newest systems. The Stanford HAI AI Index 2026 report describes a "jagged frontier": one model earned a gold medal at the International Mathematical Olympiad, yet the top model it tested read analog clocks correctly only 50.1% of the time. An average score, or a headline result, says little about how a model will do on the case in front of you; that has to be measured. What a graduate just sees Learning means tuning knobs to fit examples; the rule is found, not written. Performance on the data you trained on is not evidence. Only data held back is. Gradient descent is "step downhill"; the learning rate is the step size and it matters. Too simple and too flexible both fail; validation error has a U shape. A network is stacked simple functions, and backpropagation is the chain rule applied layer by layer. Accuracy hides rare cases; ask for precision, recall and the cost of each mistake. When a thing is rare, most alarms are false alarms. A model is only as fair as its data; check each group, not the average. Where it shows up next Linear Algebra (34/04) and Multivariable Calculus (34/02): weights are vectors and matrices, and the gradients are partial derivatives. Probability & Statistics (34/05): the train/test idea is the statistician's out-of-sample check, and precision is Bayes' theorem in disguise. Algorithms (34/24): training is optimisation, and its cost is why hardware like GPUs matters (see 29/12). Computer Security (34/33): learning systems can be fooled by crafted inputs and poisoned data. In the world: fraud screening, search ranking, recommendations, translation, medical imaging, and the chatbots in 29/02. As of the 2025 Stanford AI Index, the compute used to train notable models was reported to be doubling roughly every five months, which is why training is now an industrial activity. If you want to go deeper 📘 An Introduction to Statistical Learning (James, Witten, Hastie, Tibshirani; 2nd edition 2021, with a Python edition in 2023): free from the authors, the standard first university text; clear and light on maths. 📘 Deep Learning (Goodfellow, Bengio, Courville, MIT Press 2016): the standard graduate text on neural networks, free to read online. ▶️ Gentler: 3Blue1Brown's neural-networks video series builds the ideas above with pictures. 🌐 Free courses: MIT OpenCourseWare 6.036 Introduction to Machine Learning and Stanford CS229. The takeaway Machine learning replaces hand-written rules with knobs tuned to examples, using gradient descent to find the settings. Everything else is about trust: hold data back to measure honestly, find the middle between too simple and too flexible, stack functions when a line is not enough, ask which errors matter, and check who is in the data. Try this: the next time you read "an AI that is 95% accurate", ask four questions. Accurate on what data? How rare is the thing it looks for? What does each kind of mistake cost? And has anyone checked it for the group you belong to? Sources: A.-M. Legendre (1805) and C. F. Gauss on least squares (priority dispute, as summarised in standard histories of statistics); A.-L. Cauchy (1847) on gradient descent; M. Minsky and S. Papert, Perceptrons, MIT Press, 1969; D. Rumelhart, G. Hinton and R. Williams, "Learning representations by back-propagating errors", Nature 323, 1986; J. Buolamwini and T. Gebru, "Gender Shades: Intersectional Accuracy Disparities in Commercial Gender Classification", Proceedings of Machine Learning Research 81, 2018; Stanford HAI, AI Index Report 2025 (training compute doubling about every five months) and AI Index Report 2026 (the "jagged frontier": IMO gold, 50.1% on analog clocks); G. James, D. Witten, T. Hastie, R. Tibshirani, An Introduction to Statistical Learning. All datasets in the demos are invented, and every number they show was computed and cross-checked for this piece. Go deeper: 📘 An Introduction to Statistical Learning (statlearning.com, free) 📘 Deep Learning — Goodfellow, Bengio, Courville (deeplearningbook.org, free online) ▶️ 3Blue1Brown: Neural Networks 🌐 MIT OCW 6.036 Introduction to Machine Learning Step 16. Computer Security: Thinking Like an Attacker ----------------------------------------------------- Why: Thinking like an attacker so systems survive real ones. Systems fail at the cheapest door. Security is the habit of finding it first. A note on safety and law: this piece explains how attacks work so that people can defend against them. It gives no recipes. Only ever test systems you own or have written permission to test; breaking into other people's computers is a crime in most places. In 2017 the credit bureau Equifax lost the names, birth dates and Social Security numbers of about 148 million people. No spy movie was involved. A known flaw in a piece of software had a fix available for months, and the fix had not been installed. That is the first thing a security graduate learns to see: most disasters are not brilliant. They are a door that someone forgot, a password that was never changed, a trust that was never checked. The second thing is harder. You cannot defend a system by asking what could go wrong. You have to ask what a patient, lazy, clever stranger would do first. The course in one box Who takes it: computer science students, usually in the last year; security is also taught to engineers whose machines are now connected. What it is for: building and running systems that stay trustworthy when someone is actively trying to make them fail. Comes after: Operating Systems (34/26) and Computer Networks (34/27). Leads to: nothing on the map; it is one of the last subjects of the Computer Science path. It touches Software Engineering (34/31), because most breaches are engineering failures, and the library's Cryptography piece (12/09), which is an easier first read on the maths and which this piece goes beyond. What this piece gives you, and what it doesn't: you won't be able to test or secure a real system. You will see why an attacker takes the cheapest door, why a long password beats a clever one, and why one layer is never enough. What "secure" means: confidentiality, integrity, availability Security people check three properties, called the CIA triad. Confidentiality: only the right people can read it. Integrity: it cannot be changed without being noticed. Availability: it works when needed. Each can be attacked on its own. A leaked database breaks confidentiality. A forged bank transfer breaks integrity. A ransomware attack, which locks your files until you pay, breaks availability, and denial-of-service floods do the same by overwhelming a site with traffic. The triad also reveals trade-offs. A system that nobody can read is perfectly confidential and completely useless. Making something more available (more copies, more access points) can make it less confidential. Good security is not "as locked down as possible". It is choosing which property matters most for each asset, then spending effort there. Thinking like an attacker: threat modelling Threat modelling is the habit of asking four questions before building: what are we protecting, who might want it, how could they reach it, and what will we do about it? Microsoft engineers Loren Kohnfelder and Praerit Garg described a well-known checklist in 1999, called STRIDE: spoofing (pretending to be someone), tampering, repudiation (denying you did something), information disclosure, denial of service, and elevation of privilege (gaining powers you shouldn't have). The most useful single idea comes from drawing the possible paths to the goal and noticing that an attacker is lazy. They do not attack your strongest lock. They take the cheapest path. Your system is as strong as its easiest door. Interactive · The cheapest door The goal: read Sam's email. Each slider is how much effort that route costs an attacker (1 = trivial, 10 = practically impossible). The numbers are invented; the logic is not. Strengthen a door and see whether it helps. Raise the cost of guessing the password to 10 and nothing changes: the attacker was never going to guess. The money is better spent on the cheapest door, and here it is the human one. This is why security engineers talk about people as a part of the system, not as the problem. Passwords: hashing, salt and why length wins A well-built site does not store your password. It stores a hash: the output of a one-way function, a scrambled fingerprint from which the password can't be run backwards. When you log in, it hashes what you typed and compares. If the database leaks, the attacker gets fingerprints, not passwords, and has to guess: hash a candidate, see if it matches. Two details make or break that. First, the hash must be slow on purpose. General-purpose hashes such as SHA-256 or MD5 are designed to be fast, which helps attackers test billions of guesses a second on graphics cards. OWASP's guidance names purpose-built password hashes (Argon2id first, then scrypt, bcrypt and PBKDF2) that are slow and use lots of memory. Second, each password needs a salt: a random value, unique to each user, mixed in before hashing. Without it, identical passwords give identical hashes, and an attacker can precompute a table of common passwords and look up every user at once. Interactive · A leaked table of hashes Three users. Alice and Bob chose the same password. The values are real SHA-256 hashes computed in your browser. (A real site would use Argon2id or bcrypt; SHA-256 is used here only because it is easy to show.) The attacker has a lookup table of the ten most common passwords. The second thing that matters is length. The number of possible secrets is the size of the alphabet raised to the length, so adding characters multiplies the work. But this only holds when the secret is random. People are not random, which is why attackers try breached passwords and dictionaries before brute force. It is also why NIST's revised guidance (SP 800-63B, revision 4) calls for checking new passwords against lists of common and breached ones, for at least 15 characters when a password is the only factor, and against forced composition rules and routine expiry. Interactive · How long would guessing take? For a truly random secret, the average attacker finds it after trying half the possibilities. The rates are round orders of magnitude, not measurements of one machine: public benchmarks put a single high-end graphics card at roughly 10^11 guesses a second for fast MD5-type hashes, while slow password hashes are many orders of magnitude lower. What the secret is made of Length What the attacker has With these settings, 8 random keyboard characters fall to a stolen fast-hash file in about 8.5 hours on average, but 12 take around 75,000 years. Six random common words, a passphrase you can actually remember, are about as strong as 12 random symbols. Against a slow hash, even the 8 characters last about 9,700 years. Length and slow hashing together are doing the work. The last piece is multi-factor authentication: proving you are you with two of three things: something you know (a password), something you have (a phone or hardware key), something you are (a fingerprint). Then a stolen password alone is no longer enough. Not all second factors are equal. Codes sent by text or typed from an app can be relayed by a fake site in real time. Methods based on FIDO2/WebAuthn, such as passkeys and hardware keys, tie the login to the real site's address, so a lookalike can't use them. Encryption: in transit, at rest, and who holds the key Encryption turns data into something unreadable without a key. Symmetric encryption (AES is the standard) uses one shared key for both locking and unlocking, and is very fast. Public-key encryption (see Cryptography, 12/09) uses a public key to lock and a private one to unlock, which solves the problem of sharing a key with a stranger, but is much slower. Real systems use both: public-key maths to agree on a secret, symmetric encryption to carry the data. That is exactly what happens when your browser shows a padlock. TLS, the protocol behind that padlock, is defined for its current version 1.3 in RFC 8446 (2018). Step through what happens in the first fraction of a second. Interactive · Inside the padlock Encryption in transit protects data while it moves, from the cafe wifi owner or anyone on the path. Encryption at rest protects stored data, such as a laptop disk or a database file. They defend against different attackers, and neither defends against everything: AttackerIn transit (TLS)At rest (disk) Reads traffic on public wifiStoppedNo effect Steals a powered-off laptopNo effectStopped Has taken over the server while it runsNo effectUsually no effect: the system holds the key to use the data Tricks you into logging in on a fake siteNo effect: the connection to the fake is encryptedNo effect The pattern: encryption is only as good as the place the key lives. A locked safe with the key taped to it is not a safe. Much of practical security is key management. The common ways in Attackers have a short list of favourite moves, which security courses teach by class, not by tool. Social engineering and phishing attack the person, not the machine: a message that looks like it comes from your bank, your boss or IT, urging you to hand over a password or click. It works because it uses urgency and trust, not technical flaws. Injection happens when a program builds a command by gluing in text from a user, and the system cannot tell where the programmer's instructions end and the user's data begins. The cure is to keep them apart. See it with a harmless name. Interactive · Data or command? A site looks up a user by name in its database. Type a name, or pick one. Name Buffer overflow and its relatives are memory errors. In languages like C, a program that copies more data into a fixed-size space than fits spills into neighbouring memory, which can corrupt the program or even change what it does. The defences are checking lengths, using memory-safe languages, and operating-system protections (the subject of Operating Systems, 34/26). Misconfiguration is the plainest class: a default password left on, a storage bucket left public, a test account never removed. Coverage of OWASP's 2025 Top 10 list reports that security misconfiguration rose to second place. Least privilege and defence in depth Two principles, both old, do much of the work. Saltzer and Schroeder's 1975 paper "The Protection of Information in Computer Systems" set out design principles still taught today, including that access should be denied unless explicitly granted (fail-safe defaults), that every access should be checked (complete mediation), that designs should be simple (economy of mechanism), and that security should not depend on keeping the design secret (open design). Least privilege, the idea that every program and person should have only the access they need, belongs with them. If a clerk's account is stolen, the thief gets a clerk's powers, not the whole company's. Defence in depth means stacking independent protections so that one failure is not fatal. If each layer stops 70% of attacks, three layers let through 0.3 × 0.3 × 0.3 = 2.7%. But the arithmetic hides a trap, and it is the same one as in Systems Engineering (34/22), where two redundant units running identical software failed together. If some attacks go around every layer at once (a stolen administrator password, an insider), the layers are not independent. Interactive · Layers that aren't independent Number of layers Share of attacks each layer stops Share of attacks that bypass every layer With three layers at 70% each and a 5% common weakness, about 7.6% get through, nearly three times the independent figure. Adding a fourth layer barely helps; closing the shared weakness does. That is why security teams hunt for the single point that all layers depend on. How real breaches happened Each case below is well documented, and each is less exotic than it sounds. CaseWhat happenedThe lesson Morris worm, 1988On 2 November 1988 a Cornell graduate student released a self-copying program. It used a memory overflow in the finger service, a debugging hole in the mail program, trusted logins and weak passwords. A flaw in how often it re-infected machines made them unusable.Several small flaws combined; a bug in the attacker's own code did the damage. It led to the creation of CERT/CC at Carnegie Mellon. Heartbleed, 2014OpenSSL's heartbeat feature did not check the length of a request, so a caller could read up to 64 KiB of the server's memory per request, which could include keys and passwords. The flawed code had shipped for about two years (CVE-2014-0160).A missing bounds check in a trusted library. Even the encryption layer is software. Equifax, 2017Attackers used a known flaw in Apache Struts for which a patch had been released on 7 March 2017. About 147.9 million Americans were affected, and the breach went unnoticed for 76 days, until an expired certificate on a monitoring tool was renewed.Patching and monitoring are security controls. In 2019 Equifax agreed to pay at least $575 million in settlements. Colonial Pipeline, 2021Reporting says attackers used a compromised password for an old VPN account with no multi-factor authentication. The company shut down pipeline operations as a precaution; the ransomware hit business systems.One account without a second factor was the door. The harm was to availability. Notice what the lessons have in common: patching, passwords, a missing check, an unmonitored door. The security course teaches the cryptography and the attacks, but what graduates remember is that organisations fail at the basics, and that attackers are happy to wait for them to. What a graduate just sees Security is three properties (confidentiality, integrity, availability), and they pull against each other. The attacker takes the cheapest door, so the weakest link is the only one that counts. A password is never stored; a slow, salted hash of it is, and long beats clever. Encryption is only as good as the place its key lives. If a program mixes user data into its commands, someone will eventually use it as a command. Give every person and program the least access that works. Layers are only independent if they don't share a weakness. Most breaches are boring: unpatched software, reused passwords, no second factor. Assume breach, and make sure you can detect it. Where it shows up next Operating Systems (34/26) and Computer Networks (34/27) are the ground security stands on: permissions, memory protection, protocols. The padlock above is a networking story. Software Engineering (34/31): code review, testing and postmortems are the main defences against the flaws above. Systems Engineering (34/22): the same thinking applied to hardware: interfaces, single points of failure, redundancy that isn't independent. Cryptography (12/09) for the maths of the keys; Databases (34/28) for where injection and access control meet. In the real world: security engineer, penetration tester, incident responder, and every developer who writes a login form. If you want to go deeper 📘 Computer Security: Principles and Practice, William Stallings and Lawrie Brown (Pearson, 4th ed., 2018): a standard university textbook. 📘 Security Engineering, Ross Anderson (Wiley, 3rd ed., 2020): the broad, readable bible of the field, available from the author's site. 📘 The Cuckoo's Egg, Cliff Stoll (Doubleday, 1989): a gentle true story of tracking an intruder through a university network. 🌐 MIT OpenCourseWare 6.858, Computer Systems Security (Fall 2014, Nickolai Zeldovich): free lectures, notes and labs; graduate level, so it is demanding. 🌐 Harvard's CS50 Introduction to Cybersecurity: a free, beginner-friendly online course. The takeaway Security is the discipline of keeping a system trustworthy against someone who is trying to break it. Think in confidentiality, integrity and availability; model the attacker and find the cheapest door; store passwords as slow, salted hashes and make them long; use encryption but guard the key; give everything the least privilege; stack independent layers; and remember that most real breaches were failures of basics. Try this: turn on multi-factor authentication for your email account (ideally with a passkey or a hardware key), then look at what happens if you forget a password. Is there a recovery path that is easier for an attacker than the password you just protected? Sources & Further Reading Sources. STRIDE: Kohnfelder and Garg, Microsoft, 1999 (Wikipedia, "STRIDE model"). Password storage and salting: OWASP Password Storage Cheat Sheet. Password policy: NIST SP 800-63B (revision 4). Phishing-resistant MFA: CISA fact sheet and W3C WebAuthn. TLS 1.3: RFC 8446 (August 2018). Saltzer and Schroeder, 1975. Misconfiguration ranking: OWASP Top 10:2025 (as reported by secondary coverage). Morris worm: Wikipedia, "Morris worm". Heartbleed: Wikipedia, "Heartbleed". Equifax: Wikipedia, "2017 Equifax data breach". Colonial Pipeline: Wikipedia, "Colonial Pipeline ransomware attack". Guess rates: public hashcat benchmark posts (MD5 about 1.5 × 10^11 per second on one RTX 4090); the rates in the interactive are illustrative round numbers. Computed in node: bits and average guess times; SHA-256 implementation checked against the Node crypto library on six test strings; layer arithmetic. 🌐 OWASP Password Storage Cheat Sheet 🌐 NIST SP 800-63B: Authentication guidance 🌐 RFC 8446: TLS 1.3 🌐 Ross Anderson: Security Engineering 🌐 MIT OpenCourseWare 6.858: Computer Systems Security Step 17. Multivariable Calculus: Calculus on a Landscape -------------------------------------------------------- Why: The gradients that train every neural network are multivariable calculus. A raindrop on a hillside picks the steepest way down without thinking. The arrow it follows is the same one that trains every neural network and drives heat through a metal plate. Stand on a hillside with a map. Height depends on two things at once: how far east you are and how far north. Single-variable calculus handles one input at a time. The hillside needs a new question: of all the directions I could step, which one rises fastest? Almost nothing real depends on one number. Temperature in an engine block depends on position in three dimensions. The error of a language model depends on billions of adjustable weights. Air pressure depends on place and time. This course takes the slope-and-area ideas of Calculus I (34/01) and lets them live in more than one dimension. Surprisingly little new is needed: one new arrow, the gradient, and one new accounting rule, the idea that what flows out of a region is what is made inside it. The course in one box Who takes it: second-year Mechanical & Aerospace Engineering students; Computer Science students meet it in year 4 when machine learning needs it. What it is for: calculating change and totals when many things vary at once. Comes after: Calculus I (34/01). Leads to: Physics II: Electricity & Magnetism (34/07), Fluid Mechanics (34/15), Machine Learning (34/32), and through them Heat Transfer (34/16) and Propulsion (34/21). Honest line: you will not be able to grind through a surface integral after this. You will see why a gradient points uphill, why training an AI is "just" rolling downhill, and what the big theorems say in plain words. Two inputs make a landscape, and a partial derivative is one slope A function of two inputs is a surface: height above each point of a map. Engineers draw it the way hikers do, with contour lines: closely spaced lines mean steep ground, widely spaced lines mean gentle ground. To ask "how steep?" you must say in which direction. Walk due east and note the slope: that is the partial derivative with respect to x, written ∂f/∂x. Hold east still and walk north: that is ∂f/∂y. The recipe is simple: treat every other variable as frozen and differentiate as before. ∂f/∂x = slope of f as only x changes, with y held still The landscape below has a tall hill near (1, 1) and a lower one near (−1.2, −0.8). Drag the point on the map (or use the sliders). The cyan arrow shows the slope eastward and the green arrow the slope northward; a leftward or downward arrow means the ground falls in that direction. Interactive · Walk the map East–west position x North–south position y At the starting point (−0.2, 0.3) the height is 0.684, the eastward slope +0.621 and the northward slope +0.226: the ground rises both ways, more steeply towards the east. The gradient points straight uphill Put the two partial slopes together as one arrow, east component first: that is the gradient, written ∇f. It has a beautiful property: it points in the direction of steepest ascent, and its length is how steep that is. Step in any other direction and the slope is the gradient's length times the cosine of the angle between your step and the arrow. Straight along it, cosine is 1: the most you can get. Sideways to it, cosine is 0: you walk along a contour and stay level. slope in direction u = ∇f · u = |∇f| cos(angle) Two consequences follow. The gradient is always perpendicular to the contour line through that point, which is why water runs across contours, not along them. And the same arrow governs heat: in Fourier's law, heat flows down the temperature gradient, from hot to cold, at a rate proportional to its steepness. Many diffusion laws have this shape: flow follows the negative gradient. Interactive · Which way is uphill? Direction you step (0° = east, 90° = north) Turn to the gradient Turn the pink direction until the slope is largest: it lines up with the orange arrow. Turn it 90° from the arrow and the slope is zero. At the very top of a hill the gradient shrinks to nothing, which is the multivariable version of "zero slope means a peak" from Calculus I. Rolling downhill is how a network learns Now flip the sign. A machine-learning model has adjustable numbers (weights), and a loss measures how wrong it is on the training data. The loss is a landscape over the weights, with one dimension per weight. To learn, take a small step against the gradient, so downhill, then recompute and repeat. This is gradient descent, which Augustin-Louis Cauchy proposed in 1847 for solving equations, long before computers. The chain rule from Calculus I is what lets the gradient be computed layer by layer, in the method called backpropagation, published by Rumelhart, Hinton and Williams in Nature in 1986. A model like GPT-3 (2020) has 175 billion weights, so its landscape has 175 billion dimensions, yet the rule is the same arrow. new position = old position − (step size) × ∇(loss) The step size matters, and you can feel why. In the bowl below, one direction is twelve times steeper than the other. Too small a step crawls; just right is fast; too large and each step overshoots the valley floor by more than it started and the loss explodes. For this bowl, steps above 1/6 (about 0.167) diverge. Interactive · Learning rate Too small Good Zig-zag Too big Step size (learning rate) Steps taken Real training uses refinements (momentum, adaptive step sizes, random mini-batches), but all of them are ways of coping with exactly this picture: a long narrow valley where the steepest direction is not the direction of the destination. Double and triple integrals add up a landscape's worth Integrals extend the same way. A single integral adds thin slices along a line. A double integral adds tiny patches over an area: if each patch has a density (kilograms per square metre), the sum is the plate's mass. A triple integral does the same over a solid, with density in kilograms per cubic metre. The recipe is slice, multiply, add, repeated once per dimension. mass = sum over all pieces of (density × piece size)  =  ∬ ρ dA The same sums also give the centroid, the balance point: weight each position by its piece's mass and divide by the total. Engineers use it constantly: the centre of mass of a rocket, a car or an aircraft decides whether it is stable. Try a plate 2 m long and 1 m wide whose density rises along the length. Interactive · Where does the plate balance? Density rises along the length: a (kg per m² per m) Density rises across the width: b The density here is 1 + ax + by kg/m². With a = 3 and b = 0, the plate's mass is 2 + 2×3 = 8 kg and it balances at x = 1.25 m, shifted from the middle (1 m) towards the heavy end. A vector field puts an arrow on every point Wind on a weather map, water in a pipe, the pull of a magnet: each attaches an arrow (a direction and strength) to every point in space. That is a vector field. Two numbers computed from the field's partial derivatives tell you most of what it is doing locally. Divergence: is the field spreading out from here, or converging? A tap under water is a source; a drain is a sink. A positive divergence means a small blob of fluid is expanding. Curl: is the field spinning? Put a tiny paddle wheel in the flow. If it turns, the curl is not zero, and the sign tells you which way. divergence = ∂vx/∂x + ∂vy/∂y    curl = ∂vy/∂x − ∂vx/∂y Pick a field and let a round blob of fluid (grey dashes show where it started) be carried along. You will see that a source inflates the blob without turning it, a whirlpool turns it without changing its area, and a saddle stretches it one way and squeezes it the other while keeping its area. Interactive · Drift a blob through a field Source Whirlpool Shear Saddle Time elapsed Divergence and curl are the two words in Maxwell's equations of electromagnetism (Physics II, 34/07) and in the equations of fluid flow (Fluid Mechanics, 34/15). Spreading and spinning are the two things a field can do locally, besides moving along as a whole. What flows out of a region is what is made inside Here is the idea behind the three big theorems, in the language of a bathtub. If water pours out through the boundary of a region, then some taps inside must be producing it (or the level inside must be falling). Add up every tiny source and sink inside and you get the net flow out through the boundary. Nothing more is needed. net flow out through the boundary = total divergence inside That is the divergence theorem, the three-dimensional version of the statement. Green's theorem is the flat version (the name honours George Green, whose Essay of 1828 contained the related surface-to-volume formula), and Stokes's theorem relates the spinning of a field inside a surface to the flow around its edge. All three say the same kind of thing: a sum over a boundary equals a sum of local changes inside. It is why one can measure a rotating machine from outside and why conservation laws can be written either as "this region's total changes by what crosses its walls" (integral form) or as an equation about each point (differential form). Interactive · Count the flow two ways Source Cubic Source in, sink out Steady wind Circle radius Circle centre, left or right The first number adds up the field's push through the circle itself. The second never looks at the circle's edge: it adds the divergence in every patch inside. They agree for every field, radius and position. For the plain source (x, y), the divergence is 2 everywhere, so a unit circle encloses 2 × π = 6.283 units of production, and exactly 6.283 flows out through its rim. What a graduate just sees A slope needs a direction; a partial derivative is the slope with every other input held still. The gradient points straight uphill, its length is the steepness, and it is perpendicular to the contour. "Downhill" is the whole idea behind training a model: step against the gradient, and mind the step size. Heat, and many other things, flow down a gradient from high to low. A double or triple integral is slice, multiply, add, once per dimension; mass and balance point come from it. A field can only spread (divergence) or spin (curl), locally. What leaves a region through its wall is exactly what its insides produce. Where it shows up next Physics II: Electricity & Magnetism (34/07): Maxwell's equations are statements about the divergence and curl of the electric and magnetic fields. Fluid Mechanics (34/15): conservation of mass is a divergence equation, and the divergence theorem turns "what crosses the walls of this control volume" into "what happens inside it". Heat Transfer (34/16): conduction is heat flowing down the temperature gradient; the heat equation is the gradient and divergence together. Machine Learning (34/32): training is gradient descent on a loss landscape with millions or billions of dimensions. Mechanics of Materials (34/11) and Dynamics (34/12): centroids and moments of inertia are integrals of exactly the kind you added up above. If you want to go deeper 📘 Textbook: Stewart, Clegg and Watson, Calculus: Early Transcendentals (9th ed.), chapters 14 to 16: the standard multivariable text, rich in examples. 📘 Textbook: Jerrold Marsden and Anthony Tromba, Vector Calculus (6th ed., W. H. Freeman): the classic for the geometry of divergence, curl and the big theorems. ▶️ Gentler: Khan Academy's Multivariable Calculus course, which has videos with a strong visual feel, and Grant Sanderson's multivariable lessons. 🌐 Free course: MIT OpenCourseWare 18.02SC Multivariable Calculus, with lectures, notes and exercises. The takeaway With many inputs, a slope needs a direction. The partial derivatives are the slopes along the axes; the gradient joins them into one arrow that points uphill and measures how steep it is. Walk against it and you are doing gradient descent, which trains models with billions of weights and also describes how heat flows. Integrals extend to areas and volumes, giving mass and balance points, and for flows the whole subject rests on one bookkeeping rule: what leaves a region through its boundary is what its interior produces. Try this: on any hill, a park slope or a street, find the line along which a ball would roll: that is the negative gradient. Then notice that the ball's path crosses the contours at right angles. Sources & Further Reading Sources. Gradient descent: A.-L. Cauchy, "Méthode générale pour la résolution des systèmes d'équations simultanées", Comptes rendus 25 (1847), pp. 536–538; Claude Lemaréchal, "Cauchy and the gradient method", Documenta Mathematica, Extra Volume ISMP (2012). Backpropagation: Rumelhart, Hinton and Williams, Nature 323 (1986), pp. 533–536. GPT-3's 175 billion parameters: Brown et al., "Language Models are Few-Shot Learners" (2020, arXiv 2005.14165). Green's Essay of 1828 containing the theorem named after him: MacTutor biography and the essay itself. Computed in node: the landscape f = 2e−((x−1)²+(y−1)²)/1.5 + 1.2e−((x+1.2)²+(y+0.8)²)/1.0 and its analytic gradient (checked against finite differences, agreement to 3 × 10−10); gradient descent on ½(x² + 12y²), stable for step sizes below 2/12; plate mass and centroid by 3,200-cell sums against the exact formulas; blob area against ediv·t; circle flux against the divergence integral for four fields (agreement to 4 decimals). 🌐 MIT OpenCourseWare 18.02SC Multivariable Calculus 🌐 Khan Academy: Multivariable calculus 🌐 Documenta Mathematica, ISMP volume, which contains Lemaréchal's short history of gradient descent 📘 Stewart, Clegg and Watson, Calculus: Early Transcendentals, 9th ed. (Cengage) 📘 Marsden and Tromba, Vector Calculus, 6th ed.