The following outline is provided as an overview of and topical guide to algorithms:
An algorithm is a finite, well-defined sequence of instructions or rules for solving a problem or performing a computation. Algorithms are central to computer science, mathematics, operations research, artificial intelligence, cryptography, data compression, computer graphics, bioinformatics, and many other fields. The study of algorithms includes their design, proof of correctness, efficiency, computational complexity, and implementation in computer programs.
Nature of algorithms Algorithm — finite sequence of instructions for solving a problem or performing a computation Computer program — implementation of algorithms and data-processing instructions in a programming language Data structure — organization of data used by algorithms Heuristic — practical problem-solving method that may not guarantee an optimal solution Pseudocode — informal notation for describing algorithms Specification — formal or informal statement of what an algorithm is intended to do State — stored information used during a computation Termination analysis — study of whether an algorithm eventually halts Turing machine — mathematical model of computation used in computability theory
History of algorithms
Euclidean algorithm — ancient algorithm for computing the greatest common divisor Muhammad ibn Musa al-Khwarizmi — mathematician whose Latinized name is associated with the word algorithm Algorithmic logic — logic-based study of programs and algorithms Computability theory — study of what can be computed Church–Turing thesis — thesis concerning the nature of effective computation Turing machine — model formalizing computation Lambda calculus — formal system used in the study of computation Von Neumann architecture — computer architecture influencing practical algorithm implementation
Algorithm analysis
Analysis of algorithms — study of the correctness and efficiency of algorithms Asymptotic analysis — analysis of algorithm behavior as input size grows Big O notation — upper-bound notation for growth rates Big Omega notation — lower-bound notation for growth rates Big Theta notation — tight-bound notation for growth rates Time complexity — amount of time an algorithm uses as input size changes Space complexity — amount of memory an algorithm uses as input size changes Best, worst and average case — common forms of algorithm-performance analysis Amortized analysis — analysis of average cost over a sequence of operations Competitive analysis (online algorithm) — analysis of online algorithms compared with optimal offline algorithms Correctness (computer science) — property that an algorithm satisfies its specification Loop invariant — condition used to prove correctness of iterative algorithms Recurrence relation — equation often used to analyze recursive algorithms Master theorem (analysis of algorithms) — theorem for solving many divide-and-conquer recurrences
Algorithm design paradigms
Brute-force search — method of exhaustively checking candidate solutions Divide-and-conquer algorithm — technique that divides a problem into smaller subproblems Decrease and conquer — technique that reduces a problem to a smaller instance Dynamic programming — technique for solving problems with overlapping subproblems and optimal substructure Greedy algorithm — algorithm that makes locally optimal choices Backtracking — search technique that abandons partial solutions that cannot lead to valid solutions Branch and bound — search technique using bounds to eliminate candidate solutions Randomized algorithm — algorithm using randomness as part of its logic Approximation algorithm — algorithm that finds near-optimal solutions for hard optimization problems Online algorithm — algorithm that receives input incrementally Parallel algorithm — algorithm designed for parallel computation Distributed algorithm — algorithm designed for distributed systems Streaming algorithm — algorithm for processing data streams with limited memory Quantum algorithm — algorithm designed for quantum computers
Data structures and related algorithms
Arrays, lists, and sequences Array (data structure) Linked list Dynamic array Stack (abstract data type) Queue (abstract data type) Deque Priority queue Circular buffer
Trees Tree (data structure) Binary tree Binary search tree AVL tree Red–black tree B-tree B+ tree Trie Segment tree Fenwick tree Heap (data structure)
Hashing and sets Hash table Hash function Bloom filter Disjoint-set data structure Union–find algorithm Locality-sensitive hashing
Graph data structures Graph (abstract data type) Adjacency list Adjacency matrix Incidence matrix
Operating system and memory-management algorithms
Scheduling algorithms Round-robin scheduling Shortest job next Rate-monotonic scheduling Earliest deadline first scheduling Page replacement algorithm Least recently used Cache replacement policies
Searching algorithms
Linear search Binary search algorithm Interpolation search Exponential search Jump search Depth-first search Breadth-first search Best-first search Beam search A* search algorithm Dijkstra's algorithm Iterative deepening depth-first search Monte Carlo tree search
Sorting and order statistics
Comparison sorting Bubble sort Insertion sort Selection sort Merge sort Quicksort Heapsort Timsort Introsort Shellsort Tree sort
Non-comparison sorting Counting sort Radix sort Bucket sort Pigeonhole sort
Order statistics Selection algorithm Quickselect Median of medians Order statistic tree
Graph algorithms
Graph traversal Depth-first search Breadth-first search Topological sorting Flood fill
Shortest paths Dijkstra's algorithm Bellman–Ford algorithm Floyd–Warshall algorithm Johnson's algorithm A* search algorithm
Spanning trees and connectivity Minimum spanning tree Kruskal's algorithm Prim's algorithm Borůvka's algorithm Connected component (graph theory) Strongly connected component Tarjan's strongly connected components algorithm
Network flow and matching Maximum flow problem Ford–Fulkerson algorithm Edmonds–Karp algorithm Push–relabel maximum flow algorithm Minimum-cost flow problem Bipartite matching Hopcroft–Karp algorithm Blossom algorithm
Graph coloring and hard graph problems Graph coloring Clique problem Independent set (graph theory) Hamiltonian path problem Travelling salesman problem
String algorithms
String-searching algorithm Knuth–Morris–Pratt algorithm Boyer–Moore string-search algorithm Rabin–Karp algorithm Aho–Corasick algorithm Levenshtein distance Edit distance Longest common subsequence Longest common substring Suffix tree Suffix array Burrows–Wheeler transform Regular expression Parsing Earley parser CYK algorithm
Numerical and mathematical algorithms
Arithmetic and number theory Euclidean algorithm Extended Euclidean algorithm Sieve of Eratosthenes Integer factorization Primality test AKS primality test Modular exponentiation Fast Fourier transform Karatsuba algorithm Schönhage–Strassen algorithm
Linear algebra Gaussian elimination LU decomposition QR decomposition Singular value decomposition Eigenvalue algorithm Strassen algorithm Matrix chain multiplication
Numerical optimization and approximation Newton's method Gradient descent Conjugate gradient method Simulated annealing Expectation–maximization algorithm Numerical integration Monte Carlo method
Optimization algorithms
Linear programming Simplex algorithm Interior-point method Integer programming Dynamic programming Gradient descent Stochastic gradient descent Newton's method Quasi-Newton method Broyden–Fletcher–Goldfarb–Shanno algorithm Lagrange multiplier Constraint satisfaction problem Local search (optimization) Hill climbing Tabu search Genetic algorithm Ant colony optimization algorithms Particle swarm optimization Evolutionary algorithm
Artificial intelligence and machine learning algorithms
Search and planning A* search algorithm Minimax Alpha–beta pruning Graphplan Monte Carlo tree search Automated planning and scheduling Constraint satisfaction problem
Supervised learning Linear regression Logistic regression Decision tree learning Random forest Support vector machine k-nearest neighbors algorithm Naive Bayes classifier Gradient boosting Artificial neural network Backpropagation
Unsupervised learning Cluster analysis K-means clustering Hierarchical clustering Principal component analysis Independent component analysis Autoencoder Self-organizing map
Reinforcement learning Reinforcement learning Q-learning State–action–reward–state–action (SARSA) Temporal difference learning Policy gradient method Actor–critic algorithm Deep reinforcement learning
Algorithmic gameplay AlphaGo AlphaGo Zero AlphaZero MuZero TD-Gammon Chinook (draughts player) Deep Blue (chess computer)
AI-assisted algorithm discovery AlphaDev AlphaEvolve AlphaTensor Neural architecture search Automated machine learning Program synthesis
Cryptographic algorithms
Symmetric-key algorithms Advanced Encryption Standard Data Encryption Standard Triple DES Blowfish (cipher) Twofish ChaCha20-Poly1305
Public-key algorithms RSA cryptosystem Diffie–Hellman key exchange Elliptic-curve cryptography Digital Signature Algorithm EdDSA
Hashing and authentication Cryptographic hash function MD5 SHA-1 SHA-2 SHA-3 Hash-based message authentication code Password-based key derivation function Bcrypt Argon2
Compression algorithms
Lossless compression Huffman coding Arithmetic coding Run-length encoding Lempel–Ziv–Welch LZ77 and LZ78 DEFLATE Burrows–Wheeler transform
Lossy compression techniques Transform coding Discrete cosine transform Modified discrete cosine transform Vector quantization Quantization Motion compensation
Computational geometry algorithms
Convex hull algorithms Graham scan Gift wrapping algorithm Delaunay triangulation Voronoi diagram Line segment intersection Point location Closest pair of points problem Rotating calipers Sweep line algorithm
Computer graphics and image-processing algorithms
Bresenham's line algorithm Flood fill Scanline rendering Z-buffering Ray casting Ray tracing (graphics) Path tracing Phong shading Texture mapping Bump mapping Normal mapping Marching cubes Canny edge detector Random sample consensus (RANSAC) Scale-invariant feature transform Hough transform Seam carving
Database and information retrieval algorithms
B-tree B+ tree Hash join Sort-merge join Query optimization PageRank Inverted index Tf–idf BM25 Locality-sensitive hashing MapReduce Consistent hashing
Distributed, concurrent, and networking algorithms
Distributed systems Consensus (computer science) Paxos (computer science) Raft (algorithm) Byzantine fault tolerance Vector clock Lamport timestamp Leader election Gossip protocol
Concurrency Mutual exclusion Semaphore (programming) Monitor (synchronization) Deadlock prevention algorithms Lock-free and wait-free algorithms Compare-and-swap
Networking Routing algorithm Dijkstra's algorithm Bellman–Ford algorithm Distance-vector routing protocol Link-state routing protocol Congestion control Transmission Control Protocol
Bioinformatics and scientific algorithms
Needleman–Wunsch algorithm Smith–Waterman algorithm BLAST (biotechnology) Sequence alignment Hidden Markov model Viterbi algorithm Phylogenetic tree Molecular dynamics Finite element method Fast multipole method
Complexity classes and algorithmic limits
P (complexity) NP (complexity) NP-completeness NP-hardness EXPTIME PSPACE BPP (complexity) BQP Undecidable problem