| Random Link ¯\_(ツ)_/¯ | ||
| Jun 15, 2019 | » | [ToDo] Algorithms by Jeff Erickson
1 min; updated Sep 5, 2022
Introduction; Recursion; Backtracking; Dynamic Programming; Greedy Algorithms; Basic Graph Algorithms; Depth-First Search; Minimum Spanning Trees; Shortest Paths; All-Pairs Shortest Paths; Maximum Flows & Minimum Cuts; Applications of Flows and Cuts; NP-Hardness. Fast Fourier Transforms; Fast Exponential Algorithms; Dynamic Programming for Formal Languages and Automata; Advanced Dynamic Programming; Matroids; Balances and Pseudoflows; Minimum-Cost Flows; Linear Programming; Linear Programming Algorithms; Approximation Algorithms. Discrete Probability; Nuts and Bolts; Treaps and Skip Lists; Tail Inequalities; Hashing; Filtering and Streaming; String Matching; Randomized Minimum Cut; Amortized Analysis; Scapegoat and Splay Trees; Disjoint Sets; Lower Bounds; Adversary Arguments; Proof by Induction; Solving Recurrences.... |
| 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\).... |
| Nov 7, 2021 | » | 'Monte Carlo' Algorithms and Data Structures
(1 items)
Bloom Filters; |