Making Computer Science easier to understand.

Explanations in this animation:

Floyd's Cycle Detection

Floyd's cycle detection, run on a seven node list whose last node points back to the fourth. Two pointers start at the head; the slow one advances one node per round and the fast one advances two. Round by round the gap closes until both land on the same node, which is the proof that the list contains a loop. A list that simply ended would instead run the fast pointer off the end.

Recursion

The Tower of Hanoi with four discs, solved recursively in 15 moves. To move four discs from A to C, the three above the biggest are moved to B, the biggest crosses to C on its own, and the three are moved from B onto it — and each of those three-disc moves is the same problem stated again with a smaller number. The base case is a stack of zero discs, which needs no moves at all. Every extra disc doubles the work, so n discs take 2^n - 1 moves.

Backtracking

The four-queens problem solved by backtracking, in 31 decisions. Rows are filled from the top, taking the first column no earlier queen attacks along a column or a diagonal. When a row has no safe column left, the search does the thing that makes it backtracking rather than plain recursion: it lifts the previous queen back off the board and tries the next column for it instead. That happens three times here, once all the way back to the first row, before the columns 1, 3, 0, 2 are found to work.

Merge Sort

Merge sort on seven values, drawn as the recursion it is. The array is split in half, each half is split again, and the splitting stops when a piece holds a single value, which is sorted by definition. The pieces then come back up: two sorted runs are merged by comparing their front values and taking the smaller, which is where the ordering is actually created. Nothing sorts on the way down and nothing is compared until the way back up. Each level of the tree walks past every value once, and halving the array down to single values takes log n levels, so the sort costs n log n on every input there is.

Binary Search

Binary search over the sorted array 4, 11, 17, 23, 31, 42, 56, 68, 79, looking for 23. Each step checks the middle value of the range still in play and discards the half that cannot contain the target. The range shrinks from 9 values to 9, then 4, then 2, then 1, and 23 is found at index 3 after 4 comparisons. Because every step halves what is left, the work grows with the logarithm of the input rather than with the input itself.