Latest / Deep End Era. Engineering with Sankalp
The Cheapest Skeleton: Minimum Spanning Trees and Union-Find
A rural broadband cooperative in Wales must connect forty farms and three villages with fibre for the least money. The mathematics it needs was first worked out in 1926, when a power company in Moravia asked a young mathematician in Brno how to electrify the countryside cheaply. Part nine of The Deep End's algorithms series explains minimum spanning trees: why three different greedy algorithms all find the same optimal answer, and the tiny union-find structure that makes one of them nearly free. We follow spanning trees into office networks, where Radia Perlman's protocol stops broadcast…
The skinny
The skinny isn't ready yet — notes appear once the transcript is processed.