❄️Algopedia

🐬 Base

Properties2
title🐬 Base
modified—

6 min read

BRANCHES
NAMED ALGORITHMS
  • A* Algorithm
  • Aho-Corasick Algorithm
  • Ahuja-Orlin Algorithm
  • AKS Primality Test
  • Algorithm X
  • Alpha-Beta Pruning
  • Andrew’s Monotone Chain Algorithm
  • Apostolico-Giancarlo Algorithm
  • Bareiss Algorithm
  • Bellman-Ford Algorithm
  • Bellman-Held-Karp Algorithm
  • Bentley-Ottmann Algorithm
  • Bentley-Shamos Algorithm
  • Berlekamp-Massey Algorithm
  • Berlekamp Factorization Algorithm
  • Bitap Algorithm
  • Bluestein’s Algorithm
  • Booth’s Algorithm
  • BorĹŻvka’s Algorithm
  • Bostan-Mori Algorithm
  • Bowyer-Watson Algorithm
  • Boyer-Moore Algorithm
  • Boyer-Myrvold Planarity Algorithm
  • Brent’s Cycle Detection
  • Bron-Kerbosch Algorithm
  • Cantor-Zassenhaus Algorithm
  • Chan’s Algorithm
  • Chazelle’s MST Algorithm
  • Chinese Remainder Theorem
  • Christofides Algorithm
  • Chu-Liu/Edmonds’ Algorithm
  • Cipolla’s Algorithm
  • Commentz-Walter Algorithm
  • Cooley-Tukey FFT
  • Cornacchia’s Algorithm
  • Crochemore Algorithm
  • Dancing Links
  • DC3 (Skew) Algorithm
  • Dijkstra’s Algorithm
  • Dinic’s Algorithm
  • Dobkin-Kirkpatrick Hierarchy
  • Dreyfus-Wagner Algorithm
  • Dutch National Flag Algorithm
  • Duval’s Algorithm
  • Edmonds’ Blossom Algorithm
  • Edmonds-Karp Algorithm
  • Eppstein’s Algorithm
  • Euclidean Algorithm
  • Extended Euclidean Algorithm
  • Faddeev-LeVerrier Algorithm
  • Farach’s Suffix Tree Algorithm
  • Farach-Colton-Bender RMQ/LCA
  • Fast Fourier Transform (FFT)
  • Fast Walsh-Hadamard Transform (FWHT)
  • Floyd’s Cycle Detection
  • Floyd-Warshall Algorithm
  • Ford-Fulkerson Algorithm
  • Fortune’s Algorithm
  • Frederickson’s MST Algorithm
  • FĂźrer’s Algorithm
  • Gabow’s SCC Algorithm
  • Gabow-Edmonds Scaling Algorithm
  • Gabow-Tarjan Algorithm
  • Galil-Seiferas Algorithm
  • Garner’s Algorithm
  • Gaussian Elimination
  • Goemans-Williamson Algorithm
  • Goldberg-Tarjan Scaling Algorithm
  • Gomory-Hu Algorithm
  • Good-Thomas Algorithm
  • Graham Scan
  • Han’s Integer Sorting Algorithm
  • Harel-Tarjan LCA Algorithm
  • Held-Karp Algorithm
  • Hensel Lifting
  • Hierholzer’s Algorithm
  • Hirschberg Algorithm
  • Holm-de Lichtenberg-Thorup Dynamic Connectivity
  • Hopcroft-Karp Algorithm
  • Hopcroft-Tarjan Planarity Algorithm
  • Gauss-Jordan Elimination
  • Hu-Tucker Algorithm
  • Huffman Coding
  • Hungarian Algorithm
  • Johnson’s Algorithm
  • Kadane’s Algorithm
  • Kahn’s Algorithm
  • Karatsuba Algorithm
  • Karger’s Algorithm
  • Karger-Stein Algorithm
  • Karmarkar-Karp Algorithm
  • Karp’s Minimum Mean Cycle Algorithm
  • Karzanov Algorithm
  • Kasai Algorithm
  • Kirchhoff’s Theorem
  • Kirkpatrick-Seidel Algorithm
  • Kitamasa Algorithm
  • KMR Algorithm
  • Knuth-Morris-Pratt (KMP) Algorithm
  • Knuth Optimization
  • Kosaraju’s Algorithm
  • Kruskal’s Algorithm
  • Kuhn’s Algorithm
  • Lanczos Algorithm
  • Lawler’s Algorithm
  • Lengauer-Tarjan Algorithm
  • Lenstra ECM
  • Lucas Theorem
  • Lucas-Lehmer Test
  • Manacher’s Algorithm
  • Matrix Exponentiation
  • Matrix Tree Theorem
  • McCreight’s Algorithm
  • Mehlhorn’s LCA Algorithm
  • Melkman’s Algorithm
  • Micali-Vazirani Algorithm
  • Miller-Rabin Primality Test
  • Minimax Algorithm
  • Mo’s Algorithm
  • Monte Carlo Tree Search
  • Montgomery Reduction
  • Moore’s Voting Algorithm
  • Morris Traversal
  • MPM Algorithm
  • Nagamochi-Ibaraki Algorithm
  • Negascout
  • Newton-Schulz Iteration
  • Number Theoretic Transform (NTT)
  • Orlin’s Maximum Flow Algorithm
  • Pettie-Ramachandran MST Algorithm
  • Pohlig-Hellman Algorithm
  • Pollard Kangaroo Algorithm
  • Pollard’s Rho Algorithm
  • Prim’s Algorithm
  • Proof-Number Search
  • Push-Relabel Algorithm
  • Quadratic Sieve
  • Rabin-Karp Algorithm
  • Rader’s Algorithm
  • Raghavan-Thompson Randomized Rounding
  • Reif’s Minimum Cut Algorithm
  • SA-IS Algorithm
  • Schieber-Vishkin Algorithm
  • SchĂśnhage-Strassen Algorithm
  • Seidel’s LP Algorithm
  • Shamos-Hoey Algorithm
  • Shift-Or Algorithm
  • Sieve of Eratosthenes
  • Simulated Annealing
  • Sleator-Tarjan Dynamic Trees
  • SMAWK Algorithm
  • Sprague-Grundy Theorem
  • Stoer-Wagner Algorithm
  • Suurballe’s Algorithm
  • Tarjan’s Algorithm
  • Tarjan’s Offline LCA
  • Tarjan-Vishkin Algorithm
  • Tonelli-Shanks Algorithm
  • Toom-Cook Algorithm
  • UCT (Upper Confidence Trees)
  • Ukkonen’s Algorithm
  • Viterbi Algorithm
  • Weiner’s Algorithm
  • Welzl’s Algorithm
  • Wiedemann Algorithm
  • Wu-Manber Algorithm
  • Yao Optimization
  • Yen’s Algorithm
  • Z Algorithm
DATA STRUCTURES
  • 2D Fenwick Tree
  • 2D Segment Tree
  • AVL Tree
  • B‑Tree / B+ Tree
  • Binary Heap
  • Binary Trie
  • Binomial Heap
  • Bitset
  • Bitset‑based structures
  • Bounding Volume Hierarchy (BVH)
  • Brodal Queue
  • Cartesian Tree
  • Centroid Decomposition
  • DAWG
  • Deque
  • Difference Array
  • Disjoint Set Union (DSU)
  • Disjoint Sparse Table
  • Dynamic Segment Tree
  • Dynamic Tree structures
  • Eertree / Palindromic Tree
  • Euler Tour Tree
  • Euler tour based tree structures
  • Fenwick Tree (BIT)
  • Fenwick Tree on bitsets
  • Fibonacci Heap
  • Fusion Tree
  • Heap / Priority Queue
  • Heavy‑Light Decomposition (HLD)
  • Hollow Heap
  • Implicit Treap
  • Interval Stabbing structures
  • Interval Tree
  • KD‑Tree
  • Lazy Segment Tree
  • Leftist Heap
  • Li Chao Tree
  • Linear Basis / XOR Basis
  • Link‑Cut Tree
  • Meldable Heap
  • Merge Sort Tree
  • Minimum Queue
  • Minimum Stack
  • Monotonic Queue
  • Monotonic Stack
  • Octree
  • Ordered Set / Order Statistics Tree
  • Pairing Heap
  • Patricia Trie / Compressed Trie
  • Persistent DSU
  • Persistent Fenwick Tree
  • Persistent Segment Tree
  • Persistent Trie
  • Policy Based Data Structures
  • Prefix Sum
  • Quad Tree
  • Queue
  • R‑Tree
  • Randomized Heap
  • Range Tree
  • Red‑Black Tree
  • Rollback DSU
  • Rope / Rope Tree
  • Scapegoat Tree
  • Segment Tree
  • Segment Tree Beats
  • Segment tree for geometry sweeps
  • Skew Heap
  • Soft Heap
  • Sparse Table
  • Splay Tree
  • Square Root Decomposition
  • Stack
  • Suffix Array
  • Suffix Automaton
  • Suffix Tree
  • Suffix Trie
  • Tango Tree
  • Top Tree
  • Treap
  • Trie
  • van Emde Boas Tree
  • Versioned data structures
  • Virtual Tree
  • Wavelet Matrix
  • Wavelet Tree
  • X‑fast Trie
  • Y‑fast Trie
OUTLINE

Number Theory

  • Binary Exponentiation
  • Linear Diophantine Equations
  • Modular Arithmetic
  • Modular Inverse
  • Linear Congruence
  • Euler Totient Function
  • MĂśbius Function
  • Divisor Functions
  • Primality Testing
  • Integer Factorization
  • Primitive Root
  • Discrete Logarithm
  • Discrete Root
  • Wilson’s Theorem
  • Factorial Modulo p
  • Legendre Symbol
  • Quadratic Residues
  • Quadratic Reciprocity
  • Pell’s Equation
  • Fibonacci Numbers
  • Linear Recurrence
  • Gray Code
  • Balanced Ternary

Bit Manipulation

  • Bit Operations
  • Enumerating Submasks
  • Enumerating Supermasks
  • Subset DP
  • SOS DP
  • Bitset Optimization
  • Builtin Bit Functions

Data Structures

  • Prefix Sum
  • Difference Array
  • Sqrt Decomposition (as a technique)
  • DSU on Tree (as a technique)

Dynamic Programming

  • Introduction to Dynamic Programming
  • Memoization
  • Tabulation
  • State Compression DP
  • Bitmask DP
  • Digit DP
  • Tree DP
  • Rerooting DP
  • Interval DP
  • Probability DP
  • DP on DAG
  • Profile DP
  • Knapsack
  • Longest Increasing Subsequence
  • Longest Common Subsequence
  • Edit Distance
  • Divide and Conquer DP
  • Convex Hull Trick (as a technique)
  • Monotone Queue Optimization (as a technique)
  • Alien Trick
  • Slope Trick

String Algorithms

  • Prefix Function
  • Z Function
  • String Hashing
  • Rolling Hash
  • Polynomial Hashing
  • Suffix Array (as a technique - construction algorithms are in Named)
  • Suffix Automaton (as a concept)
  • Suffix Tree (as a concept)

Mathematics

  • Matrix
  • Determinant
  • Rank
  • Linear Basis (as a concept)
  • XOR Basis (as a concept)

Numerical Methods

  • Binary Search
  • Ternary Search
  • Newton Method
  • Golden Section Search
  • Binary Search on Answer
  • Coordinate Compression

Geometry

  • Geometry Basics
  • Vectors
  • Dot Product
  • Cross Product
  • Line Intersection
  • Segment Intersection
  • Circle Line Intersection
  • Circle Circle Intersection
  • Tangents
  • Distance Between Points
  • Orientation Test
  • Convex Hull (as a concept)
  • Minkowski Sum
  • Rotating Calipers (as a technique)
  • Point in Convex Polygon
  • Polygon Area
  • Pick’s Theorem
  • Closest Pair of Points
  • Half Plane Intersection
  • Sweep Line (as a technique)
  • Voronoi Diagram (concept)
  • Delaunay Triangulation (concept)
  • Minimum Enclosing Circle
  • Manhattan Geometry

Graph Theory

  • Breadth First Search
  • Depth First Search
  • Topological Sort
  • Connected Components
  • Bridges
  • Articulation Points
  • Bridge Tree
  • Strongly Connected Components (concept)
  • Condensation Graph
  • Biconnected Components
  • SPFA
  • 0‑1 BFS
  • Dial Algorithm
  • Lowest Common Ancestor (concept)
  • Binary Lifting (technique)
  • Euler Tour
  • Heavy‑Light Decomposition (technique)
  • Centroid Decomposition (technique)
  • Virtual Tree (technique)
  • Tree Isomorphism
  • Tree Hashing
  • Second Best MST
  • Eulerian Path (concept)
  • Hamiltonian Path (concept)
  • Negative Cycle (detection)
  • Minimum Cost Flow (concept)
  • Circulation with Demands
  • Bipartite Matching (concept)
  • 2‑SAT
  • Strong Orientation
  • Dominator Tree (concept)
  • PrĂźfer Code
  • Euler Tour Tree (concept)
  • Dynamic Connectivity (concept)

Game Theory

  • Combinatorial Games
  • Nim
  • Grundy Numbers (SG values)
  • Minimax (as a concept)
  • Alpha-Beta Pruning (as a concept)

Scheduling

  • Job Scheduling
  • Interval Scheduling
  • Greedy Scheduling
  • Deadline Scheduling

Polynomial / Algebra

  • Polynomial Arithmetic
  • Convolution (concept)
  • FFT / NTT (concept)
  • Formal Power Series

Randomized / Approximation

  • Randomized Algorithms (concept)
  • Las Vegas vs Monte Carlo
  • Approximation Algorithms (concept)

Exact / NP‑Hard

  • Backtracking
  • Branch and Bound
  • Meet‑in‑the‑Middle
  • Exact Cover (concept)

Graph View

Recent notes