A First Taste of Algorithms · Building the Learner

The sweep that prices everything

The operations record history as the computation runs forward. One sweep then prices every knob backward — and the sweep is built entirely from earlier chapters. Watch the curriculum reassemble:

The recorded history is a graph — Chapter 5 — with each Value a vertex and an edge to each parent. To pass blame correctly, you must process each node only after everything that depends on it, which means visiting the graph in reverse of a careful ordering: a depth-first traversal — Chapter 5’s thread, which was Chapter 3’s recursion — laying the nodes in dependency order, then walked backward.

    def backward(self):
        order = []
        visited = set()
        def build(v):                  # depth-first, Chapter 5 exactly
            if v not in visited:
                visited.add(v)
                for parent in v._parents:
                    build(parent)
                order.append(v)
        build(self)

        self.grad = 1.0                # the loss blames itself fully
        for v in reversed(order):      # walk backward; each node blames its parents
            v._backward()

That is backpropagation, complete. Seed the final output with blame 1.0 (the loss is fully responsible for itself), then walk the recorded graph backward; at each node, fire the little blame-rule that operation tucked away, and watch blame flow from the single loss number out to every knob that touched it. One forward computation records the graph; one backward walk prices the entire graph. The billion-knob bill from Chapter 8 is paid in a single sweep — and the sweep is just DFS over a graph of remembered operations, every piece of it built in a chapter you have already done.

There is even a ghost of Chapter 4 here, if you look: when one Value feeds several later operations, blame arrives from each, and the += in every rule accumulates it — the multivariable chain rule, which says a knob’s total influence is the sum of its influences along every path it affects. Summing a quantity over all the paths that contribute to it: that is linearity, Chapter 7’s workhorse, doing the bookkeeping one final time.

A human moment

Backpropagation was discovered, forgotten, and rediscovered for two decades before the world noticed. The core idea — reverse-mode differentiation — appears in a Finnish master’s thesis by Seppo Linnainmaa in 1970, with no mention of neural networks; it surfaces in Paul Werbos’s 1974 Harvard PhD thesis as a way to train them, and is largely ignored. Only in 1986, when David Rumelhart, Geoffrey Hinton, and Ronald Williams published it with compelling experiments, did the field finally absorb that this one algorithm made training deep networks practical — and even then, a long winter followed before the data and the machines caught up to the idea. Hinton would share the 2018 Turing Award and, in 2024, a Nobel Prize in Physics. The pattern is Chapter 5’s Dijkstra and Chapter 2’s Borůvka once more, sharpened to a point: the algorithm that now consumes a measurable fraction of the world’s electricity sat in plain sight, in published theses, for sixteen years, because the idea was ready before the world that needed it. You are building, in an afternoon, the thing three fields walked past for a generation.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses