Everything on the site.

Big-O notationAlgorithms · Count the steps in real loops, then compare n, n log n, n² and 2ⁿ on a live chart.RecursionAlgorithms · Watch frames push and pop on the call stack for factorial and Fibonacci.BFS vs DFSAlgorithms · A queue against a stack: draw a graph and see which order each search visits it in.Sorting algorithmsAlgorithms · Seven sorts on the same input, with comparison, swap and write counts side by side.Binary searchAlgorithms · Halve the range, probe the middle, repeat: with lo, mid and hi drawn on the array.Sets, relations and functionsDiscrete maths · Shade any set expression on a Venn diagram and test a relation for its properties.Proof by inductionDiscrete maths · Four worked proofs revealed one step at a time, and a broken one to diagnose.CombinatoricsDiscrete maths · An exact nPr and nCr calculator, and a Pascal’s triangle that shows its own addition rule.Boolean algebraDiscrete maths · The laws, De Morgan, and normal forms, with a truth-table generator built in.Finite-state machinesTheory · Build a DFA in a table, see it drawn, and run strings through it one symbol at a time.Domain theoryTheory · Why recursion needs least fixed points, and how CPOs, Scott continuity and powerdomains supply them.Truth table generatorTools · Expression in, truth table out: with DNF, CNF, a minimal form and LaTeX.Graph traversal visualiserTools · Draw a graph, then animate BFS, DFS and Dijkstra with the frontier shown.Recursion tree visualiserTools · Paste a recursive function or a recurrence and see its call tree and call count.Gradient descentML maths · Drag the starting point, set the learning rate, and watch it converge or blow up.Vectors and embeddingsML maths · Bend the plane with a 2×2 matrix and measure how close toy word vectors are.Softmax and cross-entropyML maths · Edit the logits and watch the probabilities, the loss and the gradient update live.Attention mechanismML maths · Q, K and V for three tokens, a live score heatmap, and the weighted sum of values.Image to video attentionML maths · One photo, 16 frames: switch reference attention on or off and watch the colours hold or drift.Formatting a CS paper in LaTeXLaTeX · Page limits, \documentclass, front matter, theorem environments and the bibliography.Camera-ready checklistLaTeX · Fonts embedded, PDF/A, copyright form, source bundle, and why final versions get rejected.LaTeX templatesLaTeX · Where the official classes live, plus a minimal article template you can copy.Boolean algebra calculatorTools · A Boolean expression simplifier that names the law used at every step.K-map solverTools · Fill in a Karnaugh map and see the groups, the minimal SOP and POS, and the essential terms.Logic gate simulatorTools · Wire up gates, flip the switches, and get the truth table and expression of your circuit.Regex to NFA converterTools · Type a regular expression and watch Thompson’s construction build its NFA, fragment by fragment.NFA to DFA converterTools · Enter an NFA or a regex and step through the subset construction, then minimise the DFA.DFA simulatorTools · Edit a DFA, run strings through it step by step, batch-test them and share the machine as a link.Regular expressions to automataTheory · Regex to NFA to DFA to minimal DFA, worked through on one example with every set shown.The halting problemTheory · Why no program can tell whether every program halts, with the paradox program played out.Pigeonhole principleDiscrete maths · n pigeons, k holes: why some hole gets ⌈n/k⌉, and the surprising things that follows from it.Dijkstra’s algorithmAlgorithms · Shortest paths with a priority queue: a worked table, a proof, and a graph you can redraw.Hash functionsAlgorithms · Keys in, buckets out: hash a word four ways, then watch chaining and probing handle collisions.Sorting algorithm visualizerTools · Up to seven sorts race on the same data, then step through any one of them line by line.LaTeX table generatorTools · Type or paste a table, merge cells, pick booktabs, and copy clean tabular code.Combination calculatorTools · Exact nCr with the cancelling shown, combinations with repetition, and a full list for small n.Permutation calculatorTools · nPr, nʳ, anagrams like MISSISSIPPI and round-table seatings, with exact working.AlgorithmsSection · Step-through visualisations of sorting, searching, recursion, graph traversal, Dijkstra’s algorithm, hash functions and Big-O growth, with pseudocode that follows along.Discrete mathsSection · Sets, relations and functions, proof by induction, counting, the pigeonhole principle and Boolean algebra, explained with worked examples and interactive checkers.TheorySection · Finite-state machines, regular expressions and automata, the halting problem, and the mathematical semantics of programming languages, explained from first principles.ML mathsSection · Gradient descent, vectors and embeddings, softmax, attention and image to video models, each with a formula, a worked numeric example and a live version.ToolsSection · Free browser tools: truth tables, Boolean simplification, K-maps, logic gates, nCr and nPr, regex to NFA to DFA, sorting and graph visualisers, and LaTeX tables.LaTeXSection · How to format a CS conference or workshop paper in LaTeX, a camera-ready checklist, and a minimal template you can adapt.
ML maths

How image to video AI works: animating a photo with attention

An image to video model takes one photo and returns a few seconds of moving footage. The hard part is not the motion but keeping the person or object recognisable while it moves. This page explains how image to video AI works using the same attention maths as our attention mechanism explainer, then works one step by hand and lets you switch the key trick on and off.

Interactive: Toy 3×3 animation with reference attention on or offUpdated
The idea in one sentence The photo becomes frame 0 and is never changed; every new frame is generated with attention that can look back at frame 0’s patches, so details such as a face, a logo or a shirt’s colour are copied from the photo instead of being reinvented each frame.

What has to stay the same, and what has to change

Give a model a portrait and ask for five seconds of the person turning their head. Two things must happen at once. The appearance must stay fixed: the same eyes, the same hair, the same background. The geometry must change: the head turns, the light shifts across the cheek, the background slides a little. A model that gets the motion right but lets the appearance wander produces a clip in which the person slowly becomes someone else.

Text-to-video models only have to be consistent with themselves. An image to video model also has to be consistent with a picture it was given, pixel for pixel, at the very first frame. Attention is the tool that makes that possible. If queries, keys and values are new to you, read the attention mechanism first; everything below reuses its formula.

Frames as grids of patches

Transformers work on sequences of tokens, so a video has to become a sequence. The usual way is to cut each frame into a grid of small square patches and turn each patch into one vector, an embedding that describes its colours and texture. Real models do this on a compressed version of the frame rather than raw pixels, but the idea is the same.

Our toy uses a 3×3 grid, so each frame is 9 tokens. Three frames make 3×9=273 \times 9 = 27 tokens. Number the patches 1 to 9 row by row, so patch 5 is the centre. Frame 0 is the photo; frames 1 and 2 are the ones the model has to produce.

Each token also carries its position: which frame it belongs to and where in the grid it sits. Without that, attention could not tell “the patch above” from “the same patch, one frame later”, because attention by itself ignores order.

The reference frame trick

In ordinary self-attention every token attends to every other token in the sequence. The design this page describes, used in several image to video models, gives frame 0 a special role. When the model builds frame tt, each patch’s query is compared with keys from two places: the patches of frame tt itself and the patches of frame 0. The values come from the same two places:

K=(K0Kt),V=(V0Vt),Zt=softmax⁡ ⁣(QtK⊤d)V.K = \begin{pmatrix} K_0 \\ K_t \end{pmatrix}, \qquad V = \begin{pmatrix} V_0 \\ V_t \end{pmatrix}, \qquad Z_t = \operatorname{softmax}\!\left(\frac{Q_t K^{\top}}{\sqrt{d}}\right) V.

Stacking the rows of K0K_0 on top of KtK_t just makes the score matrix wider: each query now has 18 scores instead of 9, and softmax turns all 18 into weights that sum to 1. Frame 0 itself is never rewritten. Its patches are clean, so they act as a fixed library of “what this subject looks like” that every later frame can copy from.

When a patch in frame 2 is part of the subject’s cheek, its query will match the keys of the cheek patches in frame 0 best, and most of its output will be the photo’s own cheek values. That is why the person in the photo is still the same person five seconds later. Other models reach the same goal differently, for example by feeding the photo in as extra input channels or through cross-attention on an image embedding, and many use more than one of these at once.

How it is trained

The weight matrices that produce the queries, keys and values are learned. During training the model is shown the first frame of a real clip and asked to reconstruct the rest, usually from noisy versions of those frames, and gradient descent adjusts the weights to make the reconstruction closer to the real footage. Over millions of clips, the weights learn to produce keys that match when two patches show the same part of the same thing.

Worked example by hand

Step 1: one query against nine keys

Take one patch of frame 2 with query q=(2,1)q = (2, 1), and the nine keys of frame 0, row by row:

K0:k1=(0,0)k2=(1,0)k3=(0,0)k4=(0,1)k5=(2,1)k6=(0,1)k7=(0,0)k8=(1,0)k9=(0,0)K_0:\quad \begin{array}{ccc} k_1 = (0,0) & k_2 = (1,0) & k_3 = (0,0) \\ k_4 = (0,1) & k_5 = (2,1) & k_6 = (0,1) \\ k_7 = (0,0) & k_8 = (1,0) & k_9 = (0,0) \end{array}

To keep the arithmetic short we leave out frame 2’s own keys; adding them would only add more columns of the same kind.

Step 2: scores

Each score is q⋅kj/2q \cdot k_j / \sqrt 2, since the vectors have length d=2d = 2. The raw dot products are 0, 2, 0, 1, 5, 1, 0, 2, 0. For the centre patch, q⋅k5=2⋅2+1⋅1=5q \cdot k_5 = 2 \cdot 2 + 1 \cdot 1 = 5. Dividing by 2≈1.414\sqrt 2 \approx 1.414 gives

scores=(0.000, 1.414, 0.000, 0.707, 3.536, 0.707, 0.000, 1.414, 0.000).\text{scores} = (0.000,\ 1.414,\ 0.000,\ 0.707,\ 3.536,\ 0.707,\ 0.000,\ 1.414,\ 0.000).

Step 3: softmax

Exponentiate each score: e0=1e^0 = 1, e0.707≈2.03e^{0.707} \approx 2.03, e1.414≈4.11e^{1.414} \approx 4.11 and e3.536≈34.31e^{3.536} \approx 34.31. The nine terms add up to about 50.60. Dividing each by that total gives the weights

A=(0.020, 0.081, 0.020, 0.040, 0.678, 0.040, 0.020, 0.081, 0.020).A = (0.020,\ 0.081,\ 0.020,\ 0.040,\ 0.678,\ 0.040,\ 0.020,\ 0.081,\ 0.020).

The centre patch of the photo takes 0.678 of the attention. Its four neighbours share about 0.243, and the corners about 0.079.

Step 4: the weighted sum of values

Give the frame-0 patches (red, blue) colour values: the centre is red (1,0)(1, 0), the top and bottom middles are purple (1,1)(1, 1), the left and right middles are blue (0,1)(0, 1), and the corners are black (0,0)(0, 0). Then

z=0.678 (1,0)+0.163 (1,1)+0.080 (0,1)+⋯≈(0.841, 0.243).z = 0.678\,(1,0) + 0.163\,(1,1) + 0.080\,(0,1) + \dots \approx (0.841,\ 0.243).

Here 0.163 is the two purple patches together, 0.080 the two blue ones, and the black corners add nothing. The new patch comes out mostly red, the colour of the photo patch it matched, with a little blending from its neighbours. In a trained model, that output is what lets the patch keep the photo’s look while the rest of the network moves it.

Try it: anchor on or off

The widget runs a toy version of the whole loop. Frame 0 is a 3×3 picture of nine colours. In each new frame the outer ring of patches turns one step around the centre, and each patch is copied from the previous frame with a little random noise added, standing in for an imperfect generator. With reference attention on, every patch also attends to frame 0, using its own colour as the query, and is pulled towards the photo patch it matches best. With it off, the patches only ever see the previous frame.

Press Play and watch the strip of frames. With the anchor off, the errors add up and the colours wander further from the photo with every frame. With it on, they stay close for all 16 frames. Click a patch to see its nine attention weights over frame 0; the outlined square is the photo patch it actually started as. Push the noise above about 0.1 and even the anchored version sometimes snaps to the wrong photo patch, such as orange to red: the photo only helps while each frame is close enough to match the right part of it.

Anchor on or off: a 3×3 picture that turns for 16 frames

Frame 0 (the photo, never changed)

Frame 1 (click a patch)

All 16 frames

Which frame-0 patches the selected patch attends to

The toy cheats in one way: its keys are built straight from colours, so a patch matches the photo patch with the nearest colour. A real model learns its keys, so it can match “the same part of the same object” even when the lighting or angle has changed.

Why this costs so much

Attention compares every query with every key, so its cost grows with the square of the number of tokens. That is the O(n2)O(n^2) term from Big-O notation, and video is where it bites. Our toy has 27 tokens, so full attention across all three frames needs 272=72927^2 = 729 scores.

Now take a five-second clip at 720p and 24 frames a second, and make some typical assumptions: the frames are compressed 8 times in each direction and 4 times in time before the model sees them, and cut into 2×2 patches. That still leaves 30 frames of 3,600 patches each, or 108,000 tokens. Full attention over all of them would need about 1.2×10101.2 \times 10^{10} scores, for every attention head in every layer, at every denoising step.

That is why generated clips are short, why models split attention into a spatial part (within a frame) and a temporal part (across frames), and why the reference frame is so useful: attending to the patches of one clean frame is far cheaper than attending to every patch of every frame, yet it carries most of the information about what the subject looks like.

Where you’ll see this

The reference frame buys two things. First, identity holds: a face, a product or a pet keeps its features from start to finish, because every frame keeps copying them from the same source. Second, the motion is free to change: since appearance is anchored, the rest of the network can concentrate on where things move, guided by a text prompt such as “the camera slowly pushes in” or by a separate motion module.

Because every frame looks back at the photo, the person or object in it stays recognisable while it moves. That is the main job of the image to video AI services that let you upload one picture, such as HighReach, and turn it into a short clip.

Limits

  • Hands and fingers. A hand changes shape a lot between frames and often shows parts the photo never did, so there is nothing in frame 0 to copy. Extra or merging fingers are still common.
  • Text in the image. Letters on a sign or a T-shirt span several patches, and small errors in each one turn words into near-words as the clip goes on.
  • Large camera moves. When the camera turns far enough to reveal what was behind the subject, frame 0 has no information about it, and the model has to invent the new area. That is where scenes change most.
  • Long clips. Because of the quadratic cost, long videos are made in chunks, each starting from the last frame of the one before. Small errors can then build up from chunk to chunk, which is the drift you saw with the anchor off.

Further reading

To go deeper, start with the attention mechanism page, then search for these papers by title:

  1. A. Blattmann et al., “Stable Video Diffusion: scaling latent video diffusion models to large datasets”, 2023, arXiv:2311.15127.
  2. S. Zhang et al., “I2VGen-XL: high-quality image-to-video synthesis via cascaded diffusion models”, 2023, arXiv:2311.04145.
  3. A. Arnab, M. Dehghani, G. Heigold, C. Sun, M. Lučić and C. Schmid, “ViViT: a video vision transformer”, ICCV 2021, arXiv:2103.15691.