Algorithms

My library of competitive-programming algorithms, with C++ implementations and Python ports based on the same techniques.

Each algorithm has its own directory containing:

• README.md: algorithm, solution approach, complexity, usage, and C++ review notes.
• <Algorithm>.cpp: C++ implementation.
• <Algorithm>.py: Python implementation.
• test_<Algorithm>.py and test_<Algorithm>.cpp: reference checks and regression tests.

Algorithms

Directory	Algorithm
BellmanFord	Bellman–Ford shortest paths and negative cycles
BFS	Breadth-first search
BigNumbers	Unsigned big integers
BinSearch	Binary search on a predicate
Bridges	Bridges and articulation points
DFS	Depth-first search
Dijkstra	Dijkstra's shortest paths
FindAndUnion	Disjoint-set union
GCD	GCD and extended Euclid
Hashing	Double polynomial hashing
Heap	Binary min and max heaps
KMP	Knuth-Morris-Pratt prefix function
KMR	Karp-Miller-Rosenberg ranks and suffix arrays
Knapsack	Zero-one knapsack
Kruskal	Kruskal's minimum spanning forest
LCA	Lowest common ancestor
LIS	Longest increasing subsequence
Manacher	Manacher's palindrome radii
MergeSort	Merge sort
Mo	Mo's algorithm for distinct counts
Modulo	Modular arithmetic
MonoQueue	Monotone maximum queue
QuickSort	Quicksort
SCC	Strongly connected components (Kosaraju)
Sieve	Linear sieve and smallest prime factors
SparseTable	Static range minimum sparse table
TopologicalSort	Topological sort with cycle detection
TreePointSegment	Point assignment / range maximum
TreeSegmentPoint	Range addition / point lookup
TreeSegmentSegment	Range addition / range sum
Trie	Trie / prefix tree
ZeroOneBFS	0–1 BFS shortest paths

Running tests

Python 3.10+ and the standard library are sufficient; no third-party packages are required. Run from the repository root:

python3 run_tests.py
python3 run_tests.py --cpp

The second command also requires g++ with C++17 support. It compiles all C++ implementations independently and runs all C++ tests with UndefinedBehaviorSanitizer, placing build products in a temporary directory. Python tests use deterministic randomized inputs and simple reference solutions where appropriate.

With Nix, obtain the tools without a global installation:

nix shell nixpkgs#python3 nixpkgs#gcc --command python3 run_tests.py --cpp

To run only one Python suite:

python3 -m unittest discover -s QuickSort -t . -p 'test_*.py'

Conventions

Python graph vertices and array positions are zero-based. Range queries are inclusive for Mo and segment trees; string hash and KMR ranges are half-open. Each README explains the equivalent C++ indexing and initialization. The newer TopologicalSort, SCC, ZeroOneBFS, BellmanFord, and Bridges snippets also use zero-based C++ vertices and dynamic storage. SparseTable uses zero-based inclusive bounds in both languages. Algorithms expect inputs satisfying their documented assumptions.

C++ files retain their original competitive-programming interfaces and fixed-capacity arrays where applicable. Files with a demo/input main can be compiled as programs; other files are reusable snippets. C++ regressions include each snippet in its own translation unit to avoid collisions between global names.

Correctness fixes cover quicksort pivot placement, duplicate union sizes, LCA parent traversal, knapsack input/output, Mo query input and interval movement, substring hashing/comparison, and consistent segment-tree semantics. DFS, LCA, and quicksort avoid unbounded call-stack depth. See individual READMEs for details.