afentev/Algorithms-and-Data-structures

Some implementations of interesting algorithms and data structures that I studied.

Algorithms and Data structures

Following stuff is already implemented:

Math algorithms

• Long arithmetic (cp-algorithms)

Prime numbers and factorization

• Sieve of Eratosthenes (wiki)
• Sieve of Eratosthenes with linear complexity (aka Euler's sieve) (wiki)
• Pollard's rho algorithm (wiki)

Sorting algorithms

• Radix sort (wiki)
• Merge sort (wiki)
• Quick sort (wiki)
• Insertion sort (wiki)
• Selection sort (wiki)
• Bubble sort (wiki)

Other algorithms related to sortings

• Quickselect (selection algorithm) (wiki)
• Quickselect with O(n) worst-case complexity. Uses Median of medians (wiki)

Heaps

• Binary heap (wiki)
• Binomial heap (wiki)
• Pairing heap (wiki)
• Leftist heap (wiki)
• Skew heap (wiki)

Search Trees

• van Emde Boas tree (wiki)
• Splay Tree (wiki)
• AVL Tree (wiki)
• B-tree (wiki)
• Skip list (wiki)
• X-fast trie (wiki)
• Y-fast trie (wiki)

Data Structures for RMQ and similar problems

• Segment tree (wiki)
• Segment tree with lazy propagation (cp-algorithms)
• Bottom-up Segment tree (aka ZKW Segment tree) (codeforces)
• Fenwick tree (wiki)
• Sparse table (cp-algorithms)
• Sparse table with binary lifting (peltorator)
• Disjoint Sparse Table (codechef)
• Sqrt decomposition (cp-algorithms)
• Farach-Colton and Bender Algorithm (peltorator)

Algorithms on graphs

• Topological sort (wiki)
• Counting the number of triangles in a graph (cs.stanford.edu)

Shortest paths

• Floyd-Warshall algorithm (wiki)
• Dijkstra's algorithm (wiki)
• Bellman-Ford algorithm (wiki)
• Shortest Path Faster Algorithm (wiki)
• Pallottino's algorithm (neerc.ifmo)
• Levit's algorithm (aka Pape-Levit's or D'Esopo-Pape) (cp-algorithms)
• 0-1 BFS (cp-algorithms)
• 1-k BFS (lksh)
• Dial's algorithm (1-k BFS) (codeforces)

Algorithms and Data structures for trees

• Heavy-light decomposition (cp-algorithms)
• Prim's algorithm (wiki)
• Kruskal's algorithm (wiki)

Least common ancestor (LCA) and Level ancestor problem (LA)

• Solving LCA via RMQ
• Binary Lifting for LCA (cp-algorithms)
• Binary Lifting for LA (wiki)
• Longest Path Decomposition (LA) (wiki)
• Ladder Decomposition (LA) (wiki)
• Ladder Decomposition and Binary Lifting combined (wiki)
• The Macro-Micro-Tree Algorithm (mit.edu)
• Farach-Colton and Bender Algorithm (cp-algorithms)
• Tarjan's offline LCA algorithm (wiki)
• Schieber-Vishkin algorithm (neerc.ifmo)

Algorithms on strings

• Rabin-Karp algorithm (wiki)

Other data structures

• Disjoint set union (Union find) (cp-algorithms)
• Persistent stack
• Queue with minimum
• Hashed array tree (wiki)
• Dynamic array with Θ(1) push_back complexity (no O(n) worst-case)

Other algorithms

• Longest increasing subsequence (wiki)
• Longest common subsequence (wiki)