The algorithms catalogue

SRT Algorithm Binary search Finds the “no → yes” boundary in ordered data in log₂ n checks. O(log n) 2 problems SRT Technique Binary search on the answer If checking an answer is easier than finding it, and the check is monotone, search for the answer by halving. O(log D · cost of a check) 2 problems SRT Algorithm Counting sort and radix sort Without comparisons: count the keys or split them into digits, O(n + k) and O(d·n) instead of n log n. O(n + k) and O(d·(n + b)) 2 problems

DS Data structure Dynamic array An array that grows by itself: access by index in O(1), appending to the end in O(1) amortised. O(1) amortised per append 2 problems DS Data structure Cuckoo hashing Two nests per key, a lookup in at most two probes; insertion evicts tenants. Works up to a load of 1/2, with buckets up to 98 %. lookup at most d probes in the worst case; insertion O(1) on average below the threshold 1 problem DS Data structure Bloom filter Says “surely not” or “maybe yes” about set membership, at about 10 bits per item. O(k) 2 problems DS Data structure Binary heap The minimum at hand, insertion and extraction in O(log n): the tree in an array that event calendars live on. O(log n) 2 problems DS Data structure Binary search tree Smaller to the left, larger to the right: search, order and the k-th element in the tree's height, from log n to n. O(h): from O(log n) to O(n) 2 problems DS Data structure AVL tree A search tree where the branch heights at a node differ by at most 1: height up to ~1.44·log₂ n. O(log n) for search, insertion and deletion 2 problems DS Data structure B-tree A tree with hundreds of keys in a page-sized node: a search among a billion keys reads five pages. O(log n) comparisons, O(log_B n) page reads 2 problems DS Data structure Disjoint set union Merge two sets and tell whether elements are in the same one, in almost O(1): a forest of parent links and two tricks. O(α(n)) 2 problems

GRA Algorithm Breadth-first search Walks a graph in layers and finds paths with the fewest edges in O(V + E). O(V + E) 2 problems GRA Algorithm Depth-first search Goes deep, marks each vertex's entry and exit and finds cycles by them in O(V + E). O(V + E) 2 problems GRA Algorithm Bridges and articulation points Streets and crossroads without which a graph falls apart: one depth-first search with the numbers tin and low, O(V + E). O(V + E) 2 problems GRA Algorithm Dijkstra's algorithm Shortest paths from one vertex in a weighted graph without negative edges. O((V + E) log V) 3 problems GRA Algorithm A* Dijkstra with a hint of how far is left: the wave stretches towards the goal, and the path stays shortest. O((V + E) log V) 2 problems GRA Algorithm Bidirectional search Two Dijkstra waves towards each other: where to stop, how much is saved, and how to make it work with A*. O((V + E) log V) 2 problems GRA Algorithm The Bellman–Ford algorithm Shortest paths with negative edges and finding a negative cycle: V rounds over all edges. O(V · E) 2 problems GRA Algorithm Contraction hierarchies A navigator's precomputation: contract unimportant crossroads into shortcuts and find the path with two waves going up. O((V + E′) log V) 1 problem GRA Algorithm Dinic's algorithm Maximum flow in phases: a layered network, a blocking flow, pointers; O(V²E), and O(E√V) in unit networks. O(V² E) 2 problems GRA Algorithm Bipartite matching The largest number of pairs in a bipartite graph: Kuhn, Hopcroft–Karp, the theorems of König and Hall. O(E √V) 2 problems GRA Algorithm Centroid decomposition Splitting a tree by centroids: log₂ n levels, and the nearest marked vertex in O(log n) after every mark. O(log n) per mark and per question 1 problem

STR Algorithm The Aho–Corasick algorithm Every occurrence of thousands of words in one pass: a trie of the words plus failure links, as in the prefix function. O(n + Σ|wᵢ| + z) 1 problem STR Algorithm Boyer–Moore Compares from right to left and skips letters: on long patterns it reads only a small part of the text. O(n + m) 2 problems STR Algorithm The Burrows–Wheeler transform A permutation that compresses a text and serves as an index to it: backward search, LF, and read alignment. O(m) to count a pattern, O(m + k·s) for k positions 2 problems STR Algorithm Edit distance The fewest insertions, deletions and substitutions between two strings: an m × n table and the alignment read from it. O(m · n) 2 problems STR Data structure BK-tree All passwords one or two edits from a given one: the triangle inequality cuts off whole branches, and where it stops helping. O(N · depth) to build 1 problem

DP Technique Dynamic programming Reduce a problem to subproblems, solve each once and keep the answers in a table. states × transitions 2 problems DP Technique Bitmask DP The state is a subset written in the bits of a number: an exact travelling salesman, assignments, tilings by profile. O(2ⁿ · n²) for the travelling salesman 2 problems DP Technique Digit DP Lucky tickets in any range in one pass over the digits: 55,252 out of a million, and any range up to 10¹⁸, in about a millisecond. O(D · 10 · S) 2 problems DP Technique Convex hull trick A minimum of lines instead of a search: 1776 catalogue tests split into sandbox runs, and a quadratic DP becomes linear. O(n) 2 problems DP Technique Knuth and divide-and-conquer optimisations 45 thousand towns on a map by population class: 3.5 million evaluations instead of five billion, because the best split is monotone. O(k · n log n) 2 problems

PAR Technique Backtracking Build a solution step by step, check at once and retreat from dead ends: sudoku, queens, colourings. O(bᵈ) in the worst case 2 problems PAR Technique Branch and bound 38 airports with a direct flight from each to each: a colouring bound shrinks the search from a million nodes to 242. exponential in the worst case 1 problem PAR Technique Divide and conquer Cut, solve the parts the same way, glue; what it costs follows from the levels of the recursion tree and the master theorem. T(n) = a·T(n/b) + f(n) 2 problems PAR Algorithm Closest pair of points The two nearest of n points in n log n: a cut, a strip 2d wide and seven neighbours; with a grid, n on average. O(n log n) 2 problems

NUM Algorithm Chinese remainder theorem A number from its residues modulo several moduli: Garner's algorithm and exact computation over many primes. O(k²) operations on machine numbers 2 problems NUM Algorithm Big integers Numbers longer than a machine word: digits in base 10⁹ or 2³⁰, carries, column methods and expensive printing. addition O(n), column multiplication and division O(n²), printing in decimal O(n²) or O(M(n) log n) 2 problems

GEO Algorithm Convex hull The smallest convex polygon containing all the points, in O(n log n). O(n log n) 2 problems GEO Algorithm Delaunay triangulation and Voronoi diagram Zones of the nearest point and triangles with empty circles: two sides of one structure. O(n log n) on average 2 problems

NUM~ Algorithm Bisection and Newton's method A root of an equation: halving an interval is reliable, Newton's tangents are fast. bisection: log₂((b − a)/ε) steps; Newton: about log₂ of the number of digits 2 problems

SYS Algorithm Consistent hashing Spreads keys over servers so that adding a server moves only its share. O(log(N·v)) to find a server 1 problem SYS Data structure Count-Min Sketch Frequencies of stream items in fixed memory: the minimum of d counters, with an error only upwards. O(d) per item and per query 2 problems SYS Technique Retry with jitter The pause before a retry doubles and is chosen at random: clients spread out in time and do not hit the server in waves. O(1) per pause decision 2 problems SYS Data structure CRDT Data whose copies are edited independently and merged in any order: counters, sets, text. O(1) per operation for a counter and a set; insertion into text O(1) on average 2 problems

ML Algorithm k-means Splits points into k groups so that points sit close to the centre of their group. O(n · k · d) per step 2 problems ML Algorithm DBSCAN Gathers dense regions of points of any shape into clusters and marks lone points as noise. O(n·Q + Σ|N(p)|) 2 problems ML Algorithm Decision tree Answers with a chain of questions “feature ≤ threshold?”; each question is chosen so that uncertainty falls the most. O(h · F · n log n) to build; O(h) to answer 2 problems ML Algorithm Perceptron and backpropagation Draw a digit: a perceptron from 1958 and a network with a hidden layer, both trained right in the page in a second, read it. perceptron: O(d) per example; network gradient: O(number of weights) per example 1 problem