A collection by Michael Casagranda

Magic Book of Algorithms

A notebook about algorithms: briefly explained, written in readable C# and shown with an example that really ran.

Algorithms: 19
Groups: 9
Language: C# / .NET 10

SRT

Sorting

Bringing data into order. The classic playground for understanding running time.

SRT-01

Bubble Sort

Swap neighbours until everything is where it belongs.

O(n²) SRT-02

Merge Sort

Halve until nothing is left to do, then merge everything back in order.

O(n log n) SRT-03

Quick Sort

One value becomes the divider, everything smaller moves to its left.

O(n log n)

SRC

Searching

Finding something specific without looking at everything.

SRC-01

Binary Search

Every step halves the search range, turning a million entries into twenty comparisons.

O(log n)

PTH

Pathfinding

Finding the cheapest way from here to there when not every step costs the same.

PTH-01

Dijkstra

The cheapest way, found without the faintest idea where the goal lies.

O((E + V) log V) PTH-02

A*

Dijkstra with a hunch: the same way for a fraction of the work.

O((E + V) log V)

MTH

Mathematics

Number sequences and calculations that show up in surprisingly many programs.

MTH-01

Fibonacci Sequence

Every number is the sum of the two before it, and suddenly the golden ratio appears.

O(n)

STA

Statistics

What many numbers tell together, even when the single number says nothing.

STA-01

Benford's Law

Real numbers start with a 1 far more often than one would think. People who make them up do not know that.

O(n)

RND

Randomness & Noise

Calculated randomness: reproducible, fast and the basis of procedurally generated worlds.

RND-01

PCG (Random Numbers)

A random generator in a handful of lines: fast, evenly spread and reproducible at any time.

O(1) RND-02

Perlin Noise

Raw randomness turns into smooth noise, the raw material for landscapes, clouds and textures.

O(n · o) RND-03

Worley Noise

Scatter points, measure distances — and out come cells, scales and cracked ground.

O(pixels)

PRC

Procedural generation

Building worlds, maps and patterns from rules instead of by hand.

PRC-01

Wave Function Collapse

Deciding tile after tile until only one possibility is left.

≈ O(cells · tiles²) PRC-02

Reaction-Diffusion

Two substances, two rules, two numbers — and out of them corals, stripes and leopard spots.

O(cells · steps)

CMP

Compression

Storing the same information in less space.

CMP-01

Run-Length Encoding (RLE)

Instead of storing W twelve times, simply remember: twelve times W.

O(n)

IMG

Image processing

Turning pixels into something else: filtering, converting, redrawing.

IMG-01

Weighted Voronoi Stippling

A picture made of nothing but dots: dense where it is dark, sparse where it is light.

O(pixels · dots · rounds) IMG-02

Dithering

Few colours that look like many from a distance.

O(pixels) IMG-03

Edge Detection

Sobel, Prewitt, Laplace and Canny: four answers to where something in a picture begins.

O(pixels · kernel) IMG-04

Bloom

Bright things spill over their edges — a flaw of optics, rebuilt in three lines.

O(pixels · radius) IMG-05

Marching Squares

A field of numbers turns into a line: sixteen cases, and no more than that.

O(cells)