E-Maxx Algorithms in English

The goal of this project is to translate at least some pages of the wonderful resource http://e-maxx.ru/algo which provides descriptions of many special algorithms especially popular in field of competitive programming.

Articles

Algebra

• Euler's totient function
• Number of divisors / sum of divisors
• Euclidean algorithm for computing the greatest common divisor
• Sieve of Eratosthenes
• Extended Euclidean Algorithm
• Binary Exponentiation
• Balanced Ternary
• Linear Diophantine Equations
• Linear Congruence Equation
• Modular Inverse
• Chinese Remainder Theorem
• Primitive Root
• Discrete Root
• Discrete Log
• Enumerating submasks of a bitmask
• Gray code
• Sieve of Eratosthenes Having Linear Time Complexity
• Arbitrary-Precision Arithmetic
• Fibonacci Numbers
• Finding Power of Factorial Divisor
• Fast Fourier transform

Data Structures

• Disjoint Set Union
• Fenwick Tree
• Sparse Table
• Segment Tree
• Treap
• Sqrt Decomposition
• Sqrt Tree
• Minimum Stack / Minimum Queue
• Randomized Heap

Dynamic Programming

• Dynamic Programming on Broken Profile. Problem "Parquet"

String Processing

• String Hashing
• Rabin-Karp for String Matching
• Expression parsing
• Suffix Array
• Suffix Tree
• Suffix Automaton
• Z-function
• Prefix function
• Finding all sub-palindromes in O(N)
• Lyndon factorization
• Aho-Corasick algorithm
• Finding repetitions

Linear Algebra

• Gauss & System of Linear Equations
• Gauss & Determinant
• Kraut & Determinant

Combinatorics

• The Inclusion-Exclusion Principle
• Binomial Coefficients
• Catalan Numbers
• Placing Bishops on a Chessboard
• Balanced bracket sequences
• Counting labeled graphs
• Burnside's lemma / Pólya enumeration theorem
• Stars and bars
• Generating all $K$-combinations

Game Theory

• Games on arbitrary graphs

Numerical Methods

• Ternary Search
• Newton's method for finding roots

Geometry

• Basic Geometry
• Length of the union of intervals on a line in O(N*logN)
• Oriented area of a triangle and predicate "clockwise"
• Intersection Point of Lines
• Circle-Line Intersection
• Circle-Circle Intersection
• Pick's Theorem - area of lattice polygons
• Lattice points of non-lattice polygon
• Area of simple polygon
• Convex hull trick and Li Chao tree
• Convex hull construction using Graham's Scan

Graphs

• Breadth First Search
• Depth First Search
• Bipartite Graph Check
• Topological Sorting
• Finding Bridges in O(N+M)
• Finding Bridges Online
• Finding Articulation Points in O(N+M)
• Checking a graph for acyclicity and finding a cycle in O(M)
• Finding a Negative Cycle in the Graph
• Floyd-Warshall - finding all shortest paths
• Number of paths of fixed length / Shortest paths of fixed length
• Dijkstra - finding shortest paths from given vertex
• Dijkstra on sparse graphs
• Bellman-Ford - finding shortest paths with negative weights
• D´Esopo-Pape algorithm
• Finding Connected Components
• Lowest Common Ancestor
• Lowest Common Ancestor - Binary Lifting
• Lowest Common Ancestor - Farach-Colton and Bender algorithm
• Solve RMQ by finding LCA
• Lowest Common Ancestor - Tarjan's off-line algorithm
• Minimum Spanning Tree - Prim's Algorithm
• Minimum Spanning Tree - Kruskal
• Minimum Spanning Tree - Kruskal with Disjoint Set Union
• Prüfer code
• Kirchhoff Theorem
• Strongly Connected Components and Condensation Graph
• Maximum flow - Ford-Fulkerson and Edmonds-Karp
• Maximum flow - Push-relabel algorithm
• Maximum flow - Push-relabel algorithm improved
• Flows with demands
• Minimum-cost flow
• Edge connectivity / Vertex connectivity
• 2-SAT

Sequences

• RMQ task (Range Minimum Query - the smallest element in an interval)
• Longest increasing subsequence
• K-th order statistic in O(N)

Schedules

• Scheduling jobs on one machine
• Scheduling jobs on two machines
• Optimal schedule of jobs given their deadlines and durations

Miscellaneous

• 15 Puzzle Game: Existence Of The Solution

---

Information for contributors and Test-Your-Page form