Approximation Algorithm Probabilistic / Approximate Counting [Complete Overview] We have introduced and explored the idea of Probabilistic algorithms in depth with the different algorithms like Morris Algorithm, HyperLogLog, LogLog and others in this domain.
Data Structures Cuckoo filter [Explained] A cuckoo filter is a probabilistic data structure that is used to test whether an element is a member of a set or not. It is similar to the Bloom filter.
Data Structures LogLog (Probabilistic Data Structure for Cardinality) LogLog is a Probabilistic Data Structure that uses the idea of hashing to compute Cardinality of a given set.
Data Structures MinHash (Probabilistic Data Structure for Similarity) MinHash was originally an algorithm to quickly estimate the jaccard similarity between two sets but can be designed as a probabilistic data structure that quickly estimates how similar two sets are.
Data Structures Probabilistic Data Structures This is a general overview of probabilistic data structures (with examples of data structures over 5 different categories).
Algorithms Fermat's little theorem, a Probabilistic test for Primality One of the most popular probabilistic algorithm for determining if a number is prime or not is based on Fermat's little theorem. The complexity of the algorithm is O(K log N) and fails only for Carmichael numbers which are composite numbers satisfying fermat little theorem starting with 561