jeffe.cs.illinois.edu

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....

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\)....

Bloom Filters;