Data Science A path through The Default Library ======================================== Turning messy data into honest answers: cleaning it, modelling it, testing what causes what, and showing it so people understand. Step 1. Calculus I: Slopes, Totals and the Bridge Between Them -------------------------------------------------------------- Why: Rates of change and accumulation, under every model. 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 2. Linear Algebra: Machines That Move Space ------------------------------------------------ Why: Data is a matrix; most methods are linear algebra. 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 3. Programming Fundamentals: Instructions, State and Taking Things Apart ----------------------------------------------------------------------------- Why: Code is how a data scientist does anything at scale. 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 4. Probability & Statistics: Reasoning with Uncertainty ------------------------------------------------------------ Why: Probability and statistics: the core of the discipline. 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 5. Data Wrangling & Exploratory Analysis: Look Before You Model -------------------------------------------------------------------- Why: Most of the job: getting data clean and looking at it first. Most of a data scientist's work happens before any model exists: getting the numbers into a shape you can trust, and then simply looking at them. The habits are small, and the mistakes they prevent are enormous. In September 1999 NASA's Mars Climate Orbiter reached Mars on a path that took it too close to the planet, and contact was lost. The investigation found that one piece of ground software reported thruster impulse in pound-force seconds while the navigation software expected newton-seconds. Every number in the pipeline was a perfectly valid number. Nothing was missing, nothing was misspelled. The numbers just did not mean what the next program thought they meant. That is the everyday danger of data. A model will happily fit whatever you feed it, and it will not tell you that a column is in cents, that a blank means "refused to answer", or that the same city is spelled three ways. The people who catch these things are not running anything clever. They are reading the table, asking what each column means, and drawing a picture before they trust a summary. Practitioners say this is most of the job. The often-quoted figure that it is "80 per cent" is a rule of thumb, not a measurement, but anyone who has worked with real data will recognise the proportion. This piece is about that part of the job: the shape data should have, the habits of cleaning it, what to do about holes, and the four ways a quick summary lies to you. The course in one box Who takes itData science, statistics and analytics majors, usually in year 2, after a first course in programming and a first course in statistics. Programmes shaped by the ACM Data Science Task Force's 2021 guidelines and by courses such as Berkeley's Data 8 and Data 100 put data acquisition, cleaning and exploration early, because every later course assumes it. It is also taught as a short course for scientists, journalists and business analysts. What it is forTurning a raw, messy table into one you can defend, and looking at it enough to know what questions it can and cannot answer. Comes afterProgramming Fundamentals (34/09) and Probability & Statistics (34/05). Leads toData Visualization & Communication (36/32), Regression & Statistical Modeling (36/33), Experiments & Causal Inference (36/34) and Big Data & Data Engineering (36/36). It also sits beside Databases (34/28), where the data usually lives. What this piece gives youYou will not learn pandas or R syntax here. You will see what a clean table looks like, why missing data is not one problem but three, why a summary needs a picture, and how a pooled number can reverse the story. Easier first reads: Statistics for Reading the World (12/05) and Benford's Law (12/20). Tidy shape: one row per observation, one column per variable Before cleaning, there is the question of layout. A table can hold the same facts in many arrangements, and some make the next step easy while others make it a chore. The rule most data scientists work to was set out by Hadley Wickham in a 2014 paper called "Tidy Data": each variable is a column, each observation is a row, and each kind of thing you measured gets its own table. one row = one observation; one column = one variable"Wide" tables spread one variable (the month) across many columns; "long" tables keep it in one Spreadsheets for people tend to be wide, with months running across the top, because that is easy to read. Tools for analysis prefer long, because "group by month" is then a single instruction on a single column. Try the switch below, then add a month. Interactive · Wide versus long Wide Long Add April Illustrative figures for three invented shops. Without JavaScript: the long table has three columns (shop, month, sales) and nine rows for three months; adding a month adds three rows and changes no formula, while the wide table gains a column and every formula that listed the months must be edited. The payoff is not tidiness for its own sake. When the shape is right, a month added next quarter does not break anything, and the same few operations (filter, group, summarise, join) work on every table you meet. Cleaning is a run of small, logged decisions Real tables arrive with the problems below, and almost always more than one at once. Duplicate rows, because an export ran twice. The same category spelled several ways. A number stored as text, with a decimal comma in one country and a point in another. Mixed units, such as dollars in most rows and cents in a few. A placeholder such as 999999 standing for "unknown". Each of these quietly wrecks an average. The discipline is to fix them one at a time, in code, and to write down what you did and why. Step through a small, invented order table below and watch the mean order value change as each fix is applied. Interactive · Clean a messy table, one decision at a time Back Next fix Reset Invented orders, labelled illustrative. "Naive" means every amount is read with a plain number parser. Without JavaScript: read naively, the thirteen raw rows give a mean order of tens of thousands of dollars because of one placeholder (999999) and one amount in cents. After removing the duplicate, standardising the names, fixing the decimal comma and cents, and treating 999999 and the blank as missing, ten amounts remain with a mean of 23.58. Two habits matter more than any technique. First, never overwrite the raw file: keep the original, and write the cleaning as a script that turns raw into clean, so anyone can rerun it. Second, keep the log. In 2013 three economists, Herndon, Ash and Pollin, re-examined the spreadsheet behind a widely cited 2010 economics paper by Reinhart and Rogoff. They found that a formula had left five countries out of an average, along with other choices about which data to include. Corrected, the average growth for the high-debt group moved from −0.1 per cent to 2.2 per cent. Reinhart and Rogoff acknowledged the coding error while disputing the other criticisms and the strength of the conclusions drawn, so scholars still argue about the economics. The lesson for a data scientist is narrower: a result that lives only inside a hand-edited spreadsheet cannot be checked. Spreadsheets cause quieter trouble too. A 2016 scan of genomics papers found that about one in five with gene lists in Excel files contained gene names the program had silently turned into dates, so that a gene called SEPT2 became "2-Sep". In 2020 England's public-health agency lost track of nearly 16,000 positive Covid-19 test results because lab files were collected into an older spreadsheet format with a row limit. None of these is a failure of intelligence. They are what happens when the cleaning is invisible. Missing data: how much matters less than why Almost every real table has holes. The first instinct, to delete rows with blanks or fill them with the average, is only sometimes harmless. Donald Rubin's 1976 framework sorts missingness into three kinds, and the right move depends on which one you have. Missing completely at random (MCAR): whether a value is absent has nothing to do with anything. A sensor drops 10 per cent of readings by chance. Deleting those rows costs precision but not honesty. Missing at random (MAR): absence depends on something you did record. Younger respondents skip the income question more often, and you know their ages. You can correct for this by using the recorded variable. Missing not at random (MNAR): absence depends on the missing value itself. High earners decline to state their income. Nothing in the table can repair it, because the evidence for the problem is exactly what is gone. The simulation below builds 3,000 invented respondents whose income rises with age, deletes a share of the incomes by each mechanism, and tries two repairs. You will see the bias in the average, and a second cost of "fill with the mean": it leaves the average alone but shrinks the spread, because the filled-in values are all identical. Interactive · Three ways to go missing Share of incomes missing30% New random sample Invented data: age 20–65, income in thousands rising about 2% a year of age plus a random spread. Bias is estimate minus the true mean of all 3,000 incomes. Without JavaScript: in a typical run with 30 per cent missing, deleting blanks leaves the mean about right under MCAR, too high under MAR (young, lower earners are missing) and too low under MNAR (high earners are missing). Filling by age band repairs MAR but not MNAR. The practical rule: ask who is missing, and write down your answer. Modern statistics offers better tools than deletion or mean-filling, such as multiple imputation, but they too rest on an assumption about why values are absent, and no software can test the MNAR case from the data alone. Same summary, different picture Once the table is clean you will want to summarise it with a mean, a spread and a correlation. These are useful and also dangerous, because very different data can share them. In 1973 the statistician Francis Anscombe made the point with four small datasets of eleven points each. All four have the same mean of x (9), the same mean of y (7.5), the same variances, the same correlation (0.816), and the same best-fitting line, y = 3 + 0.5x. Plotted, they look nothing alike. Interactive · Anscombe's quartet Without JavaScript: set I is a noisy straight line; II is a smooth curve; III is a perfect line with one outlier that tilts the fit; IV is eleven points at one x value plus a single far point that alone creates the slope. All four report r = 0.82. In 2017 Justin Matejka and George Fitzmaurice of Autodesk went further. Starting from a dinosaur-shaped scatter plot by Alberto Cairo, they used a search procedure to move points a little at a time while holding the summary statistics fixed to two decimal places, and produced a dozen very different shapes (a star, a ring, parallel lines) with the same numbers. The summaries did not change. The picture did. The habit this builds is simple: plot first, summarise second, and treat a single summary number as a claim that needs a picture to support it. A histogram is a lens: the bin width is a choice The most basic picture of one variable is the histogram, which counts how many observations fall in each bin. John Tukey's 1977 book Exploratory Data Analysis made this kind of looking a respectable part of statistics, not a warm-up. But a histogram has a setting that most tools pick for you: the width of the bins. Too wide, and distinct groups merge into one hump. Too narrow, and chance wiggles look like structure. Rules exist for a sensible default (the Freedman–Diaconis rule sets the width to twice the interquartile range divided by the cube root of the number of observations), but they are starting points. Slide the width below on 240 invented delivery times and watch two groups of trips appear and vanish. Interactive · Choose the bin width Bin width (minutes)8 Use Freedman–Diaconis width Invented delivery times for a courier: a mix of short hops and long trips, labelled illustrative. Without JavaScript: the data are a blend of short trips (around 14 minutes) and long trips (around 31 minutes). Bins of 3 to 6 minutes show two humps; bins of 25 minutes or more show one lump. Notice what the mean of this data is: about 22 minutes, a time hardly any trip took. A summary that describes nobody is a warning that you have mixed two groups. Slice before you conclude: Simpson's paradox The fourth lens is the group-by. A pattern in the whole can reverse inside every part. The standard real example comes from the fall 1973 admissions data at the University of California, Berkeley, analysed by Bickel, Hammel and O'Connell in Science in 1975. Pooled over the six largest departments, 44.5 per cent of male applicants were admitted and 30.4 per cent of female applicants. That looks like a serious gap against women. Department by department, the picture turns over. In four of the six, women were admitted at a higher rate than men; in the other two men were slightly ahead. What happened is a matter of mix. Women applied far more to departments that admitted few applicants (such as C and E), and men to departments that admitted many (A and B). The authors concluded that the pooled gap did not show a bias in the way departments decided; it came from where people applied. Why the applications differed is a further question that this data does not answer. Interactive · Pooled versus by department Pooled By department Data: six largest departments, UC Berkeley, fall 1973 (the R UCBAdmissions table, from Bickel et al. 1975). Without JavaScript: pooled, men 44.5% (1,198 of 2,691) and women 30.4% (557 of 1,835). By department, women's rates were higher in A, B, D and F and lower in C and E. Roughly half of male applicants (51.5%) applied to A or B, against 7.2% of female applicants. You can put a number on the mix effect. Give women the same department mix as the men had, keeping each department's female admission rate, and the female rate would be 51.6 per cent, above the men's 44.5. The lesson is not "the data hide the truth". It is that a pooled number answers a different question from a per-group number, and you should look at both before saying which question you are asking. This is also where exploration meets causation. The department is a variable that sits between the applicant and the decision, and whether to adjust for it depends on a causal story. Experiments & Causal Inference (36/34) takes that on. What a graduate just sees A table is only as good as what each column means; the units and the codes for "unknown" are part of the data. Long, tidy tables make later steps boring, which is the point. Cleaning is a script plus a log, never a series of manual edits to the only copy. Missing values come in three kinds, and the question is "who is missing?", not "how many?". Filling in the mean keeps the average and destroys the spread. A summary statistic is a claim; draw the picture before you believe it. A histogram has a free setting, and a mean that describes nobody is a sign of two groups. A pooled comparison can reverse inside every group, so slice by the obvious lurking variable. Where it shows up next Data Visualization & Communication (36/32): the plots you make to explore become the ones you make to persuade, with extra rules about honesty. Regression & Statistical Modeling (36/33): a coefficient is only as sound as the cleaned columns behind it, and regression is how you "adjust" for a department. Experiments & Causal Inference (36/34): Simpson's paradox is resolved by a causal diagram, not by more data. Big Data & Data Engineering (36/36): the same cleaning, written as pipelines that run every night on tables too big for one computer. In the world: hospital records, election data, sensor logs, the dashboards a company runs on, and any news chart built from a government spreadsheet. If you want to go deeper 📘 Textbook. Hadley Wickham, Mine Çetinkaya-Rundel and Garrett Grolemund, R for Data Science (2nd edition, O'Reilly, 2023), free online at r4ds.hadley.nz; or Wes McKinney, Python for Data Analysis (3rd edition, O'Reilly, 2022), free online at wesmckinney.com/book. Pick the language your field uses. 📘 Gentler. David Spiegelhalter, The Art of Statistics (2019), a readable tour of looking at data before modelling it; and John Tukey, Exploratory Data Analysis (1977), the classic that started the habit. 🌐 Free text. Ani Adhikari, John DeNero and David Wagner, Computational and Inferential Thinking, the free textbook of Berkeley's Data 8, at inferentialthinking.com. 🌐 Free course. Berkeley Data 8: The Foundations of Data Science, and MIT OpenCourseWare 15.071 The Analytics Edge (Spring 2017), which works through real data sets in R. The takeaway Data does not arrive ready to model. Give it a tidy shape, clean it with a script and a log, ask why values are missing before choosing a fix, and draw the picture before trusting a summary. The few hours spent here decide whether any later model means anything. Try this: open any spreadsheet you use, pick one column, and write down its unit and what a blank would mean. Then sort it, look at the smallest and largest five values, and ask whether each is believable. Sources & Further Reading Sources. NASA/JPL Mars Climate Orbiter Mishap Investigation Board, Phase I report (1999); Wickham, "Tidy Data," Journal of Statistical Software 59(10), 2014; Herndon, Ash and Pollin, "Does high public debt consistently stifle economic growth? A critique of Reinhart and Rogoff," Cambridge Journal of Economics (2014; working paper 2013); Reinhart and Rogoff, "Growth in a Time of Debt," American Economic Review 100(2), 2010; Ziemann, Eren and El-Osta, "Gene name errors are widespread in the scientific literature," Genome Biology 17, 2016; BBC News, "Excel: Why using Microsoft's tool caused Covid-19 results to be lost," 5 October 2020; Rubin, "Inference and missing data," Biometrika 63, 1976; Anscombe, "Graphs in statistical analysis," The American Statistician 27(1), 1973; Matejka and Fitzmaurice, "Same stats, different graphs," CHI 2017; Tukey, Exploratory Data Analysis, 1977; Freedman and Diaconis, "On the histogram as a density estimator," 1981; Bickel, Hammel and O'Connell, "Sex bias in graduate admissions: data from Berkeley," Science 187, 1975. 📘 Wickham, Çetinkaya-Rundel and Grolemund, R for Data Science 📘 Spiegelhalter, The Art of Statistics 🌐 Berkeley Data 8 Step 6. Data Visualization & Communication: A Chart Is an Argument ------------------------------------------------------------------ Why: A finding no one understands has not been found. A finding nobody understands has not been found. Charts are how analysis reaches other people, and every choice in one, from the axis to the colour to the title, either helps the reader see the truth or nudges them away from it. Imagine a company's customer-satisfaction score rising from 52 to 54 out of 100. One slide shows two bars of almost the same height, and the audience yawns. Another slide shows the same two bars on an axis that starts at 50, so the second bar towers over the first at twice the height, and the audience applauds. Nothing in the data differs. The first slide is honest about size. The second is accurate about every number and misleading about the change. Drawing data has been a deliberate craft for a long time. In 1786 the Scottish engineer William Playfair put the first line and bar charts of economic data in his Commercial and Political Atlas, and in 1801 what were probably the first pie charts in his Statistical Breviary. In 1869 the French engineer Charles Joseph Minard drew Napoleon's army shrinking on its march to Moscow and back as a band that thins, with the temperature underneath. Edward Tufte, whose 1983 book made the whole field respectable, says it may well be the best statistical graphic ever drawn. This piece is about the handful of ideas that separate a chart that informs from one that merely decorates. They come from perception research and from decades of watching charts mislead, and each one can be tested with your own eyes. The course in one box Who takes itData science, statistics, journalism, design and analytics students, usually in year 2 or 3, and as a short workshop for scientists and managers. Programmes shaped by the ACM Data Science Task Force's 2021 guidelines and by courses such as Berkeley's Data 8 and Data 100 include communicating results as part of the discipline, not an afterthought. What it is forChoosing how to show data so a reader sees the right thing quickly, and can trust what they see. Comes afterData Wrangling & Exploratory Analysis (36/31), where the plots are for you. Leads toRegression & Statistical Modeling (36/33) and Experiments & Causal Inference (36/34), where results must be shown with their uncertainty, and Data Ethics, Privacy & Fairness (36/37), where a chart's framing can harm. What this piece gives youYou will not learn a plotting library. You will know which visual channel the eye reads best, why a bar must start at zero while a line need not, how a time window can be picked to tell either story, what colour-blind readers see, and what to put in a title. Easier first reads: Statistics for Reading the World (12/05) and Data Journalism (35/97). The eye ranks the encodings: position beats area To draw a number you must turn it into something visible: a position, a length, an angle, an area, a colour. The eye is not equally good at reading these. In 1984 William Cleveland and Robert McGill, statisticians at Bell Labs, ran experiments in which people judged how large one value was relative to another under different encodings. Their ranking, from most to least accurate, was roughly: position along a common scale; position along non-aligned scales; length, direction and angle; area; then volume, curvature and shading. In 2010 Jeffrey Heer and Michael Bostock repeated the study with hundreds of online volunteers and reproduced the broad pattern. the more directly a value becomes a position on a shared scale, the more accurately it is readDots and bars on a common baseline beat angles (pie slices), which beat areas (bubbles) That ranking explains a good deal of advice. Bars on a shared baseline are easy to compare; pie slices are harder, except when you only want to see "about half" or "a small slice"; bubbles are hardest. Try it on yourself below: the page shows two values with the numbers hidden, you guess what per cent the second is of the first, then it reveals the truth. Do a few rounds with each encoding. Interactive · How well can you read it? B is what per cent of A?50% RevealNew pair Your scores live only on this page and vanish when you leave. A few guesses by one person are a demonstration, not a study. Without JavaScript: in Cleveland and McGill's ranking, position on a common scale is judged most accurately, then length and angle, then area. Bars on a shared baseline beat pie slices, which beat circles scaled by area. Before choosing an encoding, choose the chart by the question you are answering. This is the short version of what most courses teach. The reader's questionA good starting chartWhy Which is bigger?Bars on one baseline, sortedLength on a common scale How has it changed?Line over timeThe slope carries the change How is it spread out?Histogram or box plotShows shape, not just the average Are these two related?Scatter plotEach point is one case What share is each part?Stacked bar; a pie only for two or three partsAngles are read less precisely A bar's length is the number, so the bar must start at zero A bar chart tells the eye to compare lengths. The length is only a fair stand-in for the value if the bar starts at zero, because then a bar twice as long means twice the value. Cut the axis and the lengths stop meaning that. The reader sees a ratio of heights that no longer matches the ratio of values. apparent ratio = (B − base) ÷ (A − base)with base = 0 this is the true ratio B ÷ A; the nearer the base is to A, the larger the distortion A line chart is different. It marks positions, not lengths, so a line may use an axis that starts well above zero, as every temperature or share-price chart does. But even there a stretched axis exaggerates the slope, and the honest move is the same: the labels must say what range you are looking at. Designers do argue about how strict the bar rule should be. A 2020 paper by Michael Correll, Enrico Bertini and Steven Franconeri found that truncating the axis raises how large people judge an effect to be, in bar charts and other chart types alike, and that this persisted even when the chart carried explicit cues such as an axis break. They also argued that truncation is sometimes defensible when the meaningful differences in the data are small, as with body temperature, and that designers should think about the scale of the effect they want to show. The common advice, which most style guides follow, is still to start bars at zero unless you have a very good reason and say so. Interactive · Move the baseline Bars Line Axis starts at0 Invented satisfaction scores, 52 last year and 54 this year. Without JavaScript: with the axis starting at 0, bar B is 1.04 times as tall as bar A. Start the axis at 50 and B looks twice as tall, though both numbers are unchanged. The window is a choice: the same series can rise or fall Time-series charts have a quieter way to mislead: the start and end dates. Real series wander. Almost any long, noisy series contains stretches that rise sharply and stretches that fall, and anyone who picks the window picks the story. This is cherry-picking, and it needs no false number at all. The sound practice is to show the whole series, or to say why a window was chosen and what the rest of the series looks like. A reader can also ask the cheap question: why does the chart begin here? Drag the window over 48 invented months below, then let the page find the most extreme 12-month-or-longer stretches in each direction. Interactive · Pick the window, pick the story Window starts at month1 Window ends at month48 Most upward 12+ monthsMost downward 12+ monthsWhole series An invented index; a random walk with a gentle upward drift, labelled illustrative. Windows are at least 6 months wide. Without JavaScript: over all 48 months the fitted trend is slightly up (about +0.5 per month). The steepest 12-month stretch rises about 2.1 per month; another stretch falls about 1.1 per month. Colour must survive a colour-blind reader and a black-and-white printer About 1 in 12 men and 1 in 200 women have some form of red–green colour vision deficiency, the most common kind. In a room of a hundred readers that is a few people for whom a red line and a green line are the same dull colour. Red-versus-green is the most common colour scheme in business charts, and it fails exactly for them. A well-tested alternative is the eight-colour palette published by Masataka Okabe and Kei Ito (2002, revised 2008; both are themselves colour-blind), chosen so that its colours stay distinct for the common deficiencies. The simulation below converts colours to what a person with deuteranopia or protanopia would roughly see, using the model of Machado, Oliveira and Fernandes (2009) at full severity. It is an approximation: real vision varies from person to person. Interactive · What the other reader sees As designed As seen The whole Okabe–Ito palette, as seen Without JavaScript: a red (#d62728) and green (#2ca02c) pair have a colour distance of about 209 for typical vision but only about 30 for deuteranopia. A vermillion (#D55E00) and blue (#0072B2) pair stay at about 206. Two further rules follow. First, never let colour alone carry the meaning: add direct labels, line styles or markers. The luminance gap in the readout above shows why, since two colours can differ in hue and still print as the same grey. Second, use colour sparingly: grey for the context, one strong colour for the thing the reader should see. Say what you found: the title, the labels and the ink A chart that needs a paragraph of explanation beside it is only half finished. The strongest single change is the title. "Figure 3: Bike trips" names the topic. "Bike trips in City A rose by half in five years; City B's barely moved" states the finding, so the reader looks at the chart to check it instead of hunting for it. Journalists and consultants write chart titles as sentences for this reason. The second change is to remove what does not carry data. Tufte called the share of ink that shows data the data-ink ratio and urged designers to erase the rest: heavy gridlines, boxes, shadows, three-dimensional effects. The advice is a good default, though not a law. In a 2010 experiment Scott Bateman and colleagues found that charts with pictorial embellishment were recalled better after a gap of two to three weeks than plain ones, and were read about as accurately, so decoration is not always harmful. Embellishment that distorts the data, such as a three-dimensional pie whose front slice looks bigger, remains a plain loss. Interactive · Clean up the chart Title states the finding Label lines directly Remove heavy gridlines Remove frame and decoration Invented data for two cities, in thousands of trips a day, labelled illustrative. Without JavaScript: City A's daily trips go 42, 45, 38, 47, 55, 63 (thousands, 2019 to 2024), a rise of 50 per cent; City B's go 30, 31, 24, 28, 31, 33, a rise of 10 per cent. Show the denominator, and the doubt Many misleading charts have honest bars and a missing divisor. A map or ranking of raw counts mostly shows where the people are. Cases, crimes, accidents and sales need dividing by population, exposure or time before regions or years can be compared. Per-capita rates have their own trap, since small places have noisy rates, but they answer the question the reader is usually asking. Interactive · Raw count or rate? Raw count Per 100,000 people Four invented regions and invented case counts, labelled illustrative. Without JavaScript: by raw count the order is Norte (5,400), Sur (1,500), Valle (1,020), Costa (600). Per 100,000 people it reverses to Costa (100), Valle (85), Norte (60), Sur (50). The other half is doubt. An estimate drawn as a single point or a single bar claims a precision it rarely has. Error bars, bands and ranges tell the reader how much to trust the number, and they are also how you stop yourself from over-reading small differences. Regression & Statistical Modeling (36/33) shows where those intervals come from. What a graduate just sees Every chart is a translation of numbers into position, length, angle, area or colour, and the eye reads them with different accuracy. A bar starts at zero because its length is the number; a line may float, but its axis must be labelled. The start and end of a time series are choices, so ask what the rest of the series looks like. Colour that depends on telling red from green fails for about one man in twelve; add labels and test in greyscale. A title that states the finding is worth more than any decoration. Raw counts show where the people are; rates show the difference. An honest chart shows its uncertainty and its source. Where it shows up next Regression & Statistical Modeling (36/33): residual plots and fitted lines are the diagnostics, and confidence bands are the honest way to show a model. Experiments & Causal Inference (36/34): the standard picture of an effect is a point estimate with an interval, plotted against zero. Data Ethics, Privacy & Fairness (36/37): framing, aggregation and what is left off the axis decide who is seen in the data. Big Data & Data Engineering (36/36): dashboards that refresh every minute are charts built once and read by thousands. In the world: the news chart, the quarterly slide, the public-health bulletin and the scientific figure all follow these rules or break them. If you want to go deeper 📘 Textbook. Claus Wilke, Fundamentals of Data Visualization (O'Reilly, 2019), free online at clauswilke.github.io/dataviz; or Kieran Healy, Data Visualization: A Practical Introduction (Princeton, 2019), free online at socviz.co. 📘 Gentler. Alberto Cairo, How Charts Lie (Norton, 2019); Cole Nussbaumer Knaflic, Storytelling with Data (Wiley, 2015); and Edward Tufte, The Visual Display of Quantitative Information (Graphics Press, 1983; 2nd edition 2001), the classic. 🌐 Free text. The two online books above, which come with their code, and Tamara Munzner, Visualization Analysis and Design (CRC Press, 2014), for the theory behind the encodings. 🌐 Free course. MIT OpenCourseWare 15.071 The Analytics Edge (Spring 2017), whose Unit 7 is on visualization; and Berkeley Data 8. The takeaway A chart is an argument made of choices: what to encode as position, where to start the axis, which dates to show, which colours to use, what the title says, what to divide by. Make each choice so the reader would reach the same conclusion if they saw all the data. Try this: find one chart in this week's news. Check where the axis starts, what the time window is, whether the numbers are counts or rates, and whether the title states a finding. Write down what you would change. Sources & Further Reading Sources. Playfair, The Commercial and Political Atlas (1786) and Statistical Breviary (1801); Minard, "Carte figurative des pertes successives en hommes de l'armée française dans la campagne de Russie 1812-1813" (1869); Tufte, The Visual Display of Quantitative Information (1983); Cleveland and McGill, "Graphical perception," Journal of the American Statistical Association 79 (1984); Heer and Bostock, "Crowdsourcing graphical perception," CHI 2010; Correll, Bertini and Franconeri, "Truncating the y-axis: threat or menace?," CHI 2020; Machado, Oliveira and Fernandes, "A physiologically-based model for simulation of color vision deficiency," IEEE Transactions on Visualization and Computer Graphics 15(6), 2009; Okabe and Ito, "Color Universal Design" (2002, revised 2008), jfly.uni-koeln.de/color; standard clinical references for the prevalence figures (about 8% of males, 0.5% of females); Bateman, Mandryk, Gutwin, Genest, McDine and Brooks, "Useful junk? The effects of visual embellishment on comprehension and memorability of charts," CHI 2010. 📘 Wilke, Fundamentals of Data Visualization 📘 Cairo, How Charts Lie 🌐 Healy, Data Visualization: A Practical Introduction Step 7. Data Structures: How Arrangement Decides Speed ------------------------------------------------------ Why: How data is held in memory, and why it decides speed. 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 8. Databases: Why Your Data Survives a Power Cut ----------------------------------------------------- Why: Where real data lives, and how to ask it questions. 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 9. Regression & Statistical Modeling: The Line, and What It Means ---------------------------------------------------------------------- Why: Regression: the workhorse model and how to read it. Regression is the workhorse of data science: fit a line, read its slope, ask how far to trust it. Most of the skill is not in the fitting, which a computer does in a blink, but in knowing what the numbers do and do not say. Why do tall parents tend to have tall children, but children of very tall parents are on average a bit shorter than their parents? Why does a restaurant that wins an award one year tend to do slightly worse the next? Why does a model that fits last year's data perfectly predict this year's badly? Each is a regression story, and each is told wrongly all the time. Regression answers a plain question: how does one number change, on average, as another changes? The answer is a line, and a line is easy to draw. What takes a course is learning to read it: what the slope means when other things are also moving, how much the slope would wobble with a different sample, when a better-fitting curve is a worse predictor, and how to model a yes-or-no outcome. The history is short and oddly argumentative. Adrien-Marie Legendre published the method of least squares in 1805. Carl Friedrich Gauss claimed in 1809 that he had been using it since 1795, which began a priority dispute. Francis Galton coined the word "regression" in a paper of 1886 about the heights of parents and children. The word stuck to the method, though it describes only the first of its uses. The course in one box Who takes itData science, statistics, economics, psychology and engineering students, usually in year 3, as the first serious modelling course. Programmes shaped by the ACM Data Science Task Force's 2021 guidelines, the National Academies' 2018 report Data Science for Undergraduates and courses such as Berkeley's Data 100 and MIT's statistics offerings treat regression as the backbone from which more flexible models grow. Economics departments teach a close cousin as Econometrics (34/44). What it is forDescribing how an outcome relates to one or more inputs, predicting new cases, and saying how sure you are. Comes afterProbability & Statistics (34/05) and Linear Algebra (34/04), since the fit is a projection in a space of columns. Leads toExperiments & Causal Inference (36/34), Machine Learning (34/32), Deep Learning (36/35) and Econometrics (34/44). What this piece gives youYou will not run a full regression diagnostics workflow. You will see why the line minimises squares, what R² and residuals tell you, what "holding the others fixed" means, how much a slope wobbles, why flexibility backfires, and how logistic regression turns a line into a probability. Easier first reads: Statistics for Reading the World (12/05) and Probability & Statistics (34/05). Least squares: the line that makes the squares smallest Given a cloud of points, which line is "best"? Any line leaves a vertical gap at each point, called a residual: the observed value minus the line's prediction. A good line has small gaps. The question is how to add them up. Positive and negative gaps cancel, so you square them first. The line that makes the sum of squared residuals as small as possible is the least-squares line. choose the slope and intercept that minimise the sum of (observed − predicted)²for one input: slope = covariance(x, y) ÷ variance(x), and the line passes through the point (mean x, mean y) Squaring has a physical picture: each residual is the side of a square, and you are trying to make the total area of those squares small. It also has a mathematical reason: squares make the problem a smooth bowl with exactly one lowest point, so a formula (or one pass of linear algebra) finds it. Large misses are punished heavily, which is both the method's strength and its weakness, since one wild point can drag the whole line. Try it. Your line starts in a poor place. Move the sliders to shrink the squares, then compare your total with the true minimum. Drag the points (or tap where you want one) and watch the best line move; pull one point far from the rest to see how much leverage it has. Interactive · Make the squares small Your slope0.30 Your intercept4.0 Snap to best linePull one point awayReset points Nine invented points. Squares show each residual squared; the dashed line is the least-squares fit. Without JavaScript: for the starting nine points the least-squares line is about y = 1.4 + 0.67x with an R² of 0.95. A poor guess such as y = 4 + 0.3x has a sum of squares about ten times larger. R² and the residuals: what the line explained and what it missed How good is the fit? One summary is R², the share of the outcome's variation that the line accounts for. If you predicted every point with the plain average, your squared misses would total some amount (the total variation). The line's squared misses are what is left over. R² is the fraction of the total that the line removed. R² = 1 − (squared misses of the line) ÷ (squared misses of the plain average)0 means no better than the average; 1 means every point on the line; for one input it equals the correlation squared A single R² can hide a poor model, which is the lesson of Anscombe's quartet in Data Wrangling & Exploratory Analysis (36/31). The remedy is to look at the residuals. If the line is right, residuals scatter randomly around zero with the same spread everywhere. Patterns mean the model is missing something: a bow means the relationship is curved, a funnel means the noise grows with the input, and one far-off point can tilt everything. Pick a pattern below and compare the R² with the residual plot. Interactive · Residual detective Sixty invented points for each pattern. Top: data and best line. Bottom: residuals against x, with zero marked. Without JavaScript: the curved pattern still has an R² of about 0.86 although its residuals form a clear bow; the funnel has residuals about three times as spread out on the right as on the left; removing the single outlier changes the fitted slope noticeably and lowers the R². R² is also easy to inflate: adding any input, even a useless one, never lowers it on the data you fitted. That is why serious reports pair it with an out-of-sample check, which is the topic of the overfitting section below. Reading a coefficient: "holding the others fixed" With one input, the slope says how much the outcome changes on average when the input rises by one unit. With several inputs, each coefficient is read with a phrase attached: the change in the outcome per unit of this input, holding the other inputs fixed. The computer finds all coefficients at once so that, in effect, each input is compared only among cases that match on the others. That phrase is where regression earns its keep. Take children aged 5 to 12. Those with bigger feet read better. But no one thinks feet teach reading. Both grow with age. In the simulation below the true effect of shoe size on reading is a number you choose, and the default is zero. Compare the simple slope with the slope after age is included. Interactive · Add the confounder True effect of shoe length on reading (score per cm)0.00 Shoe length onlyShoe length and age youngest third middle third oldest third 200 invented children aged 5 to 12; shoe length rises about 1 cm a year. Labelled illustrative. Without JavaScript: with a true effect of zero, the simple slope of reading on shoe length is about 3.6 points per cm and looks strongly "significant"; once age is in the model the shoe coefficient falls to about 0.6, with a confidence interval that runs from below zero to above 1. Two cautions. A coefficient can only be adjusted for inputs you measured, so an unmeasured confounder survives. And "holding fixed" is a statistical statement about comparing similar cases, not proof that changing one thing in the world would change the outcome. That jump needs a design, not just a regression; Experiments & Causal Inference (36/34) is the course for it. A related trap, Simpson's paradox, appeared in Data Wrangling & Exploratory Analysis (36/31). The slope wobbles: standard errors and confidence intervals A fitted slope is an estimate from one sample. Collect another sample from the same world and you would get a slightly different line. The standard error says how much, typically. For a single input it is the typical size of a residual divided by the square root of the total spread of x: SE(slope) = s ÷ √Σ(x − mean x)², where s² = (sum of squared residuals) ÷ (n − 2)shrinks with more data, with a wider spread of x, and with less noise The dependence on data is a square root: four times as many observations halves the standard error, and ten times as many cuts it to about a third. A 95% confidence interval is the slope plus and minus a multiple of the standard error (about 1.96 for large samples, larger for small ones). The meaning is easy to garble. It is a statement about the procedure: if you repeated the whole study many times, about 95% of the intervals built this way would contain the true slope. It is not a 95% probability that this particular interval holds it, in the strict frequentist reading. Bayesian methods answer a different question, with different assumptions, and statisticians still argue about which is better to teach. See the wobble yourself. The world below has a true slope of 0.5. Choose a sample size, draw 30 samples, and look at the bundle of fitted lines. Then watch what 200 repeated samples say about the standard error and about how often the interval catches the truth. Interactive · Draw many samples Sample size n20 Draw new samples Invented world: y = 1 + 0.5x plus noise with standard deviation 2, x between 0 and 10. Bold line: the first sample; dashed: the truth. Without JavaScript: at n = 20 the standard error of the slope is about 0.16 and the 95% intervals catch the true slope in roughly 93 to 95% of repeated samples; at n = 200 the standard error is about 0.05. Ten times the data cuts the wobble to about a third, the square root of ten. Overfitting: a flexible model learns the noise A straight line is rigid. A curve with many bends is flexible, and with enough bends it can pass through every training point. That sounds like success until you ask how it does on new data. A model that has memorised the noise of one sample has learned nothing portable. The standard defence is to hold some data back: fit on a training set, then measure the error on a test set the model never saw. Training error always falls as flexibility rises. Test error falls, then climbs. The bottom of that U is where the model has learned the signal and not yet the noise. The tension is the bias–variance trade-off: a rigid model is wrong in a steady way (bias), and a flexible one changes wildly with the sample (variance). Machine Learning (34/32) takes it much further. Interactive · How bendy is too bendy? Polynomial degree1 New training sample training points test points fitted curve 12 training points and 80 test points from y = sin(2.5x) plus noise (sd 0.35), x between −1 and 1. Error is the root-mean-square miss. Curves off the chart are clipped. Without JavaScript: for the starting sample, the training error falls steadily from 0.33 at degree 1 to 0.06 at degree 9, while the test error is lowest near degree 3 (about 0.41) and rises above 2 by degree 8. Logistic regression: when the answer is yes or no A straight line is a poor model of an outcome that is 0 or 1 (passed or failed, clicked or did not, survived or not). The line goes below 0 and above 1, and "0.7 of a pass" means nothing. Logistic regression fixes this by modelling the log-odds of the outcome as a straight line, then converting back to a probability with an S-shaped curve. The odds of an event are p ÷ (1 − p): a probability of 0.75 is odds of 3 to 1. David Cox's 1958 paper on the regression analysis of binary sequences is a standard reference for the method in statistics. log(p ÷ (1 − p)) = b₀ + b₁x, so p = 1 ÷ (1 + e^−(b₀ + b₁x))each extra unit of x multiplies the odds by e^b₁, the odds ratio; p = ½ where x = −b₀ ÷ b₁ The coefficients are found by maximum likelihood rather than least squares: choose the curve under which the observed passes and fails were most probable. Slide the two parameters below to raise the likelihood, then let the page find the maximum. Interactive · Pass or fail by hours of study b₀ (intercept on the log-odds scale)-4.0 b₁ (change in log-odds per hour)0.00 Find the best fit 24 invented students. Dots at 1 passed, dots at 0 failed (spread out slightly so they do not overlap). Without JavaScript: for the invented data the best fit is near b₀ = −4.1 and b₁ = 1.16, an odds ratio of about 3.2 per hour, with a 50% chance of passing at about 3.6 hours of study. Predict or explain: two jobs for one tool Regression is used for two different purposes, and the standards differ. For prediction, the only question is whether the model does well on new cases; whether the coefficients mean anything is irrelevant. For explanation, the coefficients are the point, and you care about confounders, measurement error and whether the model is the right shape. In 2001 the statistician Leo Breiman described these as two cultures: one starting from an assumed data-generating model, the other from algorithms judged by predictive accuracy. His essay set off a debate that still runs. One more idea explains the opening puzzles. Galton found that extremely tall parents had children who were tall but, on average, less extreme. This is regression to the mean. Where two measurements are imperfectly related, a case chosen for being extreme on the first is, on average, closer to the middle on the second, because part of what made it extreme was luck. Award-winning restaurants, record-breaking seasons and top-scoring students all drift back. It is not a force; it is selection plus noise, and many "cures" and "slumps" are nothing more. What a graduate just sees The best line is the one that makes the squared vertical misses smallest, and one wild point can drag it. R² says how much of the variation the line removed, and it never says whether the line was the right shape. Residual plots are the first diagnostic: bows, funnels and lone outliers show up there. A coefficient means "per unit, holding the others fixed", and only the others you measured. Every estimate wobbles; the standard error shrinks with the square root of the sample size. More flexibility always improves the fit to the data in hand and often worsens the next prediction. For yes-or-no outcomes, model log-odds with a line and read coefficients as odds ratios. Extreme cases drift back toward the middle, with no cause needed. Where it shows up next Experiments & Causal Inference (36/34): when a coefficient may be read as a cause, and what a randomised experiment, or an instrument, buys you. Econometrics (34/44): regression with panel data, instruments and standard errors that survive real-world messiness. Machine Learning (34/32) and Deep Learning (36/35): regularisation, cross-validation and neural networks are regression made flexible, with the overfitting problem made central. Data Ethics, Privacy & Fairness (36/37): a model that predicts well can still encode and amplify a pattern in the data; fitting it does not make it fair. In the world: insurance pricing, clinical risk scores, A/B-test analysis, sports analytics, credit scoring and every "the data show that" claim in the news. If you want to go deeper 📘 Textbook. Gareth James, Daniela Witten, Trevor Hastie and Robert Tibshirani, An Introduction to Statistical Learning (2nd edition, Springer, 2021; a Python edition followed in 2023), free from statlearning.com; or Andrew Gelman, Jennifer Hill and Aki Vehtari, Regression and Other Stories (Cambridge University Press, 2020), which is strong on reading coefficients honestly. 📘 Gentler. David Spiegelhalter, The Art of Statistics (2019), with a lively chapter on regression and regression to the mean; and Charles Wheelan, Naked Statistics (2013). 🌐 Free text. The two textbooks above are the standard routes. Computational and Inferential Thinking at inferentialthinking.com (Berkeley Data 8) has a chapter on regression built from first principles. 🌐 Free course. MIT OpenCourseWare 18.650 Statistics for Applications (Fall 2016, Philippe Rigollet), with lecture videos on linear and logistic regression; and 15.071 The Analytics Edge (Spring 2017), whose Unit 2 is linear regression. The takeaway Regression fits the line that makes squared misses smallest, then asks the questions that matter: what is left over, what does each slope mean when other things move, how much would it wobble, and does it still work on data it has not seen. Treat the output as the start of an argument, not the end. Try this: find a claim of the form "X is linked to Y" in the news. Ask what else grows with X, whether the study measured it, and whether the result is a prediction or an explanation. Sources & Further Reading Sources. Legendre, Nouvelles méthodes pour la détermination des orbites des comètes (1805); Gauss, Theoria motus corporum coelestium (1809); Galton, "Regression towards mediocrity in hereditary stature," Journal of the Anthropological Institute 15 (1886); Anscombe, "Graphs in statistical analysis," The American Statistician 27(1), 1973; Cox, "The regression analysis of binary sequences," Journal of the Royal Statistical Society B 20(2), 1958; Breiman, "Statistical modeling: the two cultures," Statistical Science 16(3), 2001; James, Witten, Hastie and Tibshirani, An Introduction to Statistical Learning, 2nd ed., 2021; ACM Data Science Task Force, Computing Competencies for Undergraduate Data Science Curricula (2021); National Academies, Data Science for Undergraduates (2018). 📘 James, Witten, Hastie and Tibshirani, An Introduction to Statistical Learning 📘 Gelman, Hill and Vehtari, Regression and Other Stories 🌐 MIT OCW 18.650 Statistics for Applications Step 10. Experiments & Causal Inference: Why a Coin Flip Beats a Clever Model ----------------------------------------------------------------------------- Why: Correlation is not causation; experiments and the methods that stand in for them. Data tells you what goes with what. Whether pulling a lever changes anything is a different question, and answering it takes a design, not more data. For decades, doctors read the same pattern in large observational studies: women who took hormone therapy after menopause had fewer heart attacks. It was a big, careful body of research, and the advice followed it. Then the Women's Health Initiative did something simpler. It assigned thousands of women, by lot, to hormones or a placebo. The trial's combined-hormone arm was stopped early in 2002 because the treated women had more breast cancer and more cardiovascular events, not fewer (Rossouw and colleagues, JAMA, 2002). Researchers still discuss why the earlier studies pointed the other way. One often-cited explanation is that women who chose hormones were healthier and better off to begin with, in ways that adjusting for recorded factors did not fully remove. That is the central worry of this subject. A pattern in data is a fact about the data. A cause is a claim about what would happen if you changed something, and no table of numbers contains that on its own. A graduate of a causal-inference course keeps a habit: before looking at an estimate, ask what would have happened to these same people without the treatment, and what in the design makes the comparison fair. The tools are old and new. Ronald Fisher built the logic of randomised experiments at the Rothamsted agricultural station in the 1920s and wrote it up in The Design of Experiments (1935). The formal language of "what would have happened" came from Jerzy Neyman (1923) and Donald Rubin (1974), and Judea Pearl's diagrams (from the 1980s, in Causality, 2000) turned it into something you can draw. Today the same ideas run every A/B test at every large web company. The course in one box Who takes itData science and statistics majors, usually in year 3 after regression; also economics, epidemiology and public-health students, who often meet it as "causal inference" or inside econometrics. Programmes differ in emphasis: statistics departments favour potential outcomes and randomisation, computer science favours Pearl's graphs, and economics favours natural experiments. Technology companies teach the experimentation side in-house. What it is forAnswering "what would change if we did this?", and knowing when the data in hand can and cannot answer it. Comes afterRegression & Statistical Modeling (36/33). Leads toNo later subject in this major lists it as a prerequisite. It underlies the testing of a model's effects in Data Ethics, Privacy & Fairness (36/37), and connects to Research Methods in Psychology (35/19) and Econometrics (34/44). What this piece gives youYou will not be able to design a clinical trial or run an experimentation platform. You will see why a coin flip beats a clever model, how to draw the story before touching a regression, and why an A/B test can mislead. For the econometric toolkit (difference-in-differences, instruments, cutoffs, and the minimum-wage study), read Econometrics (34/44); this piece does not repeat it. A first read on spotting the trap is the Simpson's paradox section of Probability & Statistics (34/05). Aggregates can reverse: Simpson's paradox In the fall of 1973, the University of California, Berkeley received 8,442 graduate applications from men and 4,321 from women. About 44% of the men and 35% of the women were admitted. It looks like proof of bias against women, and a lawsuit was threatened. Peter Bickel, Eugene Hammel and J. W. O'Connell looked inside (Science, 1975). Admissions are decided department by department, so they went there. Take the six largest departments (anonymised as A to F in the paper). Together, 45% of the men and 30% of the women were admitted. But in four of the six departments, a higher share of women than men were admitted. The reason is where people applied. Women applied in large numbers to departments that rejected most applicants (in C to F, admission rates of 35% or less in the table below); men applied heavily to A and B, which admitted nearly two thirds. A fact about the whole reverses inside every part: Simpson's paradox. Interactive · Berkeley, 1973 (real data, six largest departments) Source: Bickel, Hammel and O'Connell, Science 187 (1975); the figures are those of the six largest departments as commonly reproduced (the R dataset UCBAdmissions). Departments were anonymised in the paper. Without JavaScript: pooled, 44.5% of 2,691 men and 30.4% of 1,835 women were admitted. In departments A, B, D and F women's rates were higher; in C and E men's were. If women had applied in the men's proportions, the same department rates would give 51.6%. The tempting lesson, "always look at the subgroups", is wrong. The right lesson is that the data cannot tell you which view answers the question. If the question is "does a department discriminate in its decisions?", the department-level numbers are the right ones. If the question is "why do far fewer women end up in the programmes that admit most?", the pooled view and the earlier steps (who is encouraged to apply where) become the story. Which table to trust depends on the causal arrows, and the next sections give you a way to draw them. Bickel and colleagues concluded that the pooled gap came from where people applied, and that the department-level data showed, if anything, a small bias favouring women. The missing counterfactual, and why a coin fixes it The language that makes this precise is simple. Every person has two potential outcomes: how they would do if treated, and how they would do if not. Call them Y(1) and Y(0). The effect on that person is the difference. And we can never see both, because each person is treated or not: this is "the fundamental problem of causal inference" (Paul Holland's phrase, 1986). Every causal estimate fills in the missing half with a stand-in group, and the whole subject is about when the stand-in is fair. average effect = average of Y(1) − Y(0) over everyonewhat we want. What we can compute is: average of Y among the treated − average of Y among the untreated The two agree when who gets treated has nothing to do with how people would have done anyway. They disagree when it does: if sicker people seek out the treatment, the treated group does worse on average, and the treatment looks harmful even when it helps each person. Below are 200 invented patients. The treatment truly raises everyone's recovery score by 6. Turn up how strongly the sicker patients choose treatment, then press "Peek" to see the column nobody gets to see in real life. Interactive · Who chose the treatment? (invented patients) How strongly sicker patients seek treatment0.5 Peek at the hidden column Invented data. Recovery without treatment is 70 minus 30 times severity (severity 0 to 1) plus noise; treatment adds exactly 6 for everyone. Without JavaScript: when sicker patients are much more likely to choose treatment, the treated group's average recovery is about 4 points below the untreated group's, although the treatment adds 6. Randomisation breaks the link. If a coin decides who is treated, the two groups are alike in everything: severity, motivation, genes, luck, and things nobody measured. On average the treated-minus-untreated difference then equals the true average effect. "On average" matters: one experiment can still be off by chance, so repeat it and watch. Interactive · The same study, 300 times How strongly sicker patients seek treatment1 Run 300 studies patients choose   coin flip assigns estimated effect, from -6 to 14 (true effect: 6) Press the button. Without JavaScript: in 300 simulated studies at full selection, patient-chosen treatment gave an average estimate of -4.0 (5th to 95th percentile -5.5 to -2.3); coin-flip assignment gave 6.1 (3.7 to 8.2). The truth is 6. Notice two things. The coin's estimates scatter around the truth, with the scatter set by sample size. The self-selected estimates scatter around the wrong number, and a bigger sample would only make them confidently wrong. Draw the arrows first: confounders, mediators and colliders Randomisation is the gold standard but often impossible or unethical: you cannot assign people to smoke. Then you rely on assumptions about how the data came to be, and Pearl's causal diagrams (directed acyclic graphs) make those assumptions visible. Each arrow says "this directly affects that". Three shapes cover most of what goes wrong: Confounder (a fork): something that affects both the treatment and the outcome. Hot weather raises ice-cream sales and drownings. Compare like with like, that is, adjust for it. Mediator (a chain): part of the route by which the treatment works. Exercise lowers resting heart rate partly by raising fitness. Adjust for it and you remove part of the effect you wanted; whether that is right depends on the question (total effect or direct effect). Collider (an inverted fork): something affected by both. Among famous actors, talent and looks can appear to trade off, simply because you need enough of one or the other to be famous. Adjusting for a collider, or selecting on it, creates a link that was not there. Joseph Berkson described the hospital version in 1946. The surprising part is the last: adding a control variable can make an estimate worse. The rule is not "adjust for everything you have". It is "adjust for what the diagram says you should". Try each story below on simulated data in which the true answer is known. Interactive · Adjust, or not? (simulated data, 4,000 people) Adjust for the middle variable: off Each story is simulated with known arrow strengths and the slope of Y on X is fitted by least squares, with or without the other variable. Names and numbers are illustrative. Without JavaScript: in the heat story, the raw slope is about 0.63 and falls to about 0 after adjusting. In the fame story it is about 0 raw and about -0.8 after adjusting. In the exercise story the raw slope of -0.60 is the total effect, and adjusting leaves only the direct part, -0.2. Experiments in practice: noise, power and peeking Most experiments today are A/B tests. Half the visitors see version A, half see B, a coin decides, and you compare a metric such as the share who buy. The logic is exactly that of the previous section, so the worry is noise rather than bias. Suppose 10% of visitors buy, and the change really adds one percentage point. With 5,000 visitors per arm, the difference you observe wobbles by about 0.6 points from chance alone, so a one-point effect is only 1.7 wobbles tall. A standard rule of thumb (Lehr's formula, in van Belle's Statistical Rules of Thumb) says you need roughly this many per arm for 80% power at the 5% level: n per arm ≈ 16 × p(1 − p) ÷ (effect)²for p = 0.10 and an effect of 0.01, that is 16 × 0.09 ÷ 0.0001 = 14,400 per arm Power is the chance that a real effect is detected. Underpowered tests miss real effects, and, because only the lucky big estimates reach significance, the winners they do find exaggerate the effect. The second trap is peeking. If you look at the running result every day and stop the first time p dips under 0.05, you are giving chance many tries. With ten looks, a test with no true effect declares a winner about 19% of the time (in the run below), not 5%. Sequential tests exist that allow peeking honestly, and are what large experimentation platforms use. A third trap is the number of metrics: with 20 independent metrics and no real effect, the chance that at least one shows p below 0.05 is 1 − 0.9520, about 64%. Interactive · How often does a test "win"? True lift in conversion (percentage points)0 Peek 10 times and stop at the first p < 0.05: offRun 400 experiments Baseline conversion is 10%. Press Run. Each run draws every visitor at random and tests the difference in proportions (two-sided z-test). With only 400 runs the percentages carry a couple of points of noise. Without JavaScript: with a true lift of 0, 400 experiments of 1,000 visitors per arm give a "winner" about 4% of the time if you look once, and about 19% if you peek ten times. With 5,000 per arm and a true one-point lift, about 37% win with a single look. Interference: when your treatment changes the control Everything above quietly assumed that one person's treatment does not affect another's outcome. Rubin called this the "stable unit treatment value assumption". It fails whenever units compete or talk. Vaccinate half a town and the unvaccinated are protected too. Give half the sellers on a marketplace a discount and they take sales from the other half. Show half of a social network's users a new feed and their friends in the control group are affected. The marketplace case is the clearest. Suppose 100 sellers share a fixed pool of 1,000 buyers. In a test, a randomly chosen share gets a discount that makes them more attractive. The test compares treated sellers with control sellers and reports a big lift. But much of it was taken from the controls. If everyone got the discount, nothing would change in a fixed market. Engineers meet this in two-sided platforms, ride-hailing and ad auctions, and respond with experiments randomised by whole cities, regions or time blocks, which cost power but keep the arms from touching. Interactive · A discount test on a marketplace (illustrative model) Share of sellers in the test group50% How much more attractive the discount makes a seller1.5× Extra buyers drawn in if everyone discounts0% Model: 100 sellers, about 1,000 buyers; each buyer picks a seller with probability proportional to attractiveness (1 for a normal seller). The extra-buyers slider is an assumption about how much total demand grows with the share discounting. Sales are per seller per day. Without JavaScript: with half the sellers discounted at 1.5 times as attractive and no extra demand, treated sellers sell 12 a day and control sellers 8. The test reports +50%. Giving everyone the discount changes nothing, so the true roll-out effect is 0%. When you cannot randomise: adjust for what you measured, fear what you did not With observational data, the standard move is to compare like with like on everything you recorded: split people into groups with similar severity (strata), match them, or model the chance of treatment from their characteristics (a propensity score, Rosenbaum and Rubin, 1983). If every factor that drives both treatment and outcome was measured, this works. The fatal catch is that you can never check that "if". The question to ask of every observational claim is: what unmeasured thing might have pushed people into the treatment and changed their outcome? Analysts now quantify how strong such a hidden factor would have to be to erase a result, with tools such as the E-value (VanderWeele and Ding, 2017). Where a rule or an accident acts like a coin flip, you can do better than adjustment: a policy that hit one state but not its neighbour (difference-in-differences), a lottery that nudged people (instrumental variables), a cutoff that put near-identical people on either side (regression discontinuity), or a weighted blend of untreated places built to match the treated one (synthetic control, Abadie and colleagues). The 2021 economics Nobel prize went to David Card, and to Joshua Angrist and Guido Imbens, for this credibility revolution; Econometrics (34/44) works through three of them. Try the first idea here, and then the limit. Interactive · Adjust for severity, but what about the hidden factor? (simulated) Strength of an unmeasured factor (frailty)0 4,000 simulated patients. Severity is recorded; frailty is not, and it affects both who gets treated and how they fare. The true effect of treatment is +5. "Adjusted" compares treated and untreated within five severity bands and averages. Without JavaScript: with no hidden factor, the raw difference is about -1.1 (the treatment looks harmful), and adjusting for severity gives about 4.7 against a truth of 5. With a hidden factor of strength 5, adjusting gives about -2.8. What a graduate just sees A causal claim compares what happened with what would have happened, and the second is never observed. A pooled number and a within-group number can point opposite ways; the causal story decides which answers the question. Randomisation is powerful because it balances what nobody measured, not because it is a ritual. Draw the arrows before the regression: adjust for confounders, think twice about mediators, never for colliders. Adding more controls is not always safer, and an unmeasured confounder is a risk that no sample size removes. An A/B test is a noisy instrument: ask for the sample size, the number of looks and the number of metrics. If units can affect each other, the treated-versus-control gap is not the effect of a roll-out. Effects differ across people; an average can hide who gains and who loses, and the right answer depends on who is being asked about. Where it shows up next Econometrics (34/44): the natural-experiment toolkit, applied to prices, schooling and minimum wages. Research Methods in Psychology (35/19): experiments, effect sizes, power and the replication crisis are this piece's tools in another field. Data Ethics, Privacy & Fairness (36/37): "did the algorithm cause this disparity?" is a causal question, and fairness definitions differ in their causal assumptions. In the world: drug trials and vaccine studies, product teams at every large web company, development economics (randomised trials of schooling and cash transfers, Nobel 2019), and policy evaluation by governments. If you want to go deeper 📘 Textbook. Miguel Hernán and James Robins, Causal Inference: What If (Chapman & Hall/CRC, 2020), free from Hernán's Harvard page, rigorous and diagram-based; and Guido Imbens and Donald Rubin, Causal Inference for Statistics, Social, and Biomedical Sciences (Cambridge University Press, 2015), for potential outcomes. 📘 For experiments. Ron Kohavi, Diane Tang and Ya Xu, Trustworthy Online Controlled Experiments (Cambridge University Press, 2020), written from running experiments at large technology companies. 📘 Gentler. Judea Pearl and Dana Mackenzie, The Book of Why (2018), and Joshua Angrist and Jörn-Steffen Pischke, Mastering 'Metrics (Princeton, 2015), a short, friendly tour of the econometric toolkit. Scott Cunningham's Causal Inference: The Mixtape (Yale University Press, 2021) is also available to read free online. 🌐 Free course. MIT OpenCourseWare 14.387 Applied Econometrics: Mostly Harmless Big Data (Fall 2014, Angrist and Chernozhukov), a graduate-level course whose notes and problem sets are public. The takeaway Causal questions are about what would have happened otherwise, and only a fair stand-in for that answers them. A coin flip is the most reliable stand-in; failing that, draw the story, adjust only for what the diagram says, and say out loud what you could not measure. Try this: take any "X is linked to Y" headline this week and write down one confounder, one possible reversal of direction, and what a randomised version of the study would look like. If you cannot imagine the experiment, you have found why it is hard. Sources & Further Reading Sources. Rossouw et al., JAMA 288 (2002), Writing Group for the Women's Health Initiative; Fisher, The Design of Experiments (1935); Neyman 1923 (translated in Statistical Science 1990); Rubin, Journal of Educational Psychology 1974 and "Randomization analysis of experimental data," JASA 1980; Holland, "Statistics and causal inference," JASA 1986; Pearl, Causality (2000); Berkson, Biometrics Bulletin 1946; Bickel, Hammel and O'Connell, "Sex bias in graduate admissions: data from Berkeley," Science 187 (1975), 398–404 (department-level counts for A to F as reproduced in the R dataset UCBAdmissions and in Wikipedia, "Simpson's paradox"); Rosenbaum and Rubin, Biometrika 1983; VanderWeele and Ding, Annals of Internal Medicine 2017; Abadie, Diamond and Hainmueller, JASA 2010; van Belle, Statistical Rules of Thumb (2nd ed. 2008); Nobel Prize in Economic Sciences 2019 (Banerjee, Duflo, Kremer) and 2021 (Card; Angrist and Imbens). All simulations, percentages and rules of thumb in the text were computed in node. Patients, sellers and visitors are invented. 📘 Hernán and Robins, Causal Inference: What If 📘 Kohavi, Tang and Xu, Trustworthy Online Controlled Experiments 🌐 MIT OCW 14.387 Step 11. Econometrics: How to Find What Caused What --------------------------------------------------- Why: How economists draw causes out of observational data. Correlation is cheap. Econometrics is the craft of getting from "these move together" to "this made that happen", and of knowing how badly you could be fooled on the way. A city opens a new tram line, and a year later house prices along it have risen. Did the tram do it? Maybe. Or maybe the city built the line where it already expected the area to boom. Or a new university opened nearby the same year. Every headline that says "X is linked to Y" hides this question, and most of the time the headline cannot answer it. An economist sees the same pattern in a minimum-wage law, a school-class size, a tax change, a drug trial. The data show a link. The job is to say what the link would have been if nothing else had been going on. That is econometrics: statistics built for questions where you usually cannot run the experiment, and where the people in your data chose their own circumstances. The course in one box Who takes itEconomics majors, usually in year 2 or 3, straight after a first statistics course. Public policy, political science, finance and business-analytics programmes teach close cousins. Programmes such as MIT's Course 14-1, the LSE and Chicago all require it. What it is forEstimating the effect of one thing on another from messy real-world data, with an honest statement of how wrong the estimate might be. Comes afterProbability & Statistics (34/05). Leads toDevelopment Economics (34/48), and it is the working tool in Behavioral Economics (34/46), Marketing Research & Analytics (34/59) and Machine Learning (34/32). What this piece gives youYou will not be able to run a regression package after this. You will see why a coefficient can lie, what a clever study does to stop it lying, and why a "significant" result is weaker evidence than it sounds. It goes further than Probability & Statistics (34/05), whose last section stops at "correlation is not causation"; here is what to do about it. The library's How to Spot Bullshit (17/03) is a gentler start. All datasets here are invented and labelled illustrative. Regression is the best-fitting line Take twelve students: hours studied, and the score each got. Plot them and the dots drift upward. A regression draws the one straight line that sits closest to all the dots. "Closest" has a precise meaning: for each dot, measure the vertical gap to the line (the residual), square it, and add up the squares. The line with the smallest total is the ordinary least squares (OLS) line. Squaring means one big miss counts far more than several small ones; the picture shows each squared miss as a literal square. score = a + b × hours + errorb is the slope: the score gap between two students who differ by one hour Interactive · Fit the line yourself (illustrative data) Slope b (points per hour) Intercept a (score at 0 hours) Snap to the best line Twelve invented students. The best line is found by solving the least-squares equations; no other line has a smaller sum of squared misses. The best line here is about 47 + 3.5 × hours (the readout gives it exactly). The coefficient b says: students who studied an hour more scored about 3.5 points higher. Notice what that sentence does not say. It compares different students. It does not say that making one student study an extra hour would raise her score by 3.5. That gap, between a comparison and a cause, is the rest of the course. Omitted variables: add the confounder, watch the effect change Suppose you regress wages on years of schooling in a big survey and find that each extra year goes with higher pay. Is that what schooling does? People with more drive or talent may both stay in school longer and earn more anyway. If so, the schooling coefficient is also soaking up the talent effect. This is omitted-variable bias, and it has a tidy rule: bias ≈ (effect of the omitted factor on the outcome) × (how strongly it moves with your variable)if either is zero, there is no bias In the lab below, the true effect of one more year of schooling is exactly 3 (thousand dollars). Talent also raises pay, and a dial sets how strongly talent pushes people toward more school. Switch the model between ignoring talent and including it. Interactive · The hidden confounder (illustrative simulation, 1,500 people) How strongly talent pushes people to stay in school Ignore talent Control for talent Randomise schooling above-average talent   below-average talent True schooling effect = 3.0; talent adds 8 per standard deviation. Wage = 10 + 3·school + 8·talent + noise. "Randomise" means a coin-flip-like process assigns schooling regardless of talent. Without JavaScript: with talent pushing schooling at strength 1.2, ignoring talent gives a schooling coefficient near 4.7 instead of the true 3.0; controlling for talent recovers about 3.0; randomising schooling also recovers about 3.0. Ignoring talent at strength 1.2 gives about 4.7, over half again too large. Control for talent and it falls to about 3. The cost of this fix: you must measure the confounder. Most real confounders (motivation, family connections, how well-run the firm is) sit in no dataset. That is why economists spent decades arguing about what regressions could prove. Randomise: the coin that cuts every hidden link Press the third button. When schooling is assigned by a process unrelated to talent, the link between them is broken, and even the naive regression that ignores talent lands on 3. A coin flip is independent of everything: motivation, family, luck, things nobody thought to measure. That is why a randomised experiment is the gold standard, and why 2019's Nobel prize in economics went to Abhijit Banerjee, Esther Duflo and Michael Kremer for experimental approaches to reducing poverty. But economists rarely get to flip the coin: you cannot randomly assign years of schooling, a recession or a minimum wage. The next three ideas are ways to find a coin that nature or a rule has already flipped. Together they are called the credibility revolution, a phrase from Joshua Angrist and Jörn-Steffen Pischke's 2010 essay, answering Edward Leamer's 1983 complaint that econometrics needed to "take the con out" of itself. Difference-in-differences: borrow the other group's trend In 1992 New Jersey raised its minimum wage and neighbouring Pennsylvania did not. David Card and Alan Krueger surveyed fast-food restaurants in both states before and after (American Economic Review, 1994). Looking only at New Jersey before and after would confuse the law with anything else changing that year. Instead they used Pennsylvania as the stand-in for "what would have happened anyway". Their finding, that employment did not fall in New Jersey, contradicted the textbook prediction at the time. It has been disputed ever since: Neumark and Wascher re-analysed it with payroll records and found job losses, and the field's overall reading is still argued over. The design is not in dispute. Card shared the 2021 Nobel prize in part for it. effect = (treated after − treated before) − (comparison after − comparison before)subtract the comparison group's change to remove the common trend Interactive · Difference-in-differences (illustrative numbers) Common trend (hits both groups) True effect of the policy Treated group was already drifting differently Treated group starts at 20, comparison at 24 (invented units). Dashed line: where the treated group would have gone without the policy, if it followed the comparison's trend. With a common trend of +1.5 and no true effect, the treated group still rises by 1.5, so a naive "before and after" would claim a policy success. The difference-in-differences correctly says zero. The design's weak point is the third slider: it assumes the two groups would have moved in parallel without the policy. If the treated group was already on a different path, the estimate is off by exactly that gap. Good papers show the two lines tracking each other for years before the policy. Instruments and cutoffs: two more ways to find a coin An instrumental variable is something that nudges the thing you care about but has no other route to the outcome. Angrist (1990) studied whether military service in the Vietnam era changed later earnings. Men who chose to serve differ from those who did not, so a plain comparison is confounded. But the draft lottery assigned numbers by birthday at random, and a low number made service much more likely. The lottery number is a coin that pushes people into uniform. Its effect on earnings, divided by its effect on service, isolates the effect of service for the people who served because of the lottery. His study found that service lowered earnings for the veterans concerned. effect of service = (earnings gap by lottery group) ÷ (service gap by lottery group)the "Wald" ratio: reduced form over first stage A worked number, invented to show the arithmetic: suppose 35% of low-number men served and 20% of high-number men, a first stage of 0.15; and low-number men earned $300 less a year on average. Then the estimated effect of serving is −300 ÷ 0.15 = −$2,000 a year. Dividing by a small first stage blows up noise, which is why weak instruments are dangerous. A regression discontinuity uses a cut-off. Israeli school classes are capped at 40 pupils under a rule attributed to the twelfth-century scholar Maimonides, so a school with 40 pupils has one class and a school with 41 splits into two small classes of about 20. Angrist and Lavy (1999) compared schools just either side of those thresholds, where enrolment is close to a coin flip, to estimate what class size does to test scores. Slide the window below: narrow windows are fairer but noisier. Interactive · Regression discontinuity (illustrative data) Window around the cut-off (± points) True jump at the cut-off 400 invented students; those scoring 60 or more get a support programme. Outcome rises 0.3 per score point anyway, so just comparing everyone above with everyone below overstates the jump. Standard errors: how much would the answer wobble? Every estimate comes from one sample, and a different sample would have given a different number. The standard error is the typical size of that wobble. For a regression slope it shrinks with the square root of the sample size, grows with the noise around the line, and shrinks when x varies a lot: SE(b) ≈ (noise around the line) ÷ ( spread of x × √n )four times the data halves the wobble The rule of thumb: an estimate more than about two standard errors from zero is called statistically significant at the 5% level. Significant means "hard to produce by sampling wobble alone if the true effect were zero". It does not mean big or important, and it does not mean true. Run 300 studies of a real but modest effect below and see who gets stars. Interactive · Run 300 studies (illustrative simulation) Sample size per study True slope Run 300 new studies significant at 5%   not significant At n = 50 and a true slope of 0.3, a little over half of the studies reach significance, and those average about 0.40, a third above the truth, because only the lucky overestimates clear the bar. Drop to n = 10 and a true slope of 0.05 and the few stars (about 8%) average roughly 0.7, fourteen times too big. Published results are mostly the significant ones, so they exaggerate. That is one reason newer replications so often find smaller effects. P-hacking: test enough things and something will glow A test at the 5% level is wrong by chance 1 time in 20 when nothing is going on. Test 20 unrelated outcomes and the chance that at least one glows is 1 − 0.9520 = 64%. A researcher who tries several outcomes, subgroups or control sets and reports the one that "worked" is p-hacking, whether on purpose or just by wandering a garden of forking paths. Simmons, Nelson and Simonsohn (2011) showed how easy it is: using flexible, ordinary-looking choices they "found" that listening to a song about being older made students younger by about a year and a half. Economists are not exempt: Brodeur and co-authors (2016) found an unnatural pile-up of results just below the 0.05 line in top economics journals. Interactive · A study of nothing (illustrative simulation) Outcomes you test (all truly unaffected) Run one studyRun 500 studies Each outcome compares two groups of 50 drawn from the same distribution, so every "effect" is noise. A cell lights up when |t| passes the 5% cut-off (1.98). Defences: decide the analysis before seeing the data (pre-registration), report every test you ran, adjust the threshold when you run many, and above all prefer designs, like the ones above, where the answer does not depend on which controls you picked. What a graduate just sees A regression coefficient is a comparison between different people, not a lever you can pull. Before believing "X raises Y", ask what else moves with X and also moves Y. The bias is its effect times its link to X. Adding controls can only fix confounders you measured. A coin flip fixes the ones you did not. Every natural-experiment study is a hunt for a coin: a lottery, a border, a cut-off, a law that changed for some and not others. Difference-in-differences needs parallel trends; ask to see the years before the policy. "Significant" means hard to get from wobble alone. It says nothing about size, and a small-sample star probably overstates. If you can run twenty tests, one will light up. Ask how many were run. Where it shows up next Development Economics (34/48): randomised trials and natural experiments are how economists test what actually helps poor countries. Behavioral Economics (34/46): the replication record in that piece depends on this one, from effect sizes to p-hacking. Marketing Research & Analytics (34/59): "did the campaign cause the sales, or did summer?" is difference-in-differences. Machine Learning (34/32): prediction asks "what will happen"; econometrics asks "what would happen if I changed it". They need each other. In the world: central banks and tax agencies, tech companies' A/B test teams, public-health trials, and every think-tank report that says "causes". If you want to go deeper 📘 Textbook. James Stock and Mark Watson, Introduction to Econometrics (Pearson). A standard undergraduate text, strong on causal thinking and applications. 📘 Textbook. Jeffrey Wooldridge, Introductory Econometrics: A Modern Approach (Cengage). The other standard choice, more algebra and more worked data. 📘 Gentler. Joshua Angrist and Jörn-Steffen Pischke, Mastering 'Metrics: The Path from Cause to Effect (Princeton, 2015). Written for people who are not specialists, built around exactly the designs above. 🌐 Free course. MIT OpenCourseWare 14.32 Econometrics (Spring 2007, Joshua Angrist): undergraduate course with lecture notes and problem sets. The takeaway A regression gives you a comparison, and a comparison is only a cause if nothing else differs between the groups. Econometrics is a toolkit for making that true or nearly true (randomise, difference out a trend, use a lottery, zoom in on a cut-off), plus the humility to report how much your number would wobble and how many ways you tried. Try this: the next time a headline says "X linked to Y", name one confounder that could drive both, and ask what coin flip, border or cut-off could separate them. Sources & Further Reading Sources. Least squares, omitted-variable bias, standard errors and the Wald estimator are standard textbook material (Stock & Watson; Wooldridge; Angrist & Pischke). Card & Krueger, "Minimum Wages and Employment: A Case Study of the Fast-Food Industry in New Jersey and Pennsylvania," American Economic Review 84(4), 1994; the Nobel Prize in Economic Sciences 2021 went to David Card (half) and Joshua Angrist and Guido Imbens (half, "for their methodological contributions to the analysis of causal relationships"). Angrist, "Lifetime Earnings and the Vietnam Era Draft Lottery," 1990; Angrist & Lavy, "Using Maimonides' Rule to Estimate the Effect of Class Size on Scholastic Achievement," 1999; regression discontinuity was introduced by Thistlethwaite & Campbell in 1960. Angrist & Pischke, "The Credibility Revolution in Empirical Economics," Journal of Economic Perspectives 2010; Leamer, "Let's Take the Con out of Econometrics," 1983. Simmons, Nelson & Simonsohn, "False-Positive Psychology," 2011; Brodeur, Lé, Sangnier & Zylberberg, "Star Wars: The Empirics Strike Back," 2016. The 2019 economics Nobel went to Banerjee, Duflo and Kremer. Every number an interactive shows was computed in node from the code on this page: the best line is 47.0 + 3.53 × hours; omitted-variable bias at strength 1.2 is 8 × 1.2 ÷ (1.2² + 4) = 1.76 in theory (1.67 in this sample); 1 − 0.9520 = 64.2%. All datasets are invented. 🌐 MIT OCW 14.32 Econometrics 📘 Angrist & Pischke, Mastering 'Metrics 📘 Stock & Watson, Introduction to Econometrics Step 12. Machine Learning: Programs That Write Their Own Rules -------------------------------------------------------------- Why: Machine learning: prediction 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 13. Deep Learning: How Stacked Simple Layers Learn to See -------------------------------------------------------------- Why: Neural networks and why they took over. A deep network is a long chain of small bends, trained by sliding downhill. Once you have felt why depth, sharing, steady gradients and a little restraint matter, every modern model looks like a variation on a few moves. Point your phone at a street sign in another language and the words turn into your own, drawn over the live picture. Ask it to find "dog" in ten thousand photos and it does. Twenty years ago both would have been research projects with a few percent of the accuracy. Nobody wrote a rule for what a dog looks like. A network with tens of millions of adjustable numbers was shown labelled pictures and nudged until its guesses improved. The previous course, Machine Learning (34/32), taught the loop: a model with knobs, a score for how wrong it is, and gradient descent to turn the knobs. Deep learning is that loop applied to a very particular kind of model, one made of many layers, and the engineering that makes the loop work when the model is deep, wide and hungry for data. A graduate keeps a short list of facts about why this works at all and what breaks when it does not. The first widely noticed success was in 2012. A convolutional network called AlexNet, trained by Alex Krizhevsky, Ilya Sutskever and Geoffrey Hinton on two gaming graphics cards, reached a 15.3% top-5 error rate on the ImageNet photo-recognition contest, more than ten percentage points better than the runner-up. In 2018 Yoshua Bengio, Geoffrey Hinton and Yann LeCun received the Turing Award for their work on deep networks, and in 2024 John Hopfield and Hinton shared the Nobel Prize in Physics for foundational work on artificial neural networks. The course in one box Who takes itComputer science and data science majors, usually in year 4 or as a graduate elective; also engineering and physics students. Typical courses are Stanford's CS230 and CS231n (convolutional networks for vision) and the deep-learning courses at MIT, Toronto and Montréal. Most start from backpropagation and end at transformers. What it is forBuilding and training models made of many layers, and understanding why the training succeeds, fails or generalises. Comes afterMachine Learning (34/32) and Multivariable Calculus (34/02). Leads toNo later subject in this major lists it as a prerequisite. It feeds Data Ethics, Privacy & Fairness (36/37), where these models' harms are weighed, and Computational Linguistics (36/30), where language models are the central tool. What this piece gives youYou will not be able to train a large model after this. You will see six things that explain most of what goes right and wrong. Easier first reads: Machine Learning (34/32), which covers the training loop, overfitting and a small network learning XOR, and How Large Language Models Actually Work (29/02), which covers tokens, embeddings and what attention does. This piece goes underneath them and does not repeat them. Depth: stacked bends that fold the input A layer of a modern network does two things. It takes weighted sums of its inputs, then bends the result with a simple non-linear function. The most common bend is the ReLU: pass positive numbers through unchanged, replace negatives with zero. With ReLUs, a whole network is a patchwork of flat straight pieces joined at kinks. One hidden layer is already enough, in principle, to approximate any smooth function: this is the universal approximation theorem (Cybenko and Hornik, both 1989). But the theorem says nothing about how wide that layer must be, and the answer can be absurd. Depth is the cheaper route. Each layer takes the output of the one below and bends it again, so the number of pieces can multiply from layer to layer instead of merely adding. Telgarsky (2016) gave a clean example, and you can build it here. tent(x) = 2·ReLU(x) − 4·ReLU(x − ½)two ReLU units make a triangle on 0 to 1: it rises to 1 at ½ and falls back to 0. Feed the result into the same two units again, and again. Each pass folds the interval in half, like folding a strip of paper. After k folds the curve has 2k straight pieces, built from only 2k hidden units. A single hidden layer with 2k units can make at most 2k + 1 pieces on a line. Interactive · Fold the input Layers stacked (2 ReLU units each)3 Computed by running real ReLU units layer on layer; pieces are counted from the slope changes of the curve. The point is the growth rate, not that folding paper is a useful model. Without JavaScript: 3 stacked layers use 6 hidden units and make 8 straight pieces; one wide layer with 6 units makes at most 7. At 7 layers it is 128 against 15. That is the intuition a graduate keeps. Depth lets a network reuse the same cheap building block at every scale, so a pattern like "an eye, in a face, in a crowd" can be built from parts of parts. Real networks do not fold exactly, and the theory of why deep nets are so effective in practice is still active research. But the exponential count of pieces is a real result (Montúfar and colleagues, 2014, proved bounds of this kind), and it is the first reason why people stacked layers instead of widening one. Convolution: one small detector slid everywhere A photo of 224 by 224 pixels in three colours has 150,528 numbers. A fully connected layer that maps them to just 1,000 units needs 150,528 × 1,000 = about 150 million weights. That is too many to learn, and it is also silly: a cat in the corner and a cat in the centre would need to be learned separately. A convolutional layer makes two bets. Nearby pixels matter together, so each unit looks at a small patch, say 3 by 3. And a useful detector in one place is useful in every place, so the same small set of weights, a filter, slides across the whole image. That layer with 64 filters over a three-colour image has 3 × 3 × 3 × 64 = 1,728 weights, whatever the size of the picture. output(y, x) = sum over the 3 × 3 patch of (weight × pixel)deep-learning libraries compute this cross-correlation and call it convolution; the difference is only a flip of the filter Stacked layers build up features: the first finds edges, the next corners and textures, later ones parts of objects. Yann LeCun's group used this design on handwritten zip codes in 1989 and refined it into LeNet-5 by 1998. AlexNet in 2012 was the same idea with more data, more layers and graphics cards. Try the filters below on a small picture. Interactive · A filter slides over a picture Tap pixels to draw. Output cells are warm where the filter responds positively, cold where negative. Picture (8 × 8) Output (6 × 6) Shift picture 1 pixel right Without JavaScript: a vertical-edge filter responds on the left and right sides of a filled square and nowhere else. Slide the square one pixel and the responses slide with it. The sliding gives a property worth naming: equivariance. Move the cat and the pattern of responses moves with it. The sharing is also why convolutional nets need far less data than a dense net on pictures. When a graduate looks at a new data type, they ask the same question: what is the symmetry here, and can one shared detector exploit it? Sound has time, graphs have neighbours, molecules have rotations. Deep chains fade or explode, and skip connections fix it Backpropagation (taught in Machine Learning, 34/32) sends the error signal backwards through the layers, and at every layer it is multiplied by that layer's weights and by the slope of its bend. Multiply thirty numbers together and the outcome depends strongly on whether each is a bit below one or a bit above. Below one, the signal reaching the early layers shrinks to nothing and those layers stop learning: the vanishing gradient, analysed in Sepp Hochreiter's 1991 diploma thesis. Above one, it blows up. The classic bend, the sigmoid, makes this worse. Its slope is never more than ¼, so even with weights of the right size, thirty layers can multiply the signal by something like 0.2530, about 10-18. The remedies are one of the stories of the field, and a graduate knows them as a list: A bend with slope 1 on its active side (ReLU), widely adopted around 2010 to 2012. Careful starting weights, scaled by layer width: Glorot and Bengio (2010) for sigmoid-like bends and He and colleagues (2015) for ReLU. Normalisation layers, such as batch normalisation (Ioffe and Szegedy, 2015). Skip connections, the key idea of residual networks: each block outputs x + F(x), so the signal has a direct path to the input. ResNet (He, Zhang, Ren and Sun) trained a 152-layer network and won the 2015 ImageNet contest. Interactive · The gradient on its way back Skip connections: off Layers20 A real forward and backward pass through a random 20-unit-wide network, computed in the page. The vertical axis is the base-10 logarithm of the gradient's size, with the output end set to 1. Weight scale is a multiple of 1/√20 (about 0.22). Without JavaScript: with sigmoid bends, scale 1 and 30 layers, the gradient reaching the first layer is about 10-19 of the one at the output. With skip connections it stays near 1. Notice what the skip does and does not do. At scale 1.4 with ReLU, the skip grows the signal instead: residual branches have to start small (practitioners scale or zero-initialise them) so that stacking a hundred of them stays tame. The lesson a graduate keeps is not a recipe but a diagnosis. When a deep network does not train, check how big the signal is at each layer, forwards and backwards. Optimisers: momentum and Adam in a narrow valley Plain gradient descent steps straight downhill. In a long narrow valley, downhill points mostly at the valley's nearest wall, so the steps zigzag across it while creeping along the floor. Raise the learning rate to hurry and the zigzag grows until it diverges. The valley below is the simplest case, a bowl 5 times narrower in one direction than the other (curvature 25 against 1). For this bowl, gradient descent is stable only for learning rates below 2/25 = 0.08, a number you can derive in one line. Momentum (Polyak, 1964) lets the step remember its recent direction, like a ball with inertia: zigzags cancel, the steady push along the valley adds up. Adam (Kingma and Ba, 2014, published at ICLR 2015) also rescales each parameter's step by the typical size of its recent gradients, so steep and shallow directions get comparable steps. It is the default in much of deep learning, with variants such as AdamW, though careful momentum-based training still wins in some settings, and which is best is argued case by case. momentum: v ← 0.9·v + gradient; position ← position − rate·vAdam: divide a smoothed gradient by the square root of a smoothed squared gradient, per parameter Interactive · Three walkers, one valley Rate for plain and momentum0.03 Adam rate0.3 Steps taken30 plain gradient descent   momentum   Adam Loss = ½(x² + 25y²), start at (−4, 1). Start loss 20.5. Real loss landscapes have millions of dimensions; this only shows the zigzag problem. Without JavaScript: at rate 0.03 and 60 steps, plain descent reaches a loss of about 0.21, momentum about 0.019 and Adam (rate 0.3) about 0.0024. At rate 0.09 plain descent diverges. More knobs than data, and it still generalises The old rule from statistics said that a model with more parameters than data points will memorise the data and fail on new data. Deep networks routinely break the rule. Zhang and colleagues (ICLR 2017) showed that standard image networks can fit images with randomly shuffled labels perfectly, so they certainly have the capacity to memorise, and yet the same networks generalise well on real labels. Belkin and colleagues (PNAS, 2019) described a "double descent" curve: test error can rise as the model nears the point where it just fits the training data, then fall again as it grows larger. Why the large regime works is still being explained; the working summary is that the training process itself prefers simpler fits among the many that exist. Practice leans on a few restraints, all cheap to state: weight decay (a small penalty on large weights), early stopping (stop at the lowest validation error), dropout (randomly silence units during training, Srivastava and colleagues, 2014), and data augmentation (flip, crop and jitter the pictures). Try the first two on 12 noisy points from a sine wave. Interactive · Train a small network Training steps so far500 fit / training error   validation error   dashed: true sine One hidden layer of tanh units trained with Adam on 12 invented points (sine plus noise of 0.25). Validation uses 60 other noisy points. The noise alone limits any model to an error of about 0.06. Without JavaScript: with 50 hidden units and no decay the validation error is lowest (0.125) after about 450 steps and has risen to 0.181 by step 4,000 while training error keeps falling to 0.007. With a decay of 0.001 the final validation error is 0.131. Two cautions. A held-out set is still the only honest score, and the same split reused to choose settings slowly stops being a test (Machine Learning, 34/32). And all of this assumes new data resembles the old; a network that has never seen a rainy night can still be confidently wrong in one. Attention: why scores are divided by the square root of d How Large Language Models Actually Work (29/02) explains what attention does: every token compares its query with the other tokens' keys and takes a weighted mix of their values. Here is a detail that shows how a deep-learning researcher thinks. The comparison is a dot product of two vectors of length d. If the entries are independent numbers of typical size 1, a dot product adds d such products, and its typical size grows like the square root of d. Those scores then go through softmax, which turns them into weights that sum to 1. Softmax is hypersensitive to large inputs: when one score leads by a few units it takes nearly all the weight, and the gradient through it nearly vanishes, the same disease as the previous section. The transformer paper (Vaswani and colleagues, NeurIPS 2017) divides the scores by √d for this reason. The whole fix is one division. weights = softmax( (query · key) ÷ √d )without the division, big vectors give near-one-hot weights before any learning happens Interactive · Six keys, one query Vector length d64 400 random trials per setting in the page: random vectors with entries of typical size 1; each query is compared with six random keys. Even weights would give 0.17 to each. Without JavaScript: at d = 64 the scores have a typical size near 8, and the largest of six weights averages about 0.89 without scaling and about 0.42 with it. What a graduate just sees A network is a composition of simple bends; with ReLU it is a patchwork of straight pieces, and depth multiplies the number of pieces where width only adds. When the data has a symmetry (position, time, order), one shared detector beats a separate one for every location. Training a deep net is a signal-flow problem: if the gradient dies or explodes between layers, nothing else matters yet. Skip connections, sensible initialisation and normalisation exist to keep the signal about the same size at every depth. The optimiser matters most in badly shaped valleys; momentum and Adam are cures for zigzag and for mismatched scales. Memorising and generalising are different things, and the network that could memorise often does not. Only held-out data tells you which happened. Small details such as one division by √d can decide whether a design trains. Whether further scale is enough is argued: Richard Sutton's "The Bitter Lesson" (2019) says general methods plus computation have always won, while critics such as Gary Marcus (2018) argue deep learning alone will hit limits that need other ingredients. Where it shows up next Data Ethics, Privacy & Fairness (36/37): these models inherit patterns in their training data, and large ones can memorise and leak what they were trained on. Computational Linguistics (36/30): language models are deep networks trained to predict the next piece of text, with attention at the core. Big Data & Data Engineering (36/36): training runs on thousands of chips, and the data pipelines feeding them are an engineering field of their own. In the world: speech recognition and translation, medical-image screening tools under regulatory review, recommendation feeds, protein-structure prediction and weather emulators. If you want to go deeper 📘 Textbook. Ian Goodfellow, Yoshua Bengio and Aaron Courville, Deep Learning (MIT Press, 2016), the standard reference, free to read at deeplearningbook.org; and Simon Prince, Understanding Deep Learning (MIT Press, 2023), more recent and clearly illustrated, with a free draft at udlbook.github.io. 📘 Hands-on text. Aston Zhang, Zachary Lipton, Mu Li and Alexander Smola, Dive into Deep Learning, a free online book with runnable code at d2l.ai. ▶️ Gentler. Grant Sanderson's Neural Networks series on the 3Blue1Brown channel (2017 onward), for the pictures behind backpropagation, and Andrej Karpathy's Neural Networks: Zero to Hero video lectures, which build a small network and a language model from scratch. 🌐 Free course. Stanford's CS231n: Deep Learning for Computer Vision, whose notes and past lecture recordings are public; or Practical Deep Learning for Coders from fast.ai, a code-first free course. The takeaway Deep learning is gradient descent on layered functions, and most of the craft is keeping that machine healthy: depth for reuse, sharing to exploit symmetry, steady signals front to back, a good optimiser, and honest held-out data. The theory lags the practice, which is an invitation, not an embarrassment. Try this: next time a feature of your phone recognises something (a face, a word, a song), ask what the symmetry is. Is it the same pattern anywhere in the picture, anywhere in time? That question is how a deep-learning engineer starts. Sources & Further Reading Sources. Cybenko, Mathematics of Control, Signals and Systems 1989; Hornik, Stinchcombe and White, Neural Networks 1989; Telgarsky, "Benefits of depth in neural networks," COLT 2016; Montúfar, Pascanu, Cho and Bengio, "On the number of linear regions of deep neural networks," NeurIPS 2014; LeCun et al., Neural Computation 1989 and Proceedings of the IEEE 1998; Krizhevsky, Sutskever and Hinton, NeurIPS 2012 (15.3% top-5 error, more than 10.8 points ahead of the runner-up; summary on Wikipedia, "AlexNet"); Hochreiter, diploma thesis, TU München 1991; Glorot and Bengio, AISTATS 2010; He et al., "Delving deep into rectifiers," ICCV 2015 and "Deep residual learning for image recognition," CVPR 2016 (ILSVRC 2015 winner); Ioffe and Szegedy, ICML 2015; Polyak 1964; Kingma and Ba, arXiv 2014, ICLR 2015; Srivastava et al., JMLR 2014; Zhang et al., "Understanding deep learning requires rethinking generalization," ICLR 2017; Belkin, Hsu, Ma and Mandal, PNAS 116(32), 2019; Vaswani et al., "Attention is all you need," NeurIPS 2017; Sutton, "The Bitter Lesson," 2019; Marcus, "Deep learning: a critical appraisal," arXiv 2018; ACM A.M. Turing Award 2018 (Bengio, Hinton, LeCun), announced 2019; Nobel Prize in Physics 2024 (Hopfield, Hinton). Every number shown by the interactives, and the figures in the prose, were computed in node. 📘 Goodfellow, Bengio and Courville, Deep Learning 📘 Prince, Understanding Deep Learning 🌐 Stanford CS231n Step 14. Big Data & Data Engineering: What Changes When Data Outgrows One Computer ---------------------------------------------------------------------------------- Why: When data outgrows one computer. One disk reads a terabyte in about two hours; a hundred disks together read it in a minute. Everything in this subject is the price of getting that speed-up: splitting data, surviving broken machines, and keeping time straight. Type a few words into a search engine and the answer comes back in a fraction of a second, drawn from an index of many billions of pages. Your bank flags a suspicious payment while you are still standing at the till. A streaming service updates "what to watch next" for hundreds of millions of people overnight. None of that happens on one computer. None of it could. Data engineering begins at the moment one machine stops being enough: not enough disk, not enough memory, or just not enough time. The moment you spread a job over many machines, three new problems appear that did not exist before. Machines fail all the time, so the system must work with some of them gone. Data has to be divided in a way that lets the machines work independently. And there is no single clock, so "what happened first?" needs an answer. A graduate keeps these three problems in mind and knows the standard answers. A fair warning that experienced engineers repeat: many datasets labelled "big" fit comfortably on one modern server, and a single well-written program on one machine often beats a cluster. Frank McSherry, Michael Isard and Derek Murray made the point in a 2015 paper, "Scalability! But at what COST?", by showing a laptop outrunning several distributed systems on some graph tasks. The tools below are worth it only when the data or the speed really demands them. The course in one box Who takes itData science and computer science majors, usually in year 4 as an elective, or as a graduate course. Data-science programmes teach it as "data engineering" or "big data systems"; computer science departments teach the theory as distributed systems (for example MIT's 6.5840 and Stanford's CS246 on mining massive datasets). Much of it is learned on the job. What it is forStoring, moving and processing data that is too big, too fast or too important to live on one machine. Comes afterDatabases (34/28) and Operating Systems (34/26). Leads toNo later subject in this major lists it as a prerequisite. It feeds Deep Learning (36/35), whose training runs on pipelines like these, and Data Ethics, Privacy & Fairness (36/37), because data kept at scale must also be protected and deleted. What this piece gives youYou will not be able to run a production cluster after this. You will see how the arithmetic of scale works, how data is split and kept safe, and why time is hard. For how a single database keeps data safe and what the CAP theorem says, read Databases (34/28); this piece builds on it. One machine runs out: the arithmetic of scanning Start with the cheapest calculation in the subject. A hard disk can read sequentially at very roughly 150 megabytes a second, a SATA solid-state drive at about 500, and a fast NVMe drive at a few gigabytes a second. These are round figures that vary by model; the pattern matters, not the digits. A terabyte is a million megabytes, so one hard disk needs about 6,700 seconds, nearly two hours, to read it once. time = data size ÷ (number of disks × speed of each)if the data is split evenly and every disk works at once, a hundred disks cut two hours to about a minute That is the whole reason for the field. The catch is what else scales with the number of machines: failures. In 2024 Backblaze reported an annualised failure rate of 1.57% across about 299,000 of its drives. For one drive that is rare. For 10,000 drives it is about 157 failures a year, roughly three a week, so at that size a failure is routine, not an emergency. Systems built for scale assume parts will break and carry on. Try the arithmetic. Interactive · How long to read it all? Machines, each with one disk1 Illustrative round speeds, perfect even splitting and no network limits, which real jobs never have. Failure figure: Backblaze Drive Stats for 2024 (annualised failure rate 1.57%, about 299,000 drives). Without JavaScript: 1 TB on one hard disk at 150 MB/s takes about 1.9 hours; across 100 disks, about 67 seconds. 1,000 TB across 1,000 disks takes about 1.9 hours again. Partitioning: which machine holds which row? To use many machines you must decide where each piece of data lives. The simplest answer is a hash: run the key (a user ID) through a scrambling function and take the remainder when dividing by the number of machines. Every key lands on a predictable machine, and the load spreads evenly. It has one terrible flaw. Add a machine and the divisor changes, so almost every key now maps somewhere else, and nearly all your data must move. Going from 3 machines to 4 moves 3 keys in 4. Consistent hashing, introduced by David Karger and colleagues in 1997 for web caches, avoids this. Put the machines on a circle by hashing their names, and give each key to the first machine clockwise from its own hash. A new machine takes over only a slice of the circle, so about one key in N + 1 moves. Using many points per machine ("virtual nodes") evens out the load. Amazon's Dynamo (2007) and many databases built since use the idea. Interactive · Add one machine, count the moves Machines before adding one3 10,000 keys named user-0 to user-9999, scrambled with a 32-bit FNV-1a hash plus a finishing mix; the circle uses 100 points per machine. Both columns use the same keys. Without JavaScript: going from 3 machines to 4, remainder hashing moves 75% of the keys and consistent hashing about 26%. From 9 to 10: about 90% against 10.5%. MapReduce: move the program to the data Once data is spread across machines, how do you compute over it? In 2004 Jeffrey Dean and Sanjay Ghemawat of Google published MapReduce, a programming model that hid the hard parts. You write two small functions. Map looks at one record and emits key-value pairs. The system then shuffles: it groups all pairs with the same key onto one machine. Reduce combines the values for each key. The framework handles splitting, retrying failed tasks and moving data. Doug Cutting and Mike Cafarella built the open-source Hadoop from the idea around 2006, with Yahoo as an early backer. Counting words is the standard example. Each mapper emits ("the", 1) for every "the" it sees. The shuffle sends all the "the" pairs to the same reducer. The reducer adds them. Nothing in your two functions mentions machines, so the same code runs on 3 lines or 3 billion. Its weakness is that results between stages were typically written to disk; Apache Spark (Zaharia and colleagues, NSDI 2012) kept working data in memory and became the more common choice for multi-step jobs. The shuffle is the expensive step, because it moves data across the network. A combiner adds up counts inside each mapper first, so fewer pairs travel. Interactive · Word count, step by step Mappers2 Reducers2 Combiner: off1 · Map2 · Shuffle3 · Reduce Six invented lines are dealt to the mappers in turn. Words are sent to a reducer by hashing. Every count shown is computed by the page. Without JavaScript: six short lines of text contain 34 words. Without a combiner, all 34 pairs cross the network in the shuffle; with a combiner on 2 mappers, 18 do. Replication and quorums: surviving broken machines With that failure rate, you cannot keep a single copy of anything. The standard answer is replication: keep N copies on different machines (three is a common default in Hadoop's file system). Lose one and two remain. The new problem is that copies can disagree. A write reaches some replicas first; a read that lands on a stale one returns old data. Amazon's Dynamo paper made the trade-off explicit with three numbers. N is the number of replicas, W the number that must confirm a write, R the number asked on a read. If R + W is greater than N, any set of R replicas must overlap any set of W replicas, so a read always meets at least one up-to-date copy. If not, a read can miss the latest write. Bigger W and R mean stronger guarantees and slower, less available operations, because you are waiting on more machines. This is the practical content of the CAP theorem (Eric Brewer's 2000 conjecture, proved by Seth Gilbert and Nancy Lynch in 2002): when the network splits, you choose between answering and being sure the answer is current. Martin Kleppmann has argued that the usual "pick two of three" summary is misleading, since partitions are not optional. Interactive · Will a read see the latest write? Replicas N3 Write waits for W1 Read asks R1 Model: a write lands on W random replicas and the rest lag; a read asks R random replicas and sees the latest write if any of them has it. Exact value from counting, plus a 20,000-trial simulation. Without JavaScript: with N = 3, W = 1 and R = 1, a read is stale two times in three (66.7%). With W = 2 and R = 2, R + W = 4 is greater than 3 and reads are never stale. With N = 5, W = 2, R = 2 the stale chance is 30%. Columns, not rows: reading only what you need Analytical questions usually touch a few columns of a wide table: total sales by country uses two of the twenty columns. Storing a table row by row, as most transactional databases do, forces you to read every column just to reach the two you want. Columnar formats store each column together. Queries read only the columns they need, and a column of similar values compresses far better than a row of mixed ones. The idea was used in research systems in the 2000s and spread through Google's Dremel paper (2010) and open formats such as Apache Parquet (2013). Interactive · How much do you read? Columns the query uses (of 20)2 Compression ratio in columnar form4× Assumes 20 columns of 8 bytes each and a scan speed of 1 GB per second across the cluster (illustrative). Real compression ratios depend on the data. Without JavaScript: for 1 billion rows of 20 columns at 8 bytes each (160 GB), a row layout reads all 160 GB, about 160 seconds at 1 GB/s. A query that needs 2 columns reads 16 GB in a column layout, 4 GB if the columns compress 4 times. Time is hard: event time, processing time and late data Many pipelines process streams: clicks, sensor readings, payments. Computing "events per minute" sounds trivial until you ask whose minute. Event time is when the thing actually happened, stamped on the phone or the sensor. Processing time is when your system saw it. Between the two sit slow mobile networks, retries and a phone in a tunnel, so events arrive late and out of order. Count by arrival and a burst of delayed events lands in the wrong minute. The remedy, popularised by Google's Dataflow model (Akidau and colleagues, 2015) and open-source engines such as Apache Flink and Beam, is to window by event time and track a watermark: the system's estimate of "I have probably seen everything up to time T". Wait longer after a window ends and you drop fewer late events but answer later. There is no free setting. Logs such as Apache Kafka, created at LinkedIn and open-sourced in 2011, store the events in order so a failed job can replay them. Replaying only works safely if each step is idempotent: running it twice gives the same result as once, the last interactive below. Interactive · Count by when it happened, or when it arrived Slowest arrival delay (seconds)20 How long to wait for late events (seconds)0 true (event time)   by arrival   event time, late ones dropped 40 invented events in the first minute, each delayed by a random amount up to the slider. Windows are 10 seconds. Windows beyond 60 seconds only receive late arrivals. Without JavaScript: with delays up to 20 seconds, counting by arrival puts only 1 event in the first 10-second window where 7 really happened. Waiting 10 seconds after each window closes drops 9 of the 40 events as too late; waiting 20 drops none. Pipelines that can be re-run: idempotence Distributed jobs fail halfway, and the system's response is to run them again. That is only safe if running a step twice has the same effect as once. A job that appends its five rows to a table will, after a crash at row 3 and a retry, leave eight. A job that replaces the whole day's partition, or inserts each row by its unique key and updates it if it exists, leaves five whichever way it fails. Real systems add other tools (transactions, atomic file renames, deduplication keys), and vendors often advertise "exactly-once" delivery, which in practice means at-least-once delivery plus idempotent writes. Try it. Interactive · Load five rows, then crash and retry Run the jobCrash after 3 rows, then retryReset table Without JavaScript: "append" leaves 8 rows after a crash and retry; "replace the day" and "upsert by key" leave 5. What a graduate just sees Spreading data over N machines divides the time by N and multiplies the failures by N; scale is that trade. Before reaching for a cluster, ask whether one machine would do, and compare against that baseline. How you split data decides what is cheap: hash partitions spread load, but adding a machine moves everything unless the scheme is consistent. MapReduce's lesson is to move the code to the data and make the shuffle the only expensive step. Replicas buy survival; quorums (R + W > N) buy freshness; each costs speed or availability. Store the columns you read together, together. There is no global clock: event time and processing time differ, and a watermark is a bet about lateness. Make every step safe to run twice, because it will be. Where it shows up next Deep Learning (36/35): training a large model means streaming terabytes of data to thousands of chips, and keeping the run alive when one fails. Data Ethics, Privacy & Fairness (36/37): data copied to many machines and years of logs make deletion requests, retention limits and breach handling hard problems of design. Databases (34/28) and Operating Systems (34/26): the single-machine ideas (transactions, logs, scheduling) reappear here across a network. In the world: search and recommendations, fraud detection, genomics pipelines, ride and delivery apps, telescope surveys and every company that wants one correct dashboard. If you want to go deeper 📘 Textbook. Martin Kleppmann (with Chris Riccomini in the second edition, O'Reilly, 2026), Designing Data-Intensive Applications, the book most data engineers recommend; and Jure Leskovec, Anand Rajaraman and Jeffrey Ullman, Mining of Massive Datasets (Cambridge University Press), free to read at mmds.org, which is the usual text for MapReduce-style algorithms. 📘 Practice. Joe Reis and Matt Housley, Fundamentals of Data Engineering (O'Reilly, 2022), a survey of the whole data-engineering lifecycle. 📘 Gentler. The original papers are readable: Dean and Ghemawat, "MapReduce: Simplified Data Processing on Large Clusters" (OSDI 2004), and DeCandia and colleagues, "Dynamo: Amazon's Highly Available Key-value Store" (SOSP 2007). 🌐 Free course. MIT 6.5840 Distributed Systems (formerly 6.824), with lecture notes, readings and labs on its course site; a hands-on option is the free Data Engineering Zoomcamp from DataTalks.Club. The takeaway Scale buys speed by splitting data across machines, and charges for it in failures, copies, network traffic and confusion about time. The craft is knowing the standard answers: partition so that work divides, replicate so that failure is survivable, aggregate near the data, window by the time that matters, and make every step safe to repeat. Try this: next time an app shows a count or a "last updated" time that seems slightly off, guess which of the ideas above is behind it: a lagging replica, a late event, or a retried job. Then check whether the number corrects itself later. Sources & Further Reading Sources. Backblaze, "Drive Stats for 2024" (annualised failure rate 1.57%; 298,954 drives meeting the inclusion criteria); McSherry, Isard and Murray, "Scalability! But at what COST?", HotOS 2015; Karger et al., "Consistent hashing and random trees," STOC 1997; Ghemawat, Gobioff and Leung, "The Google File System," SOSP 2003; Dean and Ghemawat, "MapReduce," OSDI 2004 (and Communications of the ACM 2008); Zaharia et al., "Resilient distributed datasets," NSDI 2012; DeCandia et al., "Dynamo," SOSP 2007; Brewer, PODC 2000 keynote; Gilbert and Lynch, ACM SIGACT News 2002; Kleppmann, "A critique of the CAP theorem," 2015; Melnik et al., "Dremel," VLDB 2010; Akidau et al., "The Dataflow Model," VLDB 2015; Apache Hadoop, Parquet and Kafka project histories. Disk speeds are round illustrative figures. All simulation outputs and counts were computed in node. 📘 Kleppmann and Riccomini, Designing Data-Intensive Applications (2nd ed.) 📘 Leskovec, Rajaraman and Ullman, Mining of Massive Datasets 🌐 MIT 6.5840 Distributed Systems Step 15. Data Ethics, Privacy & Fairness: Who a Model Can Harm -------------------------------------------------------------- Why: Privacy, bias and who a model can harm. Every dataset about people is a record of someone. This subject is the habit of asking who can be found in it, who gets sorted by it, and what happens when the sorting is wrong. In 1997 the Massachusetts group that insured state employees released hospital records with the names removed, so researchers could use them. A graduate student, Latanya Sweeney, bought the city's voter list for a few dollars. It held names, ZIP codes, birth dates and sexes. Only one voter in the governor's town matched the governor's birth date, and the record that matched him in the hospital file was his. Nothing in the hospital data said "Weld". It did not need to. The same kind of story keeps repeating. A hospital program picks patients for extra care with a score that is quietly worse for one group. A benefits agency flags thousands of parents as fraudsters, and a government falls. The data was real, the maths was correct, and people were hurt anyway. Data ethics is what a data scientist learns to see before the harm: privacy that dissolves when datasets meet, fairness that has more than one meaning, and decisions that nobody can appeal. This piece describes how privacy law and data ethics work. It is not legal advice; laws differ by country, change often, and a real question belongs with a qualified lawyer or your local data-protection authority. The course in one box Who takes itData science and computer science students, usually in the final year, often as a required "responsible data science" module; also information-science, public-policy and law students. The ACM Data Science Task Force guidelines (2021) list ethics and privacy among the competencies every programme should teach, and many universities now teach it alongside or inside the machine learning course. What it is forSeeing how data about people can identify, mislead or harm them, and knowing the tools, laws and habits that reduce the harm. Comes afterMachine Learning (34/32), which builds the models this subject asks about, and Probability & Statistics (34/05). Leads toIt closes the Data Science major. It connects back to Experiments & Causal Inference (36/34), Deep Learning (36/35), Ethics (36/02) and Legal Systems of the World (35/01), and forward to Computational Linguistics (36/30) for bias in language models. What this piece gives youYou will not be able to write a privacy policy or certify a model as fair. You will see why "anonymous" is a claim to be tested, how noise protects a person, why a fair-sounding score can still sort groups unequally, and why two reasonable fairness rules can contradict each other. Easier first read: How Large Language Models Actually Work (29/02). Re-identification: "anonymous" is a claim, not a fact Removing names does not make data anonymous. What identifies you is the combination of ordinary details that others also know: where you live, when you were born, your sex. Each detail is shared by many people; the set may be shared by one. Sweeney later estimated that 87% of people in the United States were unique on just ZIP code, birth date and sex (2000, using 1990 census figures). A later re-analysis with 2000 census data (Golle, 2006) put it nearer 63%. Either way, three dull fields single out most people. The lesson came back in 2008, when Arvind Narayanan and Vitaly Shmatikov showed that a handful of movie ratings and rough dates could pick one subscriber out of the Netflix Prize data. k-anonymity: every combination of identifying fields is shared by at least k people"Quasi-identifiers" are the fields an outsider could know. Larger k hides you in a bigger crowd. Below, 24 invented patients. Blur the fields and watch the smallest crowd grow, and notice what you lose: a researcher who wants age-specific rates can no longer have them. Interactive · Hide in the crowd ZIP digits kept Birth-year band Sex shown 24 invented people and invented five-digit codes. Each square is a person; a red square is unique, and so identifiable by anyone who knows those fields. "Same condition" counts crowds in which everyone has the same diagnosis, which leaks it even when k is large. Without JavaScript: with full ZIP, exact birth year and sex, all 24 people are unique. With the first three ZIP digits, a 20-year band and no sex field, the smallest crowd has 3 people. k-anonymity has a known gap. If everyone in a crowd shares the same diagnosis, the crowd protects nothing: an attacker who knows you are in it learns your condition anyway. The deeper problem: the safety of a release depends on what else exists in the world, which you cannot see. Laws reflect this. The EU's GDPR treats data as personal if a person can be identified using "all the means reasonably likely to be used" (Recital 26), and it treats pseudonymised data, where names are swapped for codes, as still personal. Differential privacy: a budget for how much one person shows Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith (2006) turned the question around. Instead of asking whether a table is anonymous, ask whether an answer would have been noticeably different if one person's data had been left out. If not, nobody can tell whether you were in the data, so nothing about you can be learned from the answer that could not be learned without you. To get there, add random noise to the answer. For a counting query (how many patients have asthma?), one person changes the true count by at most 1. Adding noise from a Laplace distribution with scale 1/ε makes the two answers, with you and without you, almost indistinguishable. The number ε (epsilon) is the privacy budget: small ε means more noise and more privacy. answer = true count + Laplace noise of scale 1/εwith or without any one person, the probability of any answer changes by a factor of at most eε Interactive · Pay for privacy with accuracy Privacy budget ε Ask again Invented clinic: the true count of asthma patients is 412 out of 1,000. The curves are exact Laplace densities, with and without one more person; the dots are random draws, so they change each time you ask. Without JavaScript: at ε = 1 the noise has a typical size of about 1.4 and 95% of answers fall within about 3 of the truth; at ε = 0.1 about 95% fall within 30. The cost is real and it is the whole point: a count of 412 plus or minus 3 is fine for a statistician, but the same method on a count of 12 plus or minus 30 is useless. Differential privacy works best on big groups and badly on small ones, which is exactly where individuals are most exposed. Every extra question spends budget, so a data holder must decide in advance how much total ε to give away. The US Census Bureau used differential privacy for its 2020 Census releases, and users argued over whether the noise damaged small-area counts. Apple (2016) and Google (RAPPOR, 2014) used a local version, in which noise is added on your own device. The oldest local idea is Stanley Warner's randomised response (1965). Ask a sensitive yes/no question and let each person flip a coin first: heads, answer truthfully; tails, flip again and answer yes on heads, no on tails. Any single answer is deniable. Yet if 40% of the answers are yes, the true share is 2 × 0.40 − 0.5 = 30%. A "yes" is at most three times as likely from someone whose truth is yes as from someone whose truth is no, which is ε = ln 3, about 1.1. Privacy law: the regimes, described Most countries now have a data-protection law. They share ideas (use data only for stated purposes, keep no more than you need, let people see and correct their records, secure it) but differ in scope, legal basis and enforcement. The explorer is a summary for understanding, not a guide to compliance. Interactive · Seven regimes side by side Choose a law Summaries, not advice. Details, thresholds and dates change; check the text of the law and the regulator's guidance. Fine figures are the headline maximums written into each law. Without JavaScript: the EU's GDPR (applied from 25 May 2018) allows fines up to €20 million or 4% of worldwide annual turnover, whichever is higher. Brazil's LGPD (in force September 2020), China's PIPL (November 2021) and India's DPDP Act (2023, phased in from November 2025) are comparable in spirit. Three differences are worth keeping. First, the basis: the GDPR lists six lawful bases (Article 6), of which consent is only one, so a company may process data without consent if, for example, it is necessary for a contract. California's law works by giving residents rights (to know, delete, opt out of sale or sharing) rather than requiring a basis for every use. Second, automated decisions: GDPR Article 22 gives people a right not to be subject to a decision based solely on automated processing that has legal or similarly significant effects, with exceptions; how far that amounts to a "right to explanation" is argued by lawyers. Third, scope: the US has no single general federal privacy law, so it relies on sector laws (health, children's data, credit) and a patchwork of state laws. The EU's AI Act (Regulation 2024/1689, in force 1 August 2024, with duties phasing in from 2025) adds rules by risk level for AI systems, including limits on some uses and extra duties for "high-risk" ones. Where bias gets in: the label is not the thing Bias is usually in the setup, not the maths. A model predicts a label, and the label is rarely the thing we care about. We care about illness and measure cost; about danger and measure arrests; about job performance and measure past hiring. In 2019 Ziad Obermeyer and colleagues studied a widely used US health-care algorithm that ranked patients for extra care. It predicted future health-care cost. But less is spent on Black patients than on white patients with the same illnesses, for reasons of access and trust. So, at the same risk score, Black patients were measurably sicker. The authors estimated that removing the disparity would raise the share of Black patients flagged for extra help from 17.7% to 46.5%. The algorithm was never told anyone's race. It did not need to be. Interactive · Cost is a proxy for need Group B's spending gap at equal need Invented illustration: 100 people in each group, with needs spread evenly from 1 to 100 in both. A program picks the 40 people (the top 20%) with the highest predicted cost. Group B's cost is lower by the gap at the same need. Without JavaScript: with no gap, 20 of the 40 people chosen are in group B. At a 20% gap, 11 are; at a 40% gap, none are, although half of the 40 people with the greatest need are. The same pattern, in other forms: face-analysis systems trained mostly on lighter faces do worse on darker ones (Joy Buolamwini and Timnit Gebru's Gender Shades, 2018, found error rates up to 34.7% for darker-skinned women against 0.8% for lighter-skinned men in three commercial gender classifiers); résumé screens learn from who was hired before. When data records past human decisions, the model inherits the decisions. Hence the habit graduates keep: ask what the label really measures, and who is missing or mismeasured in it. Feedback loops: the model changes the data that trains it A model that is used also reshapes the world it measures. Predictive policing is the textbook case. Send more patrols to the area with more recorded incidents, and you record more incidents there, because you are looking there. Kristian Lum and William Isaac (2016) showed with simulation how a system trained on police records could keep directing patrols to the same neighbourhoods; Danielle Ensign and colleagues (2018) proved that under some assumptions such a loop runs away. The toy makes that visible. Two districts have the same true crime rate and a small head start in records (55 to 45). Each round, patrols are shared in proportion to records raised to a power γ, and records grow with patrols. At γ = 1 the split stays put. Above 1, a "hotspot" policy, the head start is amplified. Interactive · A head start that never ends Hotspot focus γ Rounds of patrol A stylised model after Ensign et al. (2018), computed in expected values. Real systems are messier, and many departments have changed or stopped using such tools. The point is the mechanism, not a forecast. Without JavaScript: starting from 55 to 45, after 200 rounds district A holds 50% of the records at γ = 0, 55% at γ = 1, 89% at γ = 2 and 96% at γ = 3, though the true rates are equal. Fairness has several meanings, and they collide "Make the model fair" sounds like one instruction. It is several, and a landmark result says you cannot always follow all of them. In 2016 ProPublica analysed the COMPAS recidivism score used in US courts and reported that among defendants who did not go on to be re-arrested, 44.9% of Black defendants had been labelled higher risk against 23.5% of white defendants. The maker, Northpointe, answered that the score was equally accurate for both groups: a given score meant about the same chance of re-arrest whatever the defendant's race. Both statements were true. They were different definitions of fair. Equal error rates (equalised odds): among people who truly would reoffend, or truly would not, the chance of being flagged is the same in each group. Calibration (predictive parity): a score of 70% means a 70% chance of the outcome, in every group. Equal selection rates (demographic parity): the same share of each group is flagged. Jon Kleinberg, Sendhil Mullainathan and Manish Raghavan (2016) and Alexandra Chouldechova (2017) showed that if two groups have different base rates, a score cannot satisfy calibration and equal error rates at once, except in the useless cases of perfect prediction or equal base rates. Chouldechova's identity makes it concrete: false-positive rate = base-rate odds × (1 − PPV) / PPV × true-positive rate, where PPV is the share of flagged people who truly have the outcome. If base rates differ and PPV and TPR are held equal, the false-positive rates must differ. Interactive · Try to satisfy everyone Same cut-off for both groupsSeparate cut-offs Cut-off for group A (flag at or above) Cut-off for group B Group AGroup B Invented scores for 1,000 people in each group, in ten score bins. In every bin the share who truly have the outcome equals the bin's score, so the score is perfectly calibrated for both groups. Group B has the higher base rate (57% against 43%). Without JavaScript: with one cut-off at 0.6, flagged-but-innocent rates are 11.4% in group A and 23.6% in group B, while PPV is 78.3% and 79.3%. Setting A to 0.5 and B to 0.6 brings true-positive rates to 67.4% and 68.2%, but PPV becomes 72.5% against 79.3%. This is a mathematical fact, not an engineering failure. It forces a choice about values: which mistake matters most, whom it falls on, and who decides. The field names no single right metric. A graduate insists that the choice is made in the open, and that the base-rate gap itself is examined: it often reflects unequal policing, access or history, which no threshold can fix. Accountability: consent, documentation and appeal Modern research ethics begins with harm done in the name of science. In the Tuskegee study (1932 to 1972) US Public Health Service researchers followed Black men with syphilis and withheld treatment after penicillin became standard, without informed consent. The Belmont Report (1979) answered with three principles that data ethics still borrows: respect for persons (consent and autonomy), beneficence (do no harm, maximise benefit) and justice (fair distribution of burdens and benefits). The Menlo Report (2012) adapted them for computing research. Practical habits followed. Datasheets for Datasets (Gebru and colleagues, 2018) and Model Cards (Mitchell and colleagues, 2019) ask builders to write down what data a model was trained on, what it should not be used for and how it performs for different groups. The GDPR requires a data protection impact assessment (Article 35) before high-risk processing. And the Dutch childcare benefits affair shows what happens without appeal. Between 2005 and 2019 the Dutch tax authority wrongly accused roughly 26,000 parents of benefit fraud and demanded repayment of often tens of thousands of euros. The data protection authority later found its use of nationality unlawful and discriminatory, and the cabinet resigned on 15 January 2021. The failure was a system in which suspicion was automatic and correction nearly impossible. Data ethics asks the practical version of the questions in Ethics (36/02): who is in this data, did they know, who is affected by the decision, and how can they challenge it? What a graduate just sees Removing names is not anonymising; a few ordinary fields together can single a person out. Privacy can be measured: a differential-privacy budget trades accuracy for protection, and it is cheap for big groups and costly for small ones. Data-protection laws share a core (purpose, minimisation, access, security) but differ in basis, scope and enforcement, and they change. A model learns its label, not the truth the label stands for; cost is not need, arrests are not crime. Models used in the world change the data they will be trained on, and small head starts can compound. Fairness has several definitions; with different base rates they cannot all hold, so choosing one is a decision about values. The people affected need a way to know, to ask and to appeal; documentation and audits make that possible. Where it shows up next Machine Learning (34/32) and Deep Learning (36/35): evaluating a model by group, not just overall accuracy, is now a standard step. Experiments & Causal Inference (36/34): asking whether a disparity is caused by the model or by the world it learned from needs causal tools. Computational Linguistics (36/30): language models absorb the associations in their training text. Legal Systems of the World (35/01) and Ethics (36/02): the same questions in the language of rights and duties. In the world: hospital risk scores, credit and hiring tools, the Census, the apps on your phone, and the compliance and audit jobs that now exist at every large organisation. If you want to go deeper 📘 Textbook. Solon Barocas, Moritz Hardt and Arvind Narayanan, Fairness and Machine Learning: Limitations and Opportunities (MIT Press, 2023; free at fairmlbook.org), the standard graduate text on the criteria above. For privacy, Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy (2014), free from the authors. 📘 Gentler. Cathy O'Neil, Weapons of Math Destruction (2016), and Michael Kearns and Aaron Roth, The Ethical Algorithm (2019), which explains differential privacy and fairness trade-offs for general readers. 🌐 Free text. The full text of the GDPR at eur-lex.europa.eu and the Belmont Report at hhs.gov. The recitals are readable. 🌐 Free course. MIT OpenCourseWare RES.EC-001, Exploring Fairness in Machine Learning for International Development (Spring 2020). The takeaway Data about people is not neutral raw material. Combining it can identify them, labelling it can mismeasure them, and deploying a model can reshape the world it learned from. There are tools (noise, documentation, audits) and laws, and none of them removes the need to decide whose mistakes count most. Try this: choose an app you use and find its privacy settings. Write down three kinds of data it holds about you and one way a stranger who combined them with a public list could pick you out. Then ask who gets to see the scores it computes about you. Sources & Further Reading Sources. Sweeney, "Simple demographics often identify people uniquely," Carnegie Mellon Data Privacy Working Paper 3 (2000); Golle, "Revisiting the uniqueness of simple demographics in the US population," WPES 2006; Narayanan and Shmatikov, "Robust de-anonymization of large sparse datasets," IEEE Symposium on Security and Privacy 2008; Dwork, McSherry, Nissim and Smith, "Calibrating noise to sensitivity in private data analysis," TCC 2006; Warner, "Randomized response," Journal of the American Statistical Association 1965; Obermeyer, Powers, Vogeli and Mullainathan, "Dissecting racial bias in an algorithm used to manage the health of populations," Science 366 (2019); Buolamwini and Gebru, "Gender Shades," PMLR 81 (2018); Angwin, Larson, Mattu and Kirchner, "Machine Bias," ProPublica, 23 May 2016; Kleinberg, Mullainathan and Raghavan, "Inherent trade-offs in the fair determination of risk scores" (2016); Chouldechova, "Fair prediction with disparate impact," Big Data 2017; Lum and Isaac, "To predict and serve?" Significance 2016; Ensign et al., "Runaway feedback loops in predictive policing," PMLR 81 (2018); Gebru et al., "Datasheets for datasets" (2018); Mitchell et al., "Model cards for model reporting" (2019); Regulation (EU) 2016/679 (GDPR), Recital 26, Articles 5, 6, 22, 35 and 83; Regulation (EU) 2024/1689; The Belmont Report (1979); Dutch parliamentary and data protection authority reports on the childcare benefits affair. All outputs of the interactives were computed in node. Datasets in the interactives are invented. This piece describes law and research; it is not legal advice. 📘 Barocas, Hardt and Narayanan, Fairness and Machine Learning 📘 Kearns and Roth, The Ethical Algorithm 🌐 The GDPR, full text Step 16. Algorithms: Why Growth Beats Speed ------------------------------------------- Why: Algorithms and their cost, when the data is huge. 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)