Algorithm engineering

A repository of Python snippets for different algorithms.

See the appendix for source code for all of the algorithms.

Greedy

• Stable Matching
  • The Gale–Shapley algorithm for Stable Matching. The algorithm runs in linear time in the total size of preferences, or, $O(n^2)$ where $n$ is the number of "hospitals".

Graphs

• Bipartite Matching
  • Compute a maximum matching in an unweighted bipartite graph using DFS to find augmenting paths. Implements the classic alternating-path approach for bipartite matching.
• Dfs Tree
  • Run DFS and get a DFS tree
• Dijkstra
  • Simple Dijkstra implementation running in time $O(m \log n)$.
• Kahns Algorithm
  • Kahn's algorithm produces a topological order of a DAG by repeatedly removing vertices with zero in-degree and updating their neighbors' in-degrees until none remain.
• Kosarajus Algorithm
  • A strongly connected component (SCC) is a maximal set of vertices where every vertex can reach every other by directed paths. Kosaraju's algorithm finds all SCCs by doing a DFS to record finish times, reversing all edges, then running DFS again in reverse finish order.
• Rrt
  • Grow a rapidly-exploring random tree (RRT) toward a target while avoiding obstacles. Expands the tree incrementally by sampling feasible edges until the goal region is reached or iterations are exhausted.
• Topological Sort With Dfs
  • Use postorder DFS to get a reversed topological ordering.
• Union Find
  • Simple Union Find (with path compression) datastructure implementation for use in MST.

Sliding searching sorting

• Consecutive Sum
  • Maximum consecutive sum in an array with possibly negative values.
• Longest Nonnegative
  • Find the length of the longest contiguous subarray with a non-negative sum. Uses prefix sums and two-pointer scanning over forward minima and reverse maxima.
• Prefix Sum
  • Compute the prefix sum of a given list as input.
• Sliding Window
  • Sliding window to find best $k$ sized window in linear time.

Dynamic programming

• Bellman Ford
  • Single-source shortest paths (SSSP) with negative edges can be solved by Bellman–Ford, which uses dynamic programming over path lengths to relax edges up to $n-1$ times. If a further relaxation still decreases a distance, it indicates a negative-weight cycle reachable from the source.
• Dominating Set On Trees
  • Weighted Dominating Set on Trees. Dynamic Programming.
• Edit Distance
  • Compute the edit distance (Levenshtein distance) with dynamic programming. With applications in spell checking.
• Feedback Arc Set
  • Exact $2^n$ algorithm for Feedback Arc Set (with memoization).
• Floyd-warshall

  • APSP (All-Pairs Shortest Paths) is the problem of finding the shortest path distances between every pair of vertices in a weighted graph.

    Floyd–Warshall is a classic dynamic programming algorithm for APSP.

    By updating dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for each intermediate vertex k, it computes shortest paths for all pairs in $O(n^3)$ time.

• Independent Set On Trees
  • Weighted Independent Set on trees.
• Knapsack 01
  • 0-1-Knapsack dynamic programming.
• Knapsack Wr
  • Knapsack with repetitions. Dynamic Programming.
• Line Breaking
  • Use DP to minimize the raggedness of a paragraph of text.
• Linear Regression Queries
  • Given a set of $n$ $(x, y)$ points, compute the least squares for the data set. In addition, create a data structure that can answer query least_squares(i, j) of all points in data[i:j]. Using dynamic programming we can compute the entire data structure in time $O(n^2)$.
• Longest Path Dag
  • Longest Path in a DAG. Dynamic programming.
• Subset Sum
  • Dynamic programming routine (recursion with memoization) for Subset Sum.

Segment trees

• Segment Tree
  • Basic implementation of a segment tree.
• Sqrt Decomposition

  • Basic implementation for SQRT decomposition. The SQRT data structure can answer range queries such as sum, max, min in time $O(\sqrt n)$ and can do update element in $O(\sqrt n)$ as well.

    In theory, this data structure can take any associative operation (e.g., gcd, lcm), and the elements can even be higher order structures such as matrices with the operation being matrix multiplication. Indeed, you can take elements over $\text{GL}_n(\mathbb{C})$, and answer such queries.

Divide and conquer

• Fast Fourier Transform
  • Fast Fourier Transform using divide and conquer in time $O(n \log n)$.

Geometry

• Bentley Ottmann
  • Find all intersection points among a set of line segments using a simplified Bentley–Ottmann sweep. Maintains an active list of segments and schedules intersection checks through an event queue.
• Closest Pair
  • A divide and conquer algorithm for computing a closest pair of points in a set of $n$ points in the plane in time $O(n \log n)$. It outputs both their distance and the pair itself.
• Faces
  • Compute the faces of a planar graph.
• Graham Scan
  • The Graham scan algorithm for computing the convex hull of a set of $n$ points in the plane. It runs in time $O(n \log n)$, which is optimal.
• Jarvis March
  • The Jarvis march (gift wrapping) algorithm for computing the convex hull of a set of $n$ points in $O(n \cdot h)$ time where $h$ is the number of points on the hull.
• Library
  • Some Geometry functions
• Shoelace Formula
  • The Shoelace algorithm for computing the area of a polygon.

Exptime

• Coloring
  • Graph coloring.
• Permute
  • Enumerate all permutations of a list
• Travelling Salesman
  • Travelling Salesman dynamic programming routine.

Flow

• Edmonds Karp
  • The Edmonds–Karp variant of the Ford–Fulkerson algorithm for computing maximum flow.

Strings

• Hashing
  • Rolling hash.
• Knuth Morris Pratt
  • Knuth–Morris–Pratt (KMP) algorithm for pattern matching.
• Trie
  • A basic implementation of a trie.

Math

• Gcd
  • Extended Euclidean algorithm: compute the coefficients of Bézout's identity, i.e., $ax + by = \gcd(a, b)$.
• Primes
  • Factorize a number into prime factors.
• Sieve
  • The Sieve of Eratosthenes — an ancient algorithm for finding all prime numbers up to any given limit.