| Random Link ¯\_(ツ)_/¯ | ||
| Dec 14, 2025 | » | Shortest Paths in a Graph
8 min; updated Dec 14, 2025
A shortest path from vertex \(s\) to vertex \(t\) in an edge-weighted digraph is a directed path from \(s\) to \(t\) with the property that no other path has a lower weight. A shortest-paths tree for a source \(s\) is a subgraph containing \(s\) and all the vertices reachable from \(s\) that forms a directed tree rooted at \(s\) such that every tree path is a shortest path in the digraph.... |
| Nov 7, 2021 | » | Bloom Filters
5 min; updated Sep 5, 2022
Bloom Filters In true fashion to Stigler’s Law of Eponymy (no scientific discovery is named after its original discoverer ), Ross Ashby (1960) did a probabilistic analysis of Calvin Mooers’s Zatocoding (1947) (coding system for library cards). This predates Burton Bloom’s work (1970). Motivation A Bloom filter for a set \(X: \{x_1, x_2, …, x_n\} \) from some universe \(\mathbb{U}\) allows one to test whether a given item \(x \in \mathbb{B}\) is an element of \(X\).... |