Princeton Algorithms, Part I & Part II

Every core algorithm, animated, in Python

The two Princeton courses cover roughly fifty algorithms and data structures. Below is all of them, in lecture order. Pick one: you get the implementation, a picture that moves one step at a time, the invariant that keeps it correct, and the running-time claim it is famous for. Nothing here is a recording — the animation is generated by running the algorithm on whatever input you give it.

Part I — data types, sorting, searching

Part II — graphs, strings, compression

Undirected graphsweek 1

Depth-first searchMark a vertex, then recur into any unmarked neighbour. Breadth-first searchSwap the recursion for a queue and vertices come off in order of distance. Connected componentsRun DFS from each vertex no earlier search reached.

Directed graphsweek 2

Directed cycle detectionAn edge to a vertex still on the recursion stack closes a cycle. Topological sortAdd each vertex to a list only after everything it points to is finished, then reverse the list. Strong components (Kosaraju–Sharir)Reverse the digraph, take its reverse postorder, then DFS the original in that order.

Minimum spanning treesweek 3

Kruskal's MSTSort the edges and take them in order, skipping any that would create a cycle. Prim's MST (lazy)Keep one growing tree and always add the cheapest edge leaving it.

Shortest pathsweek 4

Dijkstra's algorithmRepeatedly settle the unsettled vertex closest to the source and relax its edges. Shortest paths in a DAGIn an acyclic digraph, relax vertices in topological order and one pass is enough. Bellman–FordRelax every edge, V−1 times. Slower than Dijkstra, but it handles negative weights and reports a negative cycle instead…

Maximum flowweek 4

Ford–Fulkerson (max-flow)Push flow along any path with spare capacity, allowing yourself to cancel earlier flow.

Radix sortsweek 5

Key-indexed countingCount how many keys have each value, turn the counts into starting positions, then place every key directly where it… LSD radix sortSort by the last character, then the one before it, and so on. MSD radix sortSort on the first character, then recur inside each group.

Triesweek 5

R-way trieStore nothing in the nodes but branch on one character per level.

Substring searchweek 6

Brute-force substring searchTry every alignment, comparing left to right. Simple and usually fine — but it re-reads text it has already seen, which… Knuth–Morris–PrattPrecompute, for every state and character, where a mismatch leaves you. Boyer–MooreCompare the pattern right to left. A mismatched text character that does not occur in the pattern at all lets you skip… Rabin–KarpHash the pattern once, then hash every window of the text — each in constant time from the previous one.

Data compressionweek 7

Run-length encodingReplace each run of identical symbols by the symbol and its length. Huffman compressionMerge the two least frequent symbols, repeatedly. LZW compressionEmit the code for the longest known phrase, then learn that phrase plus one more character.

Every core algorithm, animated, in Python

Part I — data types, sorting, searching

Union–Findweek 1

Analysis of algorithmsweek 1

Stacks and queuesweek 2

Elementary sortsweek 2

Sorting applicationsweek 2

Mergesortweek 3

Quicksortweek 3

Priority queuesweek 4

Binary search treesweek 4

Balanced search treesweek 5

Hash tablesweek 6

Part II — graphs, strings, compression

Undirected graphsweek 1

Directed graphsweek 2

Minimum spanning treesweek 3

Shortest pathsweek 4

Maximum flowweek 4

Radix sortsweek 5

Triesweek 5

Substring searchweek 6

Data compressionweek 7

Visualization

Input edit it, then Animate

Python

Why it works

Every core algorithm, animated, in Python

Part I — data types, sorting, searching

Union–Findweek 1

Analysis of algorithmsweek 1

Stacks and queuesweek 2

Elementary sortsweek 2

Sorting applicationsweek 2

Mergesortweek 3

Quicksortweek 3

Priority queuesweek 4

Binary search treesweek 4

Balanced search treesweek 5

Hash tablesweek 6

Part II — graphs, strings, compression

Undirected graphsweek 1

Directed graphsweek 2

Minimum spanning treesweek 3

Shortest pathsweek 4

Maximum flowweek 4

Radix sortsweek 5

Triesweek 5

Substring searchweek 6

Data compressionweek 7

Visualization

Input edit it, then Animate

Python Open in Visualizer

Why it works

Python