Flip, slide, multiply, add: discrete convolution algorithm

This card formalizes the mechanical procedure used repeatedly in the lecture: reverse one list, slide it across the other, multiply all overlapping pairs, then sum those products to produce one output value [1]. Repeating the shift builds the full output sequence. The canonical toy computation

$$(1,2,3)\ast(4,5,6) = (4,13,28,27,18)$$

is not just a classroom exercise; it is the smallest example where you can see start-up overlap, full overlap, and wind-down overlap in one pass.

There are two equivalent formula styles in the lecture, and both are worth fluency:

$$(a \ast b)_n = \sum_i a_i b_{n-i}\quad\text{and}\quad(a \ast b)_n = \sum_{i+j=n} a_i b_j.$$

The first is convenient for implementation with one loop variable; the second is ideal for geometric reasoning on diagonals. Switching between them is often the difference between understanding and rote symbol pushing.

An important engineering edge case appears here and later in the video: pure mathematical convolution of lengths $m$ and $n$ has length $m+n-1$, but many libraries expose truncated modes. full keeps every overlap, same keeps output length tied to one input, and valid keeps only complete overlaps. When debugging, most off-by-one mistakes come from mixing these conventions.