StudyHub

Prep sheet

90 topics: definition, three key facts, one formula, one pitfall and a Feynman prompt each.

Sorting

Bubble sort

a pass walks the unsorted part, comparing a[j] with a[j+1] and swapping when a[j] > a[j+1].

  • After pass $k$, the $k$ largest values are final, because each pass carries the largest remaining value all the way to the end.
  • The worst case is $O(n^2)$ because there are up to $n-1$ passes, and together they make $\frac{n(n-1)}{2}$ comparisons.
  • The best case is $O(n)$ because, with the flag, a sorted array needs just one pass with no swaps.
$$\sum_{i=1}^{n-1} i \;=\; \frac{n(n-1)}{2} \;=\; O(n^2).$$

Pitfall Forgetting the swapped flag, so sorted input still costs $O(n^2)$.

Feynman Explain Bubble sort to a beginner in 2 minutes: define it, give one example, name one limitation.

Insertion sort

insertion sort keeps a sorted prefix a[0..i-1] and inserts a[i] into it by shifting bigger elements one slot right.

  • The prefix is always sorted, because each key is dropped exactly where it fits among the numbers already there.
  • The worst case is $O(n^2)$ because on reversed input key $i$ shifts past all $i$ numbers before it, $\frac{n(n-1)}{2}$ in total.
  • The best case is $O(n)$ because on sorted input every key stops after one comparison.
$$1 + 2 + \dots + (n-1) \;=\; \frac{n(n-1)}{2} \;=\; O(n^2).$$

Pitfall Shifting before saving a[i] into key, which overwrites the number you are inserting.

Feynman Explain Insertion sort to a beginner in 2 minutes: define it, give one example, name one limitation.

Selection sort

selection sort repeatedly selects the minimum of the unsorted part a[i..n-1] and swaps it into position i.

  • After pass $k$, the first $k$ slots are final, because each pass puts the smallest remaining value there.
  • It is always $\Theta(n^2)$ because each pass must scan the whole unsorted part to be sure it found the minimum.
  • It makes at most $n-1$ swaps because it swaps once per pass, after the scan.
$$\sum_{i=1}^{n-1} i \;=\; \frac{n(n-1)}{2} \;=\; \Theta(n^2).$$

Pitfall Swapping inside the inner loop every time a smaller value appears, which turns one swap per pass into many.

Feynman Explain Selection sort to a beginner in 2 minutes: define it, give one example, name one limitation.

Merge sort

merge sort splits the array into halves, sorts each half recursively, and merges the two sorted halves in linear time.

  • The merge works because both halves are sorted, so the smaller front is always the smallest number left.
  • It is $O(n \log n)$ in every case because there are $\log_2 n$ levels and each moves all $n$ numbers.
  • It needs $O(n)$ extra space because the merge writes into a scratch array.
$$\underbrace{n}_{\text{work per level}} \times \underbrace{\log_2 n}_{\text{levels}} \;=\; O(n \log n).$$

Pitfall Forgetting to copy the leftovers after one half runs out, which silently loses numbers.

Feynman Explain Merge sort to a beginner in 2 minutes: define it, give one example, name one limitation.

Quick sort

quick sort picks a pivot, partitions the array so the pivot lands in its final place with smaller-or-equal elements on its left, then sorts both sides recursively.

  • After a partition the pivot is final, because everything left of it is ≤ it and everything right of it is bigger.
  • The average case is $O(n \log n)$ because reasonably balanced splits give about $\log_2 n$ levels of $n$ work.
  • The worst case is $O(n^2)$ because a pivot that is always the min or max shrinks the problem by only one.
$$(n-1) + (n-2) + \dots + 1 \;=\; \frac{n(n-1)}{2} \;=\; O(n^2).$$

Pitfall Forgetting the final swap that puts the pivot after the left zone.

Feynman Explain Quick sort to a beginner in 2 minutes: define it, give one example, name one limitation.

Heap sort

heap sort turns the array into a max-heap (every parent ≥ its children), then repeatedly swaps the root to the end of the shrinking heap and sifts the new root down.

  • The root is always the maximum because every parent is at least as big as its children.
  • Building the heap is $O(n)$ because most nodes are near the bottom and sink only a level or two.
  • The sort is $O(n \log n)$ in every case because each of the $n-1$ extractions sinks at most $\log_2 n$ levels.
$$\underbrace{O(n)}_{\text{build}} + \underbrace{(n-1) \cdot O(\log n)}_{\text{extractions}} \;=\; O(n \log n).$$

Pitfall Sifting down with the full size n instead of the shrinking heap size, which pulls sorted numbers back into the heap.

Feynman Explain Heap sort to a beginner in 2 minutes: define it, give one example, name one limitation.

Searching

Linear search

linear search compares the target with each element in order and returns the index of the first match, or −1 if there is none.

  • It works on unsorted data because it never assumes anything about elements it hasn't checked.
  • The worst case is $O(n)$ because a missing target can only be ruled out by checking all $n$ elements.
  • The average successful search is $\frac{n+1}{2}$ comparisons because the target is, on average, halfway along.
$$\frac{1}{n}\sum_{i=1}^{n} i \;=\; \frac{n+1}{2} \;=\; O(n).$$

Pitfall Returning −1 inside the loop on the first mismatch, so only a[0] is ever checked.

Feynman Explain Linear search to a beginner in 2 minutes: define it, give one example, name one limitation.

Binary search

binary search finds a target in a sorted array by comparing it with the middle of the current range and discarding the half that cannot contain it.

  • It needs sorted data because only order lets one comparison rule out a whole half.
  • It is $O(\log n)$ because each comparison halves the range, and you can halve $n$ only $\log_2 n$ times.
  • It stops with "not found" when lo > hi because an empty range leaves no place for the target.
$$\frac{n}{2^k} = 1 \;\Longrightarrow\; k = \log_2 n, \qquad \text{at most } \lfloor \log_2 n \rfloor + 1 \text{ comparisons.}$$

Pitfall Running it on unsorted data. It doesn't crash; it silently gives wrong answers.

Feynman Explain Binary search to a beginner in 2 minutes: define it, give one example, name one limitation.

Interpolation search

interpolation search is binary search with the probe placed by linear interpolation between a[lo] and a[hi], instead of at the middle.

  • It probes near the target because it assumes values grow evenly from a[lo] to a[hi].
  • It is $O(\log \log n)$ on uniform data because each good estimate shrinks the range far more than halving does.
  • It is $O(n)$ in the worst case because skewed values can make every probe move just one step.
$$\text{pos} \;=\; lo + \frac{(x - a[lo]) \cdot (hi - lo)}{a[hi] - a[lo]}.$$

Pitfall Forgetting the a[hi] == a[lo] check, which divides by zero on runs of equal values.

Feynman Explain Interpolation search to a beginner in 2 minutes: define it, give one example, name one limitation.

Exponential search

exponential search finds a range $[i/2, i]$ containing the target by doubling $i$, then runs binary search inside it.

  • Doubling brackets the target because it stops at the first $i$ where $a[i] \ge x$, so $x$ lies in $[i/2, i]$.
  • The cost is $O(\log i)$ because both phases depend only on the target's position $i$, not on $n$.
  • It works on unbounded lists because it never needs to know $n$ in advance.
$$\underbrace{\log_2 i}_{\text{doubling}} + \underbrace{\log_2 (i/2)}_{\text{binary search}} \;=\; O(\log i) \;\le\; O(\log n).$$

Pitfall Starting the doubling at i = 0: 0 × 2 stays 0 forever.

Feynman Explain Exponential search to a beginner in 2 minutes: define it, give one example, name one limitation.

Ternary search

ternary search splits the range with two probes into three parts and keeps the one part that can contain the target, or the peak of a unimodal function.

  • Each round keeps one third because two probes split the range into three parts and only one can hold the target.
  • It is $O(\log n)$ because shrinking by a factor of 3 each round takes $\log_3 n$ rounds.
  • It loses to binary search on sorted arrays because $2 \log_3 n \approx 1.26 \log_2 n$ comparisons.
$$2 \log_3 n \;=\; \frac{2}{\log_2 3} \log_2 n \;\approx\; 1.26 \, \log_2 n.$$

Pitfall Claiming it beats binary search on sorted arrays because $\log_3 n < \log_2 n$, forgetting the 2 comparisons per round.

Feynman Explain Ternary search to a beginner in 2 minutes: define it, give one example, name one limitation.

Search in a rotated sorted array

rotated array search is binary search that, at each step, finds the sorted half and keeps it only if the target lies within its range.

  • One half is always sorted because the rotation creates only one "wrap" point, and it can be in only one half.
  • We test the target against the sorted half because only there does "between the ends" mean "inside".
  • It is $O(\log n)$ with distinct values because each round still throws away half the range.
$$\lfloor \log_2 n \rfloor + 1 \text{ rounds} \;=\; O(\log n).$$

Pitfall Testing the target against the unsorted half, where "between the ends" means nothing.

Feynman Explain Search in a rotated sorted array to a beginner in 2 minutes: define it, give one example, name one limitation.

Peak finding

a peak is an element with $a_{i-1} \le a_i \ge a_{i+1}$, and peak finding locates one by always keeping the half on the uphill side of the middle.

  • A peak always exists because the maximum element is one, and rising values must end somewhere.
  • The uphill half must contain a peak because walking up it either turns down or reaches the edge.
  • It is $O(\log n)$ because each comparison halves the candidate range.
$$\lceil \log_2 n \rceil \text{ comparisons} \;=\; O(\log n), \qquad \text{versus } O(n) \text{ for a linear scan.}$$

Pitfall Writing hi = mid - 1 on the downhill branch, which can throw away the peak at mid itself.

Feynman Explain Peak finding to a beginner in 2 minutes: define it, give one example, name one limitation.

Linear structures

Arrays

an array stores $n$ elements of the same size in one contiguous block, so element $i$ is found by address arithmetic.

  • Access is $O(1)$ because the address of a[i] is computed as $b + i \cdot s$.
  • Insert and delete in the middle are $O(n)$ because every later element has to shift by one slot.
  • Appending is amortized $O(1)$ because doubling makes the rare big copies add up to less than $2n$.
$$\text{address}(a[i]) \;=\; b + i \cdot s$$

Pitfall Shifting right starting from index i instead of from the end, which copies the same value over everything.

Feynman Explain Arrays to a beginner in 2 minutes: define it, give one example, name one limitation.

Singly linked list

a singly linked list is a chain of nodes, each holding a value and a pointer to the next node, accessed from a head pointer.

  • Inserting at the front is $O(1)$ because only the new node and the head pointer change.
  • Access by position is $O(n)$ because nodes are scattered in memory and can only be reached by following next.
  • Deleting needs the previous node because its next pointer is what must skip the removed node.
$$\frac{1}{n}\sum_{k=0}^{n-1} k \;=\; \frac{n-1}{2} \;=\; O(n)$$

Pitfall Losing the rest of the list by overwriting head before saving head->next.

Feynman Explain Singly linked list to a beginner in 2 minutes: define it, give one example, name one limitation.

Doubly linked list

a doubly linked list is a chain of nodes where each node points to both its next and its previous node.

  • Deleting a known node is $O(1)$ because it stores pointers to both neighbours.
  • pop_back is $O(1)$ because the tail's prev gives the new tail without walking.
  • Every insert writes four pointers because each link exists in both directions.
$$n \cdot (v + 2p) \quad \text{versus} \quad n \cdot (v + p) \text{ for a singly linked list}$$

Pitfall Updating only the next pointers and forgetting the matching prev ones.

Feynman Explain Doubly linked list to a beginner in 2 minutes: define it, give one example, name one limitation.

Circular linked list

a circular linked list is a linked list whose last node points back to the first, usually accessed through a tail pointer.

  • One tail pointer is enough because the head is always tail->next.
  • Both ends are $O(1)$ to add to because they meet at the tail's link.
  • Traversal must stop at the start node because there is no NULL at the end.
$$(t - 1) \bmod n$$

Pitfall Using while (p != NULL) and looping forever.

Feynman Explain Circular linked list to a beginner in 2 minutes: define it, give one example, name one limitation.

Stack

a stack is a collection where you add (push) and remove (pop) only at the top, so the last item in is the first out (LIFO).

  • The last item pushed is the first popped because both push and pop work at the same end, the top.
  • Every operation is $O(1)$ because only the top slot is ever read or written.
  • Bracket matching works because the most recent unclosed bracket is always the one that must close next.
$$\text{work} \;\le\; n \cdot O(1) \;=\; O(n), \qquad \text{extra space} \le n$$

Pitfall Popping without checking that the stack is non-empty.

Feynman Explain Stack to a beginner in 2 minutes: define it, give one example, name one limitation.

Queue

a queue is a first-in, first-out (FIFO) collection: you enqueue at the back and dequeue from the front.

  • The oldest item leaves first because items are added at the back and removed from the front.
  • Dequeue is $O(1)$ because the front index moves instead of the items.
  • The array is used in a circle because % capacity sends indices past the end back to slot 0.
$$\text{slot} \;=\; (\text{front} + \text{size}) \bmod \text{capacity}$$

Pitfall Shifting all items on dequeue, which turns $O(1)$ into $O(n)$.

Feynman Explain Queue to a beginner in 2 minutes: define it, give one example, name one limitation.

Deque

a deque (double-ended queue) supports adding and removing at both the front and the back.

  • All four end operations are $O(1)$ because each one touches one slot and updates one index.
  • A deque can act as a stack or a queue because it allows both same-end and opposite-end use.
  • push_front adds capacity − 1 because C's % can return a negative number for −1.
$$\text{front}_{\text{new}} \;=\; (\text{front} + \text{capacity} - 1) \bmod \text{capacity}$$

Pitfall Computing (front - 1) % capacity, which gives a negative index in C.

Feynman Explain Deque to a beginner in 2 minutes: define it, give one example, name one limitation.

Priority queue

a priority queue returns the item with the highest priority (here the smallest key) first; a binary min-heap implements it with $O(\log n)$ insert and extract-min.

  • The minimum is at the root because every parent is ≤ its children.
  • Insert and extract-min are $O(\log n)$ because a sift moves along one path of a tree of height $\log_2 n$.
  • The heap fits in an array because a complete tree has no gaps, so index arithmetic replaces pointers.
$$h \;=\; \lfloor \log_2 n \rfloor \quad\Longrightarrow\quad \text{insert, extract-min} = O(\log n)$$

Pitfall Thinking the heap array is sorted and reading the "second smallest" from index 1 (it could be at index 2).

Feynman Explain Priority queue to a beginner in 2 minutes: define it, give one example, name one limitation.

Trees

Binary tree basics

a binary tree is a set of nodes where each node has at most two children (left and right), with one root at the top.

  • Tree algorithms are recursive because a tree is a node plus two smaller trees.
  • Traversals are $O(n)$ because each node is visited exactly once.
  • A tree of $n$ nodes has height at least $\lfloor \log_2 n \rfloor$ because level $d$ can hold at most $2^d$ nodes.
$$n \;\le\; 1 + 2 + 4 + \dots + 2^h \;=\; 2^{h+1} - 1 \quad\Longrightarrow\quad h \;\ge\; \lfloor \log_2 n \rfloor$$

Pitfall Mixing up in-order and pre-order: in-order visits the node between its subtrees.

Feynman Explain Binary tree basics to a beginner in 2 minutes: define it, give one example, name one limitation.

Binary search tree

a binary search tree is a binary tree where, at every node, all keys in the left subtree are smaller and all keys in the right subtree are bigger.

  • Search follows one path because each comparison rules out a whole subtree.
  • Operations cost $O(h)$ because they walk from the root to at most a leaf.
  • Sorted insertion is the worst case because every new value goes the same way, building a chain.
$$\lfloor \log_2 n \rfloor \;\le\; h \;\le\; n - 1$$

Pitfall Checking only a node's direct children instead of whole subtrees: in a BST, every left-subtree value must be smaller.

Feynman Explain Binary search tree to a beginner in 2 minutes: define it, give one example, name one limitation.

AVL tree

an AVL tree is a binary search tree in which every node's two subtrees differ in height by at most one, restored after each change by rotations.

  • Every operation is $O(\log n)$ because the balance rule keeps the height below $1.44 \log_2 n$.
  • Rotations keep the tree a valid BST because they never change the in-order sequence of keys.
  • A rotation is $O(1)$ because it rewires a fixed number of pointers.
$$h \;<\; 1.44 \, \log_2 (n + 2)$$

Pitfall Using a single rotation for a zig-zag (left-right or right-left) case.

Feynman Explain AVL tree to a beginner in 2 minutes: define it, give one example, name one limitation.

Min-heap

a min-heap is a complete binary tree, stored in an array, where every parent is less than or equal to its children, so the minimum is at the root.

  • The minimum is at the root because every parent is ≤ its children.
  • A heap fits in an array because it is a complete tree, so children of $i$ are at $2i+1$ and $2i+2$.
  • Heapify is $O(n)$ because half the nodes are leaves and most others sink only a level or two.
$$\sum_{h=0}^{\lfloor \log_2 n \rfloor} \frac{n}{2^{h+1}} \cdot h \;\le\; n \quad\Longrightarrow\quad O(n)$$

Pitfall Building top-down by sifting down from index 0 first, which can leave lower subtrees unheaped.

Feynman Explain Min-heap to a beginner in 2 minutes: define it, give one example, name one limitation.

Max-heap

a max-heap is a complete binary tree, stored in an array, where every parent is greater than or equal to its children, so the maximum is at the root.

  • The maximum is at the root because every parent is ≥ its children.
  • Sinking swaps with the bigger child because that child is the only safe new parent.
  • Insert and remove-max are $O(\log n)$ because the complete tree has height $\lfloor \log_2 n \rfloor$.
$$\underbrace{O(n)}_{\text{build}} + \underbrace{k \cdot O(\log n)}_{k \text{ removals}} \;=\; O(n + k \log n)$$

Pitfall Swapping with the smaller child when sifting down a max-heap.

Feynman Explain Max-heap to a beginner in 2 minutes: define it, give one example, name one limitation.

B-tree

a B-tree is a balanced search tree whose nodes hold many sorted keys and children; it stays balanced by splitting full nodes and pushing the middle key up, so all leaves are at the same depth.

  • A B-tree is very short because every node has many children, so the height is $O(\log_t n)$.
  • All leaves are at the same depth because the tree only grows when the root splits.
  • Splits push the middle key up because it separates the two halves in the parent.
$$h \;\le\; \log_t \frac{n + 1}{2}$$

Pitfall Splitting by moving the middle key down into a child, instead of up into the parent.

Feynman Explain B-tree to a beginner in 2 minutes: define it, give one example, name one limitation.

Graphs

Graph representations

a graph $G = (V, E)$ is a set of vertices joined by edges; an adjacency matrix stores it as a $V \times V$ grid, an adjacency list as one neighbour list per vertex.

  • A matrix answers edge queries in $O(1)$ because the answer is one cell m[u][v].
  • A matrix needs $O(V^2)$ memory because it stores every pair, edge or not.
  • Lists need $O(V + E)$ memory because they store only real edges.
$$E \;\le\; \frac{V(V-1)}{2}, \qquad \sum_{v} \deg(v) \;=\; 2E$$

Pitfall Storing only one direction of an undirected edge.

Feynman Explain Graph representations to a beginner in 2 minutes: define it, give one example, name one limitation.

Breadth-first search (BFS)

breadth-first search explores a graph layer by layer from a start vertex, using a queue, and finds the fewest-edges distance to every reachable vertex.

  • BFS explores in layers because its queue processes vertices in the order they were discovered.
  • It finds shortest unweighted paths because every vertex is first reached from the layer just before it.
  • It runs in $O(V + E)$ on lists because each vertex is enqueued once and each edge is checked a constant number of times.
$$O\Big(V + \sum_{v} \deg(v)\Big) \;=\; O(V + 2E) \;=\; O(V + E)$$

Pitfall Using a stack instead of a queue, which turns BFS into DFS and loses the shortest-path property.

Feynman Explain Breadth-first search (BFS) to a beginner in 2 minutes: define it, give one example, name one limitation.

Depth-first search (DFS)

depth-first search explores a graph by following one path as deep as possible and backtracking at dead ends, using recursion or a stack.

  • DFS dives deep first because it recurses into a neighbour before looking at the next one.
  • It backtracks to the latest junction because the call stack is last-in, first-out.
  • It is $O(V + E)$ because each vertex is visited once and each adjacency list scanned once.
$$O\Big(V + \sum_{v} \deg(v)\Big) \;=\; O(V + E)$$

Pitfall Marking a vertex after exploring its neighbours, so cycles cause infinite recursion.

Feynman Explain Depth-first search (DFS) to a beginner in 2 minutes: define it, give one example, name one limitation.

Dijkstra's algorithm

Dijkstra's algorithm computes single-source shortest paths in a graph with non-negative weights by repeatedly settling the closest unsettled vertex and relaxing its edges.

  • The closest unsettled distance is final because non-negative edges can only make other routes longer.
  • Negative edges break it because a settled distance could still be improved later.
  • The heap version is $O((V + E) \log V)$ because each settle and each improvement is a heap operation.
$$O\big((V + E) \log V\big) \text{ with a heap}, \qquad O(V^2) \text{ with an array scan}$$

Pitfall Using it on a graph with a negative edge.

Feynman Explain Dijkstra's algorithm to a beginner in 2 minutes: define it, give one example, name one limitation.

Bellman-Ford algorithm

the Bellman-Ford algorithm computes single-source shortest paths by relaxing every edge $V - 1$ times; it allows negative edges and detects negative cycles.

  • It allows negative edges because no distance is declared final before all rounds are done.
  • $V - 1$ rounds suffice because a shortest simple path has at most $V - 1$ edges.
  • An improvement in round $V$ proves a negative cycle because without one, nothing can improve any more.
$$(V - 1) \cdot E \;=\; O(VE)$$

Pitfall Running only one round and assuming it is enough (it was here only because the edge order was lucky).

Feynman Explain Bellman-Ford algorithm to a beginner in 2 minutes: define it, give one example, name one limitation.

Floyd-Warshall algorithm

the Floyd-Warshall algorithm computes shortest paths between all pairs of vertices by allowing each vertex in turn as an intermediate stop.

  • It finds all pairs at once because it updates the whole matrix for each new stop-over.
  • It costs $O(V^3)$ because it checks every hub for every pair.
  • The hub loop is outermost because each stage builds on answers that used only earlier hubs.
$$V \cdot V \cdot V \;=\; O(V^3) \text{ time}, \qquad O(V^2) \text{ space}$$

Pitfall Putting the $k$ loop inside the $i$ and $j$ loops.

Feynman Explain Floyd-Warshall algorithm to a beginner in 2 minutes: define it, give one example, name one limitation.

Kruskal's algorithm

Kruskal's algorithm builds a minimum spanning tree by taking edges in increasing weight order and keeping each one that connects two different components.

  • Kruskal takes the cheapest safe edge because the cheapest edge between two groups is always part of some minimum tree.
  • It rejects edges inside one group because they would close a cycle.
  • It runs in $O(E \log E)$ because sorting the edges dominates.
$$O(E \log E) + O\big(E \cdot \alpha(V)\big) \;=\; O(E \log E) \;=\; O(E \log V)$$

Pitfall Rejecting an edge just because one end is already in the tree; only reject when both ends are in the same group.

Feynman Explain Kruskal's algorithm to a beginner in 2 minutes: define it, give one example, name one limitation.

Prim's algorithm

Prim's algorithm builds a minimum spanning tree by growing one tree from a start vertex, always adding the cheapest edge that connects the tree to a new vertex.

  • Prim always adds the cheapest edge leaving the tree because that edge is safe to include in a minimum spanning tree.
  • It keeps one connected tree because every new vertex attaches to the existing tree.
  • The array version is $O(V^2)$ because each of $V$ rounds scans all vertices for the smallest key.
$$O(V^2) \text{ (array)}, \qquad O\big((V + E) \log V\big) \text{ (binary heap)}$$

Pitfall Updating keys with key[u] + w as in Dijkstra.

Feynman Explain Prim's algorithm to a beginner in 2 minutes: define it, give one example, name one limitation.

Topological sort

a topological sort of a directed acyclic graph is an ordering of its vertices such that every edge $u \to v$ has $u$ before $v$. Kahn's algorithm builds one by repeatedly removing vertices with no incoming edges.

  • In-degree-0 vertices go first because nothing has to come before them.
  • Outputting a vertex can unlock others because it removes one prerequisite from each successor.
  • It costs $O(V + E)$ because each vertex and edge is handled once.
$$O(V + E) \text{ with adjacency lists}, \qquad O(V^2) \text{ with a matrix}$$

Pitfall Forgetting to check for cycles, so a partial order is returned silently.

Feynman Explain Topological sort to a beginner in 2 minutes: define it, give one example, name one limitation.

Cycle detection

a directed graph has a cycle exactly when DFS finds a back edge, an edge to a vertex that is still on the current DFS path (grey).

  • An edge to a grey vertex means a cycle because grey vertices form the current path, so the edge closes a loop.
  • Edges to black vertices are safe because a finished vertex cannot reach the current path.
  • It costs $O(V + E)$ because it is a single DFS with constant work per edge.
$$O(V + E) \text{ (lists)}, \qquad O\big(E \, \alpha(V)\big) \text{ (Union-Find, undirected)}$$

Pitfall Using a single "visited" flag on a directed graph and reporting false cycles.

Feynman Explain Cycle detection to a beginner in 2 minutes: define it, give one example, name one limitation.

Union-Find (disjoint sets)

Union-Find (a disjoint-set structure) keeps elements in non-overlapping groups, each stored as a tree with a root, and supports find (which group?) and union (merge two groups).

  • Same root means same group because each group is one tree with one root.
  • Union by size keeps trees short because the smaller tree goes under the bigger one, so heights grow only slowly.
  • Path compression speeds up later finds because every node on a path is linked straight to the root.
$$O\big(m \, \alpha(n)\big), \qquad \alpha(n) \le 4 \text{ for any } n \text{ you will ever meet}$$

Pitfall Linking p[a] = b with the original elements instead of their roots, which breaks the trees.

Feynman Explain Union-Find (disjoint sets) to a beginner in 2 minutes: define it, give one example, name one limitation.

Algorithm paradigms

Divide and conquer

divide and conquer solves a problem by splitting it into smaller independent subproblems of the same type, solving them recursively, and combining their solutions.

  • Divide and conquer is recursive because each subproblem is a smaller copy of the original.
  • Merge sort is $O(n \log n)$ because it has $\log_2 n$ levels and $O(n)$ combine work per level.
  • Binary search is $O(\log n)$ because it solves only one subproblem per level.
$$\underbrace{n}_{\text{work per level}} \times \underbrace{\log_2 n}_{\text{levels}} \;=\; O(n \log n)$$

Pitfall Forgetting the base case, which recurses forever.

Feynman Explain Divide and conquer to a beginner in 2 minutes: define it, give one example, name one limitation.

Greedy algorithms

a greedy algorithm builds a solution step by step, always taking the choice that looks best right now and never revising it.

  • Greedy is fast because it makes one pass without ever backtracking.
  • Earliest finish is safe because it leaves the most time for the remaining talks.
  • Greedy can fail because a choice that looks best now can block a better combination later.
$$O(n \log n)_{\text{sort}} + O(n)_{\text{scan}} \;=\; O(n \log n)$$

Pitfall Assuming greedy is optimal without a proof.

Feynman Explain Greedy algorithms to a beginner in 2 minutes: define it, give one example, name one limitation.

Dynamic programming

dynamic programming solves a problem by breaking it into overlapping subproblems, solving each one once, and storing the answers in a table for reuse.

  • DP is fast because each subproblem is solved once and then looked up.
  • Naive Fibonacci is exponential because the same subproblems are recomputed in every branch.
  • DP time is subproblems × work each because every table entry is filled exactly once.
$$\text{naive calls}(n) = 2\,fib(n+1) - 1 = O(1.618^n), \qquad \text{DP} = O(n)$$

Pitfall Not defining precisely what a table entry means, so the recurrence comes out wrong.

Feynman Explain Dynamic programming to a beginner in 2 minutes: define it, give one example, name one limitation.

Backtracking

backtracking builds candidate solutions one choice at a time and abandons a partial solution (backtracks) as soon as it cannot lead to a valid complete solution.

  • Backtracking is DFS over choices because it extends one partial solution as deep as possible before trying alternatives.
  • Pruning saves time because one early clash removes every solution that would extend it.
  • Choices must be undone because the next option must start from the same state as the first.
$$n^n \;\gg\; n! \;\gg\; \text{nodes actually explored}$$

Pitfall Forgetting to undo a choice (when state is shared), so later branches see stale decisions.

Feynman Explain Backtracking to a beginner in 2 minutes: define it, give one example, name one limitation.

NP-completeness

a problem is NP-complete if proposed solutions can be checked in polynomial time (it is in NP) and every problem in NP can be reduced to it in polynomial time (it is NP-hard). 3-SAT was among the first proved NP-complete.

  • 3-SAT is in NP because checking an assignment takes one pass over the clauses.
  • Brute force is exponential because $n$ variables have $2^n$ assignments.
  • Reductions show hardness because a fast solver for the target would give a fast solver for the source.
$$\text{check} = O(m), \qquad \text{brute force} = O(2^n \cdot m)$$

Pitfall Reducing in the wrong direction (new problem → 3-SAT).

Feynman Explain NP-completeness to a beginner in 2 minutes: define it, give one example, name one limitation.

ML foundations

Learning paradigms

supervised learning learns a mapping from features to known labels; unsupervised learning finds structure in unlabelled data; reinforcement learning learns actions that maximise reward.

  • Supervised learning needs labels because it learns by comparing its predictions with the correct answers.
  • Classification and regression differ because one predicts a category and the other a number.
  • Unsupervised learning finds structure because without answers, all it can use is how the inputs relate to each other.
$$\hat f \;=\; \arg\min_{f} \; \frac{1}{n} \sum_{i=1}^{n} L\big(f(x_i),\, y_i\big)$$

Pitfall Calling a numeric prediction "classification" because the numbers are integers (predicting a count is still regression).

Feynman Explain Learning paradigms to a beginner in 2 minutes: define it, give one example, name one limitation.

Classification metrics

a confusion matrix counts TP, FP, FN, TN; precision = TP/(TP+FP), recall = TP/(TP+FN), and F1 is their harmonic mean.

  • Accuracy can mislead because on imbalanced data predicting the majority class already scores high.
  • Precision measures trust in positives because its denominator is everything predicted positive.
  • Recall measures coverage because its denominator is everything actually positive.
$$\text{Precision} = \tfrac{TP}{TP + FP} = \tfrac{40}{50} = 0.80, \quad \text{Recall} = \tfrac{TP}{TP + FN} = \tfrac{40}{60} \approx 0.67, \quad F_1 = \tfrac{2PR}{P + R} \approx 0.73$$

Pitfall Swapping FP and FN: FP is a false alarm (predicted positive), FN is a miss.

Feynman Explain Classification metrics to a beginner in 2 minutes: define it, give one example, name one limitation.

Regression metrics

MAE is the mean absolute error, MSE the mean squared error (RMSE its square root), and R² the share of the variance in $y$ explained by the model.

  • MAE treats all errors equally because it averages their absolute sizes.
  • MSE punishes big errors because squaring makes large errors grow much faster than small ones.
  • RMSE is easier to interpret because the square root brings it back to the units of $y$.
$$\text{MAE} = \tfrac{1}{n}\sum |e_i| = 0.875, \quad \text{MSE} = \tfrac{1}{n}\sum e_i^2 \approx 1.31, \quad R^2 = 1 - \tfrac{\sum e_i^2}{\sum (y_i - \bar y)^2} \approx 0.64$$

Pitfall Forgetting the absolute value in MAE, so positive and negative errors cancel out.

Feynman Explain Regression metrics to a beginner in 2 minutes: define it, give one example, name one limitation.

Bias–variance trade-off

bias is the error of the average model (too simple to capture the truth), variance is how much the model changes between training samples (too sensitive), and the trade-off is that reducing one tends to increase the other.

  • Simple models underfit because they cannot represent the true shape, which is bias.
  • Complex models overfit because they also fit the noise of their particular training sample, which is variance.
  • There is an optimal complexity because bias falls and variance rises as flexibility grows.
$$\mathbb{E}\big[(y - \hat f(x))^2\big] \;=\; \underbrace{\big(\mathbb{E}[\hat f(x)] - f(x)\big)^2}_{\text{bias}^2} \;+\; \underbrace{\mathbb{E}\big[(\hat f(x) - \mathbb{E}[\hat f(x)])^2\big]}_{\text{variance}} \;+\; \underbrace{\sigma^2}_{\text{noise}}$$

Pitfall Fixing overfitting by adding more model capacity.

Feynman Explain Bias–variance trade-off to a beginner in 2 minutes: define it, give one example, name one limitation.

Regularization (L1 and L2)

regularization adds a penalty on the size of the weights to the loss; L2 (ridge) penalises squared weights and shrinks them, L1 (lasso) penalises absolute weights and can set some exactly to zero.

  • Regularization reduces overfitting because it makes large, noise-chasing weights expensive.
  • L1 sets weights to exactly zero because it subtracts a constant amount, stopping at zero.
  • L2 never zeroes weights because dividing a nonzero number never gives zero.
$$J_{L2}(w) = \tfrac12 \lVert y - Xw \rVert^2 + \tfrac{\lambda}{2} \lVert w \rVert_2^2, \qquad J_{L1}(w) = \tfrac12 \lVert y - Xw \rVert^2 + \lambda \lVert w \rVert_1$$

Pitfall Penalising the bias (intercept) term, which shifts all predictions for no reason.

Feynman Explain Regularization (L1 and L2) to a beginner in 2 minutes: define it, give one example, name one limitation.

Cross-validation

$k$-fold cross-validation splits the data into $k$ parts, trains $k$ times on $k - 1$ parts while testing on the remaining one, and averages the $k$ scores.

  • CV gives a more reliable score because it averages over several different test blocks.
  • Every sample is tested once because each fold serves as the test block exactly once.
  • The spread matters because a small difference in mean can be pure noise.
$$\text{CV} = \frac{1}{k}\sum_{f=1}^{k} s_f = \frac{0.82 + 0.78 + 0.85 + 0.80 + 0.75}{5} = 0.80, \qquad \text{sd} \approx 0.034$$

Pitfall Reporting only the mean, without the spread across folds.

Feynman Explain Cross-validation to a beginner in 2 minutes: define it, give one example, name one limitation.

Data preprocessing

preprocessing transforms raw data into a model-ready form: scaling numeric features to comparable ranges, encoding categories as numbers, and imputing missing values.

  • Scaling matters because distance and gradient methods treat a big-number feature as more important.
  • Standardization gives mean 0 and sd 1 because it subtracts the mean and divides by the sd.
  • One-hot encoding avoids fake order because each category gets its own independent column.
$$z = \frac{x - \mu}{\sigma} = \frac{20 - 35}{11.18} \approx -1.34, \qquad x' = \frac{x - \min}{\max - \min} = \frac{30 - 20}{50 - 20} \approx 0.33$$

Pitfall Computing the mean and sd on the full dataset before splitting (data leakage).

Feynman Explain Data preprocessing to a beginner in 2 minutes: define it, give one example, name one limitation.

Data leakage

data leakage is when information that would not be available at prediction time (test data, future data, or the label itself) is used to train or evaluate a model.

  • Leakage inflates scores because the model uses information it won't have in real use.
  • Split before preprocessing because fitted parameters must come from training data only.
  • Future-only features leak because they partly encode the answer.
$$z_{\text{correct}} = \frac{80 - 30}{8.16} \approx 6.1, \qquad z_{\text{leaky}} = \frac{80 - 42.5}{22.8} \approx 1.6$$

Pitfall Imputing missing values or selecting features using the whole dataset.

Feynman Explain Data leakage to a beginner in 2 minutes: define it, give one example, name one limitation.

ML algorithms

Linear regression

linear regression models the target as a weighted sum of the features plus a bias, $\hat y = w^\top x + b$, with weights chosen to minimise the mean squared error.

  • The slope is a ratio of covariance to variance because it measures how much $y$ moves per unit move of $x$.
  • The line passes through $(\bar x, \bar y)$ because $b = \bar y - w \bar x$.
  • Residuals sum to zero because the least-squares intercept balances positive and negative errors.
$$\min_{w, b} \; \frac{1}{n}\sum_{i=1}^{n} \big(y_i - (w^\top x_i + b)\big)^2 \quad\Longrightarrow\quad w = (X^\top X)^{-1} X^\top y$$

Pitfall Dividing the slope formula the wrong way round ($\sum (x - \bar x)^2$ is the denominator).

Feynman Explain Linear regression to a beginner in 2 minutes: define it, give one example, name one limitation.

Logistic regression

logistic regression predicts the probability of the positive class as $\sigma(w^\top x + b)$, trained by minimising the log loss.

  • The output is a probability because the sigmoid maps any score into (0, 1).
  • The boundary is linear because $p = 0.5$ exactly when $w^\top x + b = 0$.
  • Log loss punishes confident mistakes because $-\ln p$ grows without limit as $p \to 0$.
$$J(w, b) = -\frac{1}{n}\sum_{i=1}^{n} \Big[y_i \ln p_i + (1 - y_i)\ln(1 - p_i)\Big], \qquad \frac{\partial J}{\partial w} = \frac{1}{n}\sum_i (p_i - y_i)\,x_i$$

Pitfall Forgetting the bias $b$ in the score.

Feynman Explain Logistic regression to a beginner in 2 minutes: define it, give one example, name one limitation.

k-nearest neighbours (KNN)

k-nearest neighbours predicts the label of a point from the majority label (or average value) of its $k$ closest training points.

  • KNN needs no training because it stores the data and decides at prediction time.
  • Predictions are slow because each one computes distances to all $n$ training points.
  • Scaling is essential because distances are dominated by the largest-valued feature.
$$d(p, q) = \sqrt{\sum_{j=1}^{d} (p_j - q_j)^2}, \qquad \text{one prediction: } O(nd)$$

Pitfall Forgetting to scale features before computing distances.

Feynman Explain k-nearest neighbours (KNN) to a beginner in 2 minutes: define it, give one example, name one limitation.

Naive Bayes

Naive Bayes classifies by Bayes' rule, assuming features are independent given the class: $P(c \mid x) \propto P(c) \prod_j P(x_j \mid c)$.

  • Training is just counting because every probability is a frequency in the training data.
  • Likelihoods are multiplied because features are assumed independent given the class.
  • Smoothing is needed because one zero count makes a class's whole product zero.
$$P(c \mid x_1, \dots, x_m) \;=\; \frac{P(c) \prod_{j=1}^{m} P(x_j \mid c)}{\sum_{c'} P(c') \prod_{j} P(x_j \mid c')}$$

Pitfall Forgetting the prior $P(c)$ in the product.

Feynman Explain Naive Bayes to a beginner in 2 minutes: define it, give one example, name one limitation.

Decision tree

a decision tree predicts by following a sequence of feature tests from the root to a leaf, with each test chosen to maximise information gain (reduction in entropy).

  • Splits are chosen by information gain because the best question is the one that makes the groups purest.
  • Entropy is 1 for a 50/50 group because that is maximum uncertainty for two classes.
  • Trees need no scaling because each split compares one feature with a threshold.
$$H(S) = -\sum_{c} p_c \log_2 p_c, \qquad \text{Gain} = H(S) - \sum_{i} \frac{|S_i|}{|S|} H(S_i)$$

Pitfall Forgetting to weight each child's entropy by its size.

Feynman Explain Decision tree to a beginner in 2 minutes: define it, give one example, name one limitation.

Random forest

a random forest is an ensemble of decision trees, each trained on a bootstrap sample with random feature subsets at each split, combined by majority vote or averaging.

  • Averaging trees reduces variance because their different errors partly cancel.
  • Bootstrap samples make trees differ because each sees a different mix of rows.
  • Feature sampling matters because it lowers the correlation between trees, which sets the variance floor.
$$\operatorname{Var}\Big(\frac{1}{B}\sum_{b=1}^{B} T_b\Big) \;=\; \rho\,\sigma^2 + \frac{1 - \rho}{B}\,\sigma^2$$

Pitfall Thinking more trees cause overfitting; they don't, they just cost more.

Feynman Explain Random forest to a beginner in 2 minutes: define it, give one example, name one limitation.

AdaBoost

AdaBoost builds a strong classifier as a weighted vote of weak learners trained in sequence, each on data re-weighted to emphasise the previous learners' mistakes.

  • Mistakes get heavier because their weights are multiplied by $e^{\alpha} > 1$.
  • Accurate learners get a bigger say because $\alpha$ grows as ε shrinks.
  • A coin-flip learner gets $\alpha = 0$ because its vote carries no information.
$$\alpha_t = \tfrac12 \ln\frac{1 - \varepsilon_t}{\varepsilon_t}, \qquad w_i \leftarrow \frac{w_i \, e^{-\alpha_t y_i h_t(x_i)}}{Z_t}, \qquad H(x) = \operatorname{sign}\Big(\sum_t \alpha_t h_t(x)\Big)$$

Pitfall Forgetting to normalise the weights after updating.

Feynman Explain AdaBoost to a beginner in 2 minutes: define it, give one example, name one limitation.

Gradient boosting and XGBoost

gradient boosting builds an additive model of small trees, each fitted to the negative gradient (the residuals) of the loss of the current ensemble; XGBoost is a regularized, highly optimised implementation using second-order information.

  • Each tree fits the residuals because they are what the current ensemble still gets wrong.
  • A small learning rate helps because many partial corrections generalise better than a few big ones.
  • XGBoost shrinks leaf values because λ in $-G/(H + \lambda)$ penalises large outputs.
$$w^* = -\frac{G}{H + \lambda}, \qquad \text{Gain} = \frac12\left[\frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{(G_L + G_R)^2}{H_L + H_R + \lambda}\right] - \gamma$$

Pitfall Using a large learning rate with many rounds, which overfits quickly.

Feynman Explain Gradient boosting and XGBoost to a beginner in 2 minutes: define it, give one example, name one limitation.

Support vector machine (SVM)

a support vector machine is a classifier that finds the separating boundary with the maximum margin; the training points on the margin are the support vectors.

  • Only support vectors matter because the margin is set by the closest points of each class.
  • Minimising $\lVert w \rVert$ widens the margin because the margin width is $2/\lVert w \rVert$.
  • Soft margins handle noise because they let some points violate the margin at a cost set by C.
$$\min_{w, b} \; \tfrac12 \lVert w \rVert^2 \quad \text{subject to} \quad y_i\,(w^\top x_i + b) \ge 1 \;\; \forall i, \qquad \text{margin} = \frac{2}{\lVert w \rVert}$$

Pitfall Saying all training points define the boundary; only the support vectors do.

Feynman Explain Support vector machine (SVM) to a beginner in 2 minutes: define it, give one example, name one limitation.

k-means clustering

k-means partitions data into $k$ clusters by alternating between assigning each point to its nearest centroid and moving each centroid to the mean of its points, minimising the within-cluster sum of squares.

  • Each iteration lowers WCSS because both the assignment and the update step can only reduce it.
  • It converges because WCSS cannot decrease forever with finitely many assignments.
  • Results depend on the start because it only reaches a local optimum.
$$\text{WCSS} = \sum_{j=1}^{k} \sum_{x \in C_j} \lVert x - \mu_j \rVert^2 \qquad (= 4 \times 0.5^2 = 1.0 \text{ at the end})$$

Pitfall Confusing k-means (unsupervised clustering) with KNN (supervised classification).

Feynman Explain k-means clustering to a beginner in 2 minutes: define it, give one example, name one limitation.

Hierarchical clustering

agglomerative hierarchical clustering starts with every point alone and repeatedly merges the two closest clusters, producing a dendrogram that can be cut at any height.

  • No $k$ is needed upfront because the dendrogram contains every number of clusters at once.
  • Merge heights show strength of grouping because they record the distance at which clusters joined.
  • It needs $n - 1$ merges because each merge reduces the number of clusters by one.
$$d_{\text{single}}(P, Q) = \min_{p \in P,\, q \in Q} d(p, q), \qquad d_{\text{complete}}(P, Q) = \max_{p \in P,\, q \in Q} d(p, q)$$

Pitfall Mixing up single (minimum) and complete (maximum) linkage.

Feynman Explain Hierarchical clustering to a beginner in 2 minutes: define it, give one example, name one limitation.

Gaussian mixture model (GMM)

a Gaussian mixture model describes the data as a weighted sum of Gaussian components and is fitted with the EM algorithm, alternating soft assignments (E-step) and parameter updates (M-step).

  • Assignments are soft because each point gets a probability for every component.
  • The E-step uses Bayes' rule because it inverts "component → point" into "point → component".
  • The M-step uses weighted averages because each point counts in proportion to its responsibility.
$$p(x) = \sum_{k=1}^{K} \pi_k \, \mathcal{N}(x \mid \mu_k, \sigma_k^2), \qquad r_{ik} = \frac{\pi_k \mathcal{N}(x_i \mid \mu_k, \sigma_k^2)}{\sum_j \pi_j \mathcal{N}(x_i \mid \mu_j, \sigma_j^2)}$$

Pitfall Thinking a GMM gives hard labels; it gives probabilities (you can take the most likely component afterwards).

Feynman Explain Gaussian mixture model (GMM) to a beginner in 2 minutes: define it, give one example, name one limitation.

DBSCAN

DBSCAN (density-based spatial clustering of applications with noise) forms clusters from dense regions: core points with at least minPts neighbours within ε, the border points around them, and labels the rest as noise.

  • Clusters are dense regions because points join clusters through chains of core points.
  • The number of clusters is automatic because it is the number of connected dense regions.
  • Outliers are labelled noise because they are neither dense nor near a dense point.
$$N_\varepsilon(p) = \{\, q : \lVert p - q \rVert \le \varepsilon \,\}, \qquad p \text{ is core} \iff |N_\varepsilon(p)| \ge \text{minPts}$$

Pitfall Forgetting that a point counts as its own neighbour (or double-counting it), which changes core decisions.

Feynman Explain DBSCAN to a beginner in 2 minutes: define it, give one example, name one limitation.

Principal component analysis (PCA)

PCA finds orthogonal directions of maximum variance (the eigenvectors of the covariance matrix) and represents the data by its projections onto the top few of them.

  • Eigenvalues measure variance per component because they are the variance of the data projected onto each eigenvector.
  • The first components keep the most information because they are sorted by variance.
  • Components are uncorrelated because they are orthogonal eigenvectors of the covariance matrix.
$$\text{EVR}(k) = \frac{\sum_{i=1}^{k} \lambda_i}{\sum_{i=1}^{d} \lambda_i} = \frac{4 + 2}{7.5} = 0.80$$

Pitfall Running PCA on unscaled features, so the biggest-unit feature becomes PC1.

Feynman Explain Principal component analysis (PCA) to a beginner in 2 minutes: define it, give one example, name one limitation.

Deep learning

The artificial neuron

an artificial neuron computes a weighted sum of its inputs plus a bias, $z = w^\top x + b$, and outputs $g(z)$ for a non-linear activation function $g$.

  • A neuron is a weighted sum plus a bias because that lets each input count with its own learned importance.
  • The bias shifts the threshold because it is added before the activation.
  • The activation must be non-linear because stacked linear functions stay linear.
$$a = \sigma\Big(\sum_{j} w_j x_j + b\Big) = \sigma(0.5 \cdot 2 - 0.3 \cdot 3 + 0.1) = \sigma(0.2) \approx 0.550$$

Pitfall Forgetting the bias in $z$.

Feynman Explain The artificial neuron to a beginner in 2 minutes: define it, give one example, name one limitation.

Activation functions

an activation function is the non-linear function applied to a neuron's weighted sum; common ones are sigmoid, tanh, ReLU, Leaky ReLU, and softmax for multi-class outputs.

  • Sigmoid suits a single probability because it maps any score into (0, 1).
  • Softmax suits one-of-$K$ classes because its outputs are positive and sum to 1.
  • ReLU trains deep nets well because its slope is 1 for positive inputs, so gradients don't shrink.
$$\sigma'(z) = \sigma(z)(1 - \sigma(z)) \le 0.25, \qquad \tanh'(z) = 1 - \tanh^2(z) \le 1, \qquad \text{ReLU}'(z) = \begin{cases} 1 & z > 0 \\ 0 & z < 0 \end{cases}$$

Pitfall Using softmax for multi-label problems (several classes can be true at once), where independent sigmoids are right.

Feynman Explain Activation functions to a beginner in 2 minutes: define it, give one example, name one limitation.

Multi-layer perceptron (MLP)

a multi-layer perceptron is a feed-forward network of fully connected layers, each computing $g(Wx + b)$, with at least one hidden layer between input and output.

  • Hidden layers learn new features because each neuron combines the inputs in its own way.
  • An MLP can solve XOR because its hidden features make the classes linearly separable.
  • Each layer has $n_{\text{in}} n_{\text{out}} + n_{\text{out}}$ parameters because every connection has a weight and every neuron a bias.
$$h = \text{ReLU}(W_1 x + b_1), \quad \hat y = \sigma(w_2^\top h + b_2), \qquad \#\text{params of a layer} = n_{\text{in}} \cdot n_{\text{out}} + n_{\text{out}}$$

Pitfall Forgetting the biases when counting parameters.

Feynman Explain Multi-layer perceptron (MLP) to a beginner in 2 minutes: define it, give one example, name one limitation.

Forward propagation

forward propagation computes a network's output and loss by applying each layer in order, $z_\ell = W_\ell a_{\ell-1} + b_\ell$, $a_\ell = g(z_\ell)$, storing the intermediate values for backpropagation.

  • The order is fixed because each layer's input is the previous layer's output.
  • Intermediate values are cached because backpropagation needs them to compute gradients.
  • The loss is the last step because it compares the final prediction with the target.
$$L = -\ln \sigma\big(w_2^\top \,\text{ReLU}(W_1 x + b_1) + b_2\big) = -\ln \sigma(-0.8) \approx 1.17$$

Pitfall Applying the activation before adding the bias.

Feynman Explain Forward propagation to a beginner in 2 minutes: define it, give one example, name one limitation.

Backpropagation

backpropagation computes the gradient of the loss with respect to every parameter by applying the chain rule backwards through the network, reusing values from the forward pass.

  • Backprop uses the chain rule because the loss is a composition of simple functions.
  • It runs backwards because each layer's gradient needs the gradient of the layer above it.
  • It reuses the forward cache because local derivatives depend on the stored $z$ and $a$ values.
$$\frac{\partial L}{\partial w} = \underbrace{-\frac{1}{a}}_{-1.333} \cdot \underbrace{a(1 - a)}_{0.187} \cdot \underbrace{x}_{2} = (a - y)\,x \approx -0.499, \qquad w \leftarrow w - \eta \frac{\partial L}{\partial w}$$

Pitfall Forgetting a factor of the chain, typically the activation's slope.

Feynman Explain Backpropagation to a beginner in 2 minutes: define it, give one example, name one limitation.

Loss functions

a loss function measures how far a model's predictions are from the targets; MSE averages squared errors (regression), cross-entropy averages $-\ln$ of the probability given to the true class (classification).

  • Training minimises the loss because the loss defines what "better predictions" means.
  • Cross-entropy punishes confident mistakes because $-\ln p$ grows without bound as $p \to 0$.
  • MSE suits regression because it measures squared distance between numbers.
$$\text{MSE} = \tfrac13(0.1^2 + 0.2^2 + 0.4^2) = 0.07, \qquad \text{BCE} = -\tfrac13(\ln 0.9 + \ln 0.8 + \ln 0.6) \approx 0.280$$

Pitfall Using $p$ instead of $1 - p$ for examples whose true label is 0.

Feynman Explain Loss functions to a beginner in 2 minutes: define it, give one example, name one limitation.

Gradient descent

gradient descent minimises a function by repeatedly moving the parameters a small step in the direction opposite to the gradient: $w \leftarrow w - \eta \nabla L(w)$.

  • Stepping against the gradient lowers the loss because the gradient points in the direction of steepest increase.
  • Steps shrink near the minimum because the gradient approaches 0 there.
  • Too large a learning rate diverges because each step overshoots by more than the previous distance.
$$w_{t+1} - 3 = (1 - 2\eta)(w_t - 3) \quad\Longrightarrow\quad \eta = 0.1: \text{factor } 0.8, \qquad \eta > 1: |\text{factor}| > 1 \text{ (diverges)}$$

Pitfall Adding the gradient instead of subtracting it (gradient ascent).

Feynman Explain Gradient descent to a beginner in 2 minutes: define it, give one example, name one limitation.

SGD and mini-batches

stochastic gradient descent updates the parameters using the gradient of one example (or a small random mini-batch) at a time, instead of the whole training set.

  • SGD is cheap per step because it uses only a few examples to estimate the gradient.
  • Mini-batch gradients are noisy because a small sample doesn't represent the whole dataset exactly.
  • Larger batches are less noisy because averaging more examples reduces variance.
$$\bar g_B = \frac{1}{m}\sum_{i \in B} \nabla L_i(w) \approx \frac{1}{n}\sum_{i=1}^{n} \nabla L_i(w), \qquad \text{noise (std)} \propto \frac{1}{\sqrt m}$$

Pitfall Confusing epochs with iterations.

Feynman Explain SGD and mini-batches to a beginner in 2 minutes: define it, give one example, name one limitation.

Momentum

momentum is gradient descent with a velocity term: each update is an exponentially decaying sum of past gradients, $v \leftarrow \beta v + g$, $w \leftarrow w - \eta v$.

  • Momentum speeds up consistent directions because gradients that agree add up in the velocity.
  • It damps oscillations because gradients that alternate in sign cancel in the velocity.
  • The velocity can reach $g/(1 - \beta)$ because it sums a geometric series of past gradients.
$$v_t = g_t + \beta g_{t-1} + \beta^2 g_{t-2} + \dots, \qquad \text{constant } g:\; v \to \frac{g}{1 - \beta} = 10g \text{ for } \beta = 0.9$$

Pitfall Forgetting to carry $v$ from one step to the next (resetting it to 0).

Feynman Explain Momentum to a beginner in 2 minutes: define it, give one example, name one limitation.

Adam optimiser

Adam (adaptive moment estimation) updates each weight using bias-corrected moving averages of its gradient and squared gradient: $w \leftarrow w - \eta \, \hat m / (\sqrt{\hat v} + \varepsilon)$.

  • Adam combines direction and scale because $m$ averages gradients and $v$ averages their squares.
  • Steps are roughly the learning rate in size because $\hat m/\sqrt{\hat v}$ is close to ±1 for consistent gradients.
  • Bias correction is needed because both averages start at 0 and are too small early on.
$$w_{t} = w_{t-1} - \eta \frac{\hat m_t}{\sqrt{\hat v_t} + \varepsilon}, \qquad t = 1:\; w = 0 - 0.1 \cdot \frac{-6}{\sqrt{36}} = 0.1$$

Pitfall Forgetting bias correction, which makes early steps the wrong size.

Feynman Explain Adam optimiser to a beginner in 2 minutes: define it, give one example, name one limitation.

RMSProp

RMSProp divides each weight's gradient by the root mean square of its recent gradients, $w \leftarrow w - \eta\, g/(\sqrt{s} + \varepsilon)$ with $s$ a running average of $g^2$.

  • RMSProp adapts the step per weight because each weight has its own running average of squared gradients.
  • Large-gradient weights get smaller steps because their gradient is divided by a larger RMS.
  • It keeps learning on long runs because its average decays, unlike AdaGrad's ever-growing sum.
$$s_t = \rho s_{t-1} + (1 - \rho) g_t^2, \qquad w_t = w_{t-1} - \eta \frac{g_t}{\sqrt{s_t} + \varepsilon}, \qquad \text{step 1: } 0.1 \cdot \frac{6}{\sqrt{3.6}} \approx 0.316$$

Pitfall Forgetting $\varepsilon$, which divides by zero when $s$ is 0.

Feynman Explain RMSProp to a beginner in 2 minutes: define it, give one example, name one limitation.

Dropout

dropout randomly sets a fraction $p$ of a layer's outputs to zero at each training step (scaling the rest by $1/(1 - p)$), and uses all neurons at test time.

  • Dropout reduces overfitting because neurons can't rely on specific partners and must learn robust features.
  • Kept outputs are scaled by $1/(1 - p)$ because that keeps the expected signal equal to the test-time signal.
  • A new mask is drawn every step because that trains many different thinned sub-networks.
$$\tilde a_i = \frac{m_i}{1 - p}\, a_i, \quad m_i \sim \text{Bernoulli}(1 - p), \qquad \mathbb{E}[\tilde a_i] = a_i$$

Pitfall Leaving dropout on at test time.

Feynman Explain Dropout to a beginner in 2 minutes: define it, give one example, name one limitation.

Batch normalization

batch normalization normalizes each feature to zero mean and unit variance over the mini-batch, then applies a learned scale $\gamma$ and shift $\beta$.

  • Batch norm stabilises training because each layer receives inputs with a consistent scale.
  • It needs $\gamma$ and $\beta$ because the network must still be able to choose any scale and offset.
  • Inference uses running statistics because predictions shouldn't depend on which examples share a batch.
$$\hat x_i = \frac{x_i - \mu_B}{\sqrt{\sigma_B^2 + \varepsilon}}, \quad y_i = \gamma \hat x_i + \beta, \qquad \mu_B = 4,\; \sigma_B^2 = 2.67 \Rightarrow \hat x = [-1.22, 0, 1.22]$$

Pitfall Using the test batch's own statistics at inference.

Feynman Explain Batch normalization to a beginner in 2 minutes: define it, give one example, name one limitation.

Early stopping

early stopping ends training when the validation loss has not improved for a set number of epochs (the patience) and keeps the weights from the best validation epoch.

  • The validation loss decides because it measures generalisation, unlike the training loss.
  • A rising validation loss signals overfitting because the model is fitting noise in the training set.
  • Patience tolerates noise because one bad epoch doesn't mean the trend has turned.
$$e^* = \arg\min_{e \le e_{\text{stop}}} L_{\text{val}}(e) = 5, \qquad e_{\text{stop}} = e^* + \text{patience} = 8$$

Pitfall Keeping the weights from the stopping epoch instead of the best epoch.

Feynman Explain Early stopping to a beginner in 2 minutes: define it, give one example, name one limitation.

Convolutional neural networks (CNN)

a convolutional neural network uses layers that slide small learned filters over the input, computing a weighted sum at each position, so the same weights detect a pattern anywhere in the image.

  • Convolution finds patterns anywhere because the same filter is applied at every position.
  • CNNs need few parameters because a filter's weights are shared across the whole image.
  • Padding preserves size because extra border pixels let the filter cover the edges.
$$\text{out} = \frac{W - F + 2P}{S} + 1 = \frac{32 - 5 + 4}{1} + 1 = 32, \qquad \#\text{params} = (F \cdot F \cdot C_{\text{in}} + 1) \cdot C_{\text{out}} = 1{,}216$$

Pitfall Forgetting the input channels when counting parameters (a 5 × 5 filter on RGB has 75 weights, not 25).

Feynman Explain Convolutional neural networks (CNN) to a beginner in 2 minutes: define it, give one example, name one limitation.

Pooling

pooling downsamples each feature map by summarising small windows, taking the maximum (max pooling) or the average (average pooling) of each.

  • Max pooling keeps the strongest response because it takes the maximum of each block.
  • It shrinks maps by 4× because a 2 × 2 window with stride 2 halves both height and width.
  • It adds shift tolerance because small moves inside a block don't change the maximum.
$$\text{out} = \frac{W - F}{S} + 1 = \frac{4 - 2}{2} + 1 = 2, \qquad \text{values kept} = \tfrac14 \text{ for } 2 \times 2,\; S = 2$$

Pitfall Saying pooling has learned weights.

Feynman Explain Pooling to a beginner in 2 minutes: define it, give one example, name one limitation.

Recurrent neural networks (RNN)

a recurrent neural network processes a sequence step by step, updating a hidden state $h_t = \tanh(W_{hh} h_{t-1} + W_{xh} x_t + b)$ with the same weights at every step.

  • An RNN handles sequences of any length because it applies the same cell at every step.
  • The hidden state carries memory because each new state depends on the previous one.
  • The same input can give different states because the state also depends on the past.
$$h_t = \tanh(W_{hh} h_{t-1} + W_{xh} x_t + b), \qquad \frac{\partial h_t}{\partial h_{t-1}} = W_{hh} \,(1 - h_t^2)$$

Pitfall Using different weights at each time step; an RNN shares them.

Feynman Explain Recurrent neural networks (RNN) to a beginner in 2 minutes: define it, give one example, name one limitation.

LSTM

an LSTM (long short-term memory) is a recurrent cell with a separate cell state updated additively under the control of forget, input and output gates, which lets it keep information over long sequences.

  • The cell state carries long-term memory because it changes only through gated multiplication and addition.
  • Gradients flow far back because $\partial c_t / \partial c_{t-1} = f$, which can stay near 1.
  • Gates use sigmoids because their outputs between 0 and 1 act like dimmer switches.
$$c_t = f \odot c_{t-1} + i \odot g = 0.731 \cdot 0.5 + 0.622 \cdot 0.664 \approx 0.779, \qquad h_t = o \odot \tanh(c_t) \approx 0.358$$

Pitfall Mixing up the cell state $c$ (long-term memory) and the hidden state $h$ (the output).

Feynman Explain LSTM to a beginner in 2 minutes: define it, give one example, name one limitation.

GRU

a GRU (gated recurrent unit) is a recurrent cell with an update gate that blends the old hidden state with a candidate, and a reset gate that controls how much of the past the candidate uses.

  • The update gate preserves memory because with $z$ near 0 the old state is copied forward.
  • The reset gate lets the cell start fresh because with $r$ near 0 the candidate ignores the past.
  • GRUs are lighter than LSTMs because they have three weight blocks instead of four and no cell state.
$$h_t = (1 - z)\, h_{t-1} + z\, \tilde h = 0.5 \cdot 0.5 + 0.5 \cdot 0.633 \approx 0.566$$

Pitfall Mixing up which gate builds the candidate (reset) and which blends (update).

Feynman Explain GRU to a beginner in 2 minutes: define it, give one example, name one limitation.

Attention (Q, K, V)

attention computes an output as a weighted average of value vectors, where the weights are the softmax of scaled dot products between a query and the keys: $\text{softmax}(QK^\top/\sqrt{d_k})V$.

  • Attention focuses on matching items because softmax turns higher query–key similarity into larger weights.
  • The output is a blend of values because it is their weighted average.
  • Scores are scaled by $\sqrt{d_k}$ because raw dot products grow with dimension and would saturate softmax.
$$\text{Attention}(Q, K, V) = \text{softmax}\!\left(\frac{QK^\top}{\sqrt{d_k}}\right)V, \qquad \text{cost } O(n^2 d), \text{ memory } O(n^2)$$

Pitfall Forgetting the $\sqrt{d_k}$ scaling.

Feynman Explain Attention (Q, K, V) to a beginner in 2 minutes: define it, give one example, name one limitation.

The Transformer

a Transformer is a stack of blocks, each made of multi-head self-attention and a position-wise feed-forward network with residual connections and layer normalization, applied to token embeddings plus positional encodings.

  • Transformers process tokens in parallel because attention compares all positions at once instead of stepping through them.
  • Positional encodings are needed because attention by itself ignores order.
  • Residual connections make depth trainable because each sub-layer only adds a refinement to its input.
$$\#\text{weights} = \underbrace{4 d^2}_{\text{attention}} + \underbrace{2 d\, d_{\text{ff}}}_{\text{FFN}} = 4 \cdot 512^2 + 2 \cdot 512 \cdot 2048 \approx 3.15\text{M}, \qquad \text{attention cost } O(n^2 d)$$

Pitfall Forgetting positional encodings, so word order is lost.

Feynman Explain The Transformer to a beginner in 2 minutes: define it, give one example, name one limitation.

Transfer learning

transfer learning reuses a model pretrained on a large dataset as the starting point for a new task, replacing and training its output layer (and optionally fine-tuning other layers).

  • Pretrained features transfer because early layers learn generic patterns like edges and textures.
  • Only the head is replaced because the final layer is specific to the original classes.
  • Freezing prevents overfitting because a small dataset then trains only a few thousand weights.
$$\#\text{head} = 512 \cdot 2 + 2 = 1{,}026, \qquad \frac{1{,}026}{\approx 11.2\text{M}} \approx 0.01\%$$

Pitfall Forgetting to freeze the backbone, so 2,000 images overwrite millions of good weights.

Feynman Explain Transfer learning to a beginner in 2 minutes: define it, give one example, name one limitation.

Autoencoder

an autoencoder is a network trained to reproduce its input through a smaller bottleneck code, made of an encoder $x \to z$ and a decoder $z \to \hat x$, using the reconstruction error as the loss.

  • The bottleneck forces compression because the code has fewer numbers than the input.
  • No labels are needed because the training target is the input itself.
  • Reconstruction error flags anomalies because inputs unlike the training data don't fit the learned code.
$$\min_{f,\, g} \; \frac1n \sum_{i} \lVert x_i - g(f(x_i)) \rVert^2, \qquad [1, 1, 0, 0] \to \hat x = [0.5, 0.5, 0.5, 0.5],\; \text{MSE} = 0.25$$

Pitfall Using a code as large as the input without other constraints, which lets the network learn the identity.

Feynman Explain Autoencoder to a beginner in 2 minutes: define it, give one example, name one limitation.

Generative adversarial networks (GAN)

a generative adversarial network trains a generator to produce samples that a discriminator, trained at the same time, cannot distinguish from real data.

  • GANs need no explicit quality measure because the discriminator learns to judge realism.
  • The two networks are adversaries because one's loss goes down when the other's goes up.
  • At equilibrium $D = 0.5$ because perfect fakes can't be told apart from real data.
$$\min_G \max_D \; \mathbb{E}[\ln D(x)] + \mathbb{E}[\ln(1 - D(G(z)))], \qquad L_D = 0.33,\; L_G = 1.61$$

Pitfall Updating the discriminator while training the generator (it must be held fixed in that step).

Feynman Explain Generative adversarial networks (GAN) to a beginner in 2 minutes: define it, give one example, name one limitation.

Variational autoencoder (VAE)

a variational autoencoder encodes each input as a probability distribution over codes, samples from it with the reparameterization trick, and trains with reconstruction error plus a KL penalty that keeps codes close to $\mathcal{N}(0, 1)$, which makes it a generative model.

  • The encoder outputs a distribution because that fills the code space instead of leaving isolated points.
  • The KL term keeps codes near $\mathcal{N}(0, 1)$ because random samples from $\mathcal{N}(0, 1)$ must decode to sensible data.
  • The reparameterization trick enables training because it moves the randomness into $\varepsilon$, outside the path of the gradients.
$$\underbrace{(1 - 0.8)^2 + (0 - 0.1)^2}_{0.05} + \underbrace{\tfrac12\big(0.64 + 0.25 - 1 - \ln 0.64\big)}_{\approx 0.168} \approx 0.218$$

Pitfall Sampling $z$ directly from $\mathcal{N}(\mu, \sigma^2)$ in code, which blocks gradients to $\mu$ and $\sigma$.

Feynman Explain Variational autoencoder (VAE) to a beginner in 2 minutes: define it, give one example, name one limitation.