Outline of algorithms

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

See also: Timeline of algorithms, History of computer science, and History of mathematics

• 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

See also: Computational complexity theory

• 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

See also: Algorithm design and Algorithmic paradigm

• 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

See also: Data structure and List of data structures

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

See also: Operating system, Scheduling (computing), and Memory management

• 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

See also: Search algorithm and Search data structure

• 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

See also: Sorting algorithm and Selection algorithm

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

See also: Graph theory and Graph algorithm

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

See also: String-searching algorithm and Pattern matching

• 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

See also: Numerical analysis, Computer algebra, Computational mathematics, and Google DeepMind FunSearch

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

See also: Mathematical optimization and Combinatorial optimization

• 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

See also: Artificial intelligence, Machine learning, and List of artificial intelligence 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

See also: Cryptographic algorithm and Cryptography

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

See also: Data compression, Lossless compression, and Lossy compression

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

See also: Computational geometry

• 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

See also: Computer graphics and Digital image processing

• 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

See also: Database index, Information retrieval, and Search engine indexing

• 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

See also: Distributed algorithm, Concurrency control, and Computer network

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

See also: Bioinformatics, Computational biology, and Scientific computing

• 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

See also: Computational complexity theory and Complexity class

• P (complexity)
• NP (complexity)
• NP-completeness
• NP-hardness
• EXPTIME
• PSPACE
• BPP (complexity)
• BQP
• Undecidable problem
• Halting problem
• Rice's theorem
• No free lunch theorem

Lists of algorithms

• List of algorithms
• List of artificial intelligence algorithms
• List of combinatorial algorithms

Notable people

Early and foundational figures

• Al-Khwarizmi — namesake of the term algorithm
• Charles Babbage — early computing pioneer
• Ada Lovelace — wrote an early algorithm for the Analytical Engine
• Alan Turing — computability theory and the Turing machine
• Alonzo Church — lambda calculus and computability theory
• John von Neumann — von Neumann architecture and numerical analysis

Algorithm design and analysis

• Donald Knuth — analysis of algorithms and The Art of Computer Programming
• Edsger W. Dijkstra — Dijkstra's algorithm and structured programming
• Robert W. Floyd — Floyd–Warshall algorithm and algorithm analysis
• Tony Hoare — Quicksort and Hoare logic
• Michael O. Rabin — randomized algorithms and automata theory
• Richard M. Karp — NP-completeness and combinatorial optimization

Complexity theory

• Stephen Cook — Cook–Levin theorem and NP-completeness
• Leonid Levin — NP-completeness and computational complexity theory
• Juris Hartmanis — computational complexity theory
• Richard E. Stearns — computational complexity theory
• Avi Wigderson — randomness and computational complexity

Graph, network, and optimization algorithms

• Richard Bellman — dynamic programming and shortest-path algorithms
• George Dantzig — simplex algorithm and linear programming
• Jack Edmonds — matching and polyhedral combinatorics
• L. R. Ford Jr. — Ford–Fulkerson algorithm and maximum flow problems
• D. R. Fulkerson — Ford–Fulkerson algorithm and network flows
• Robert Tarjan — graph algorithms and data structures

Cryptography and randomized algorithms

• Whitfield Diffie — Diffie–Hellman key exchange
• Martin Hellman — Diffie–Hellman key exchange
• Ron Rivest — RSA and cryptographic algorithms
• Adi Shamir — RSA and cryptographic algorithms
• Leonard Adleman — RSA and DNA computing
• Shafi Goldwasser — cryptography and computational complexity

Artificial intelligence and search algorithms

• John McCarthy — artificial intelligence and symbolic artificial intelligence
• Marvin Minsky — artificial intelligence and computational models
• Herbert A. Simon — heuristic search and artificial intelligence
• Allen Newell — heuristic search and artificial intelligence
• Arthur Samuel — early machine learning and game-playing algorithms
• Judea Pearl — Bayesian networks and probabilistic reasoning

See also

• Algorithm engineering
• Outline of artificial intelligence
• Outline of computer science
• Procedure (computer science)
• List of data structures
• List of numerical analysis topics
• List of optimization software

Further reading

See also: List books on algorithms

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022). Introduction to Algorithms (4th ed.). MIT Press. ISBN 978-0-262-04630-5.
• Knuth, Donald E. (1968). The Art of Computer Programming. Addison-Wesley. ISBN 978-0-201-89683-1.
• Kleinberg, Jon; Tardos, Éva (2005). Algorithm Design. Pearson Education. ISBN 978-0-321-29535-4.
• Skiena, Steven S. (2020). The Algorithm Design Manual (3rd ed.). Springer. ISBN 978-3-030-54255-9.

External links

• Media related to Algorithms at Wikimedia Commons
• Algorithms at Wikibooks
• Learning materials related to Topic:Algorithms at Wikiversity