❄️Competitive Programming

🐬 Base

Properties2
title🐬 Base
modified—

4 min read

CONTENT

Branches

Named Algorithms

  • Kadane’s Algorithm
  • Dutch National Flag Algorithm
  • Moore’s Voting Algorithm
  • Floyd’s Cycle Detection
  • Brent’s Cycle Detection
  • Dijkstra’s Algorithm
  • Bellman–Ford Algorithm
  • Floyd–Warshall Algorithm
  • Johnson’s Algorithm
  • Prim’s Algorithm
  • Kruskal’s Algorithm
  • BorĹŻvka’s Algorithm
  • Kosaraju’s Algorithm
  • Tarjan’s Algorithm
  • Kahn’s Algorithm / Topological Sort
  • Hierholzer’s Algorithm
  • Edmonds–Karp Algorithm
  • Ford–Fulkerson Algorithm
  • Dinic’s Algorithm
  • Push–Relabel Algorithm
  • Hopcroft–Karp Algorithm
  • Hungarian Algorithm
  • Kuhn’s Algorithm
  • Edmonds’ Blossom Algorithm
  • Chu–Liu/Edmonds’ Algorithm
  • Stoer–Wagner Algorithm
  • Gomory–Hu Algorithm
  • Karp’s Minimum Mean Cycle Algorithm
  • Mo’s Algorithm
  • Karger’s Algorithm
  • Tarjan’s Offline LCA
  • Schieber–Vishkin Algorithm
  • Graham Scan
  • Andrew’s Monotone Chain Algorithm
  • Rabin–Karp Algorithm
  • Knuth–Morris–Pratt (KMP) Algorithm
  • Z Algorithm
  • Boyer–Moore Algorithm
  • Aho–Corasick Algorithm
  • Manacher’s Algorithm
  • Booth’s Algorithm
  • Duval’s Algorithm
  • Huffman Coding
  • Morris Traversal
  • Sieve of Eratosthenes
  • Euclidean Algorithm
  • Extended Euclidean Algorithm
  • Miller–Rabin Primality Test
  • Pollard’s Rho Algorithm
  • Tonelli–Shanks Algorithm
  • Chinese Remainder Theorem
  • Garner’s Algorithm
  • Lucas Theorem
  • Berlekamp–Massey Algorithm
  • Kitamasa Algorithm
  • Bostan–Mori Algorithm
  • Fast Fourier Transform (FFT)
  • Number Theoretic Transform (NTT)
  • Fast Walsh–Hadamard Transform (FWHT)
  • Gaussian Elimination
  • Gauss–Jordan Elimination
  • Matrix Exponentiation
  • Kirchhoff’s Theorem
  • Matrix Tree Theorem
  • Fortune’s Algorithm
  • Bentley–Ottmann Algorithm
  • Welzl’s Algorithm
  • A* Algorithm
  • Minimax Algorithm
  • Alpha–Beta Pruning
  • Sprague–Grundy Theorem
  • Simulated Annealing
OUTLINE

Number Theory

  • Binary Exponentiation
  • Euclidean Algorithm
  • Extended Euclidean Algorithm
  • Linear Diophantine Equations
  • Modular Arithmetic
  • Modular Inverse
  • Linear Congruence
  • Chinese Remainder Theorem
  • Garner’s Algorithm
  • Prime Numbers
  • Sieve of Eratosthenes
  • Linear Sieve
  • Segmented Sieve
  • Euler Totient Function
  • Mobius Function
  • Divisor Functions
  • Primality Testing
  • Integer Factorization
  • Pollard Rho
  • Miller Rabin
  • Primitive Root
  • Discrete Logarithm
  • Discrete Root
  • Lucas Theorem
  • Wilson’s Theorem
  • Factorial Modulo p
  • Montgomery Multiplication
  • Barrett Reduction
  • Legendre Symbol
  • Quadratic Residues
  • Quadratic Reciprocity
  • Pell’s Equation
  • Fibonacci Numbers
  • Matrix Exponentiation
  • Linear Recurrence
  • Berlekamp Massey
  • Gray Code
  • Balanced Ternary

Bit Manipulation

  • Bit Operations
  • Brian Kernighan Algorithm
  • Enumerating Submasks
  • Enumerating Supermasks
  • Subset DP
  • SOS DP
  • Bitset Optimization
  • Builtin Bit Functions
  • XOR Basis

Data Structures

  • Stack
  • Queue
  • Deque
  • Priority Queue
  • Minimum Stack
  • Minimum Queue
  • Monotonic Stack
  • Monotonic Queue
  • Prefix Sum
  • Difference Array
  • Sparse Table
  • Fenwick Tree
  • Segment Tree
  • Lazy Segment Tree
  • Persistent Segment Tree
  • Dynamic Segment Tree
  • Merge Sort Tree
  • Wavelet Tree
  • Treap
  • Splay Tree
  • AVL Tree
  • Red Black Tree
  • Disjoint Set Union
  • Rollback DSU
  • DSU on Tree
  • Sqrt Decomposition
  • Mo’s Algorithm
  • Mo’s Algorithm with Updates
  • Sqrt Tree
  • Randomized Heap
  • Li Chao Tree
  • Order Statistic Tree
  • Policy Based Data Structures
  • Trie
  • Binary Trie

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
  • Knuth Optimization
  • Convex Hull Trick
  • Li Chao Tree
  • Monotone Queue Optimization
  • Alien Trick
  • Slope Trick

String Algorithms

  • Prefix Function
  • Knuth Morris Pratt
  • Z Function
  • Rabin Karp
  • String Hashing
  • Suffix Array
  • Suffix Automaton
  • Suffix Tree
  • Aho Corasick
  • Trie
  • Patricia Trie
  • Manacher Algorithm
  • Lyndon Factorization
  • Duval Algorithm
  • Booth Algorithm
  • Rolling Hash
  • Polynomial Hashing

Mathematics

  • Matrix
  • Matrix Exponentiation
  • Gaussian Elimination
  • Determinant
  • Rank
  • Linear Basis
  • XOR Basis
  • Fast Walsh Hadamard Transform

Numerical Methods

  • Binary Search
  • Ternary Search
  • Newton Method
  • Simulated Annealing
  • 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
  • Convex Hull Trick
  • Minkowski Sum
  • Rotating Calipers
  • Point in Convex Polygon
  • Polygon Area
  • Pick Theorem
  • Closest Pair of Points
  • Half Plane Intersection
  • Sweep Line
  • Voronoi Diagram
  • Delaunay Triangulation
  • 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
  • Condensation Graph
  • Biconnected Components
  • Dijkstra
  • Bellman Ford
  • SPFA
  • 0-1 BFS
  • Dial Algorithm
  • Floyd Warshall
  • Johnson Algorithm
  • Lowest Common Ancestor
  • Binary Lifting
  • Euler Tour
  • Heavy Light Decomposition
  • Centroid Decomposition
  • Virtual Tree
  • Tree Isomorphism
  • Tree Hashing
  • Prim
  • Kruskal
  • Boruvka
  • Second Best MST
  • Eulerian Path
  • Hamiltonian Path
  • Negative Cycle
  • Ford Fulkerson
  • Edmonds Karp
  • Dinic
  • Push Relabel
  • Minimum Cost Flow
  • Circulation with Demands
  • Stoer Wagner Minimum Cut
  • Bipartite Matching
  • Kuhn Algorithm
  • Hopcroft Karp
  • Hungarian Algorithm
  • Blossom Algorithm
  • 2-SAT
  • Strong Orientation
  • Dominator Tree
  • Kirchhoff Theorem
  • Prufer Code
  • Euler Tour Tree
  • Dynamic Connectivity

Graph View

Recent notes