Algorithms and Data Structures
Search this site
Data Structures and Algorithms in Java
2-satisfiability
_How to solve algorithmic problem (draft)
Aho-Corasick algorithm
Aho-Corasick simple
Binary heap
Binary heap with increase priority operation
Binary Search
Binary Search Tree
Binomial coefficients and factorials
Bron–Kerbosch algorithm for maximum independent set
Delaunay triangulation and Voronoi diagram in O(N*sqrt(N)) (with demo)
Delaunay triangulation in O(N^4) (with demo)
Determinant of a matrix by Gauss and Crout algorithms in O(N^3)
DFS: Biconnected components, bridges and cut points
DFS: Eulerian cycle
DFS: Strongly connected components. Kosaraju's algorithm
DFS: Strongly connected components. Tarjan's algorithm
DFS: Topological sorting
Disjoint-set data structure
Doubly Linked list
Drawing of connected graph with Force-Based method
Dynamic programming: Convex Hull Optimization
Dynamic programming: domino fill
Dynamic programming: edit distance in O(N^2)
Dynamic programming: longest common subsequence in O(N^2)
Dynamic programming: longest increasing subsequence in O(N^2)
Dynamic programming: number of perfect matchings
Dynamic programming: number of solutions of linear equality
Dynamic programming: optimal matrix chain multiplication in O(N^3)
Enumeration of arrangements
Enumeration of partitions
Enumeration of permutations
Euclidean algorithm. GCD, LCM, modular inverse, Chinese remainder theorem
Expression parser: Shunting-yard algorithm
Factorization in O(sqrt(N))
Fenwick tree 2D for sum
Fenwick tree for sum and max
Fenwick tree for sum with extended operations
Gaussian elimination algorithm in O(N^3)
Geometry: Circle
Geometry: Class Complex
Geometry: Line
Graph
Greedy graph coloring in O(E * logV)
Hashing on strings
Heavy-light tree decomposition for vertices or edges
Hill Climbing
Hungarian algorithm for assignment problem
Kd-tree for nearest neightbour query in O(logN) on average
Kd-tree for rectangular query in O(sqrt(N))
Kth order statistic in O(N) on average
LCA. Lowest common ancestor on tree in O(logN)
LCA: Sparse Table
LinkCut tree - dynamic tree connectivity
LinkCut tree - dynamic tree lca
LinkCut tree - dynamic tree with path queries
Longest increasing subsequence in O(N * logN)
Matrices
Max Rectangle
Maximum flow of minimum cost in O(V^3*FLOW)
Maximum flow of minimum cost with Bellman–Ford in O(min(E^2*V^2, E*V*FLOW))
Maximum flow of minimum cost with potentials in O(min(E^2*V*logV, E*logV*FLOW))
Maximum flow. Dinic's algorithm in O(V^2 * E)
Maximum flow. Edmonds-Karp algorithm in O(min( E^2*V, E*FLOW ))
Maximum flow. Ford-Fulkerson alogithm in O(V^2 * FLOW)
Maximum flow. Push–relabel algorithm in O(V^3)
Maximum matching for bipartite graph. Kuhn's algorithm in O(E*V)
Maximum matching for bipartite graph. Kuhn's algorithm in O(V^3)
Maximum matching for general graph. Edmonds' algorithm in O(V^3)
Maximum matching for general graph. Randomized algorithm inO(V^3)
Meet in the middle
Mergeable heap. A heap with merge, add, removeMin operation in O(logN)
Minimum spanning tree. Prim's algorithm in O(E * logV)
Minimum spanning tree. Prim's algorithm in O(V^2)
Mo's algorithm (sqrt-decomposition for answering queries)
Pair (std::pair analog)
Persistent Tree
Prefix tree (Trie)
Prime numbers, sieve of Eratosthenes, Euler's totient function
Quadtree for rectangular queries in O(min(n, N+M))
Queue with minimum query in O(1)
Random permutations and arrangements
Random tree and graph generation. Prüfer code
Rational numbers class
RMQ: Sparse Table
Searching substring in O(N). Knuth–Morris–Pratt algorithm + prefix function
Segment Tree 2D without recursion with single addition for maximum
Segment Tree with interval modification
Segment Tree with interval modification without recursion
Segment Tree. Simple implementation
Shortest Hamiltonian cycle (TSP) in O(2^N * N^2)
Shortest Hamiltonian path in O(2^N * N^2)
Shortest paths. Bellman–Ford algorithm in O(V*E). Negative cycle detection.
Shortest paths. Dijkstra's algorithm in O(E * logV)
Shortest paths. Floyd–Warshall algorithm in O(V^3)
Simplex algorithm
Sorting algorithms: qsort, merge, bubble, selection, insertion, counting, radix
Suffix Array in O(N * logN) and LCP in O(N)
Suffix Array in O(N * logN^2)
Suffix automaton
Suffix tree. Ukkonen's algorithm in O(N * alphabetSize)
Travelling salesman problem: genetic algorithm (with demo)
Travelling salesman problem: simulated annealing (with demo)
Treap as a set with kth-element operation
Treap with implicit key with interval modification
Tree Centers
Classic problems
Longest palindromic subsequence
Data Structures and Algorithms in C++
Arbitrary-precision arithmetic
Binary exponentiation algorithm
C++ comparators
Class Scanner for fast input
Diametr of a planar point set in O(N * logN) with rotating calipers method
Disjoint-set data structure with rank heuristic
Fenwick tree for sum
Fenwick tree for sum on Map
Geometry convex hull: Graham-Andrew algorithm in O(N * logN)
Geometry: finding a pair of intersected segments in O(N * logN)
Kd-tree for nearest neightbour query in O(logN) on average
Laguerre's method of polynom roots finding
Matrices
Maximum flow of minimum cost in O(min(E^2*V*logV, E*logV*FLOW))
Maximum flow. Dinic's algorithm in O(V^2 * E)
Maximum matching for bipartite graph. Hopcroft-Karp algorithm in O(E * sqrt(V))
Minimum spanning tree. Prim's algorithm in O(E * logV)
Segment Tree with interval modification
Shortest paths. Dijkstra's algorithm with binary heap in O(E * logV)
Shortest paths. Dijkstra's algorithm with priority_queue or set in O(E * logV)
Sieve of Eratosthenes in O(N*loglogN)
SSE Instructions
Suffix Array and LCP in O(N). Algorithm DC3
Treap with implicit key with interval modification
Tree isomorphism
Sitemap
Recent site activity
Data Structures and Algorithms in Java
edited by Andrey Naumenko
Aho-Corasick algorithm
edited by Andrey Naumenko
2-satisfiability
edited by Andrey Naumenko
_How to solve algorithmic problem (draft)
edited by Andrey Naumenko
Mo's algorithm (sqrt-decomposition for answering queries)
edited by Andrey Naumenko
View All
Classic problems
Subpages
(1):
Longest palindromic subsequence
Comments