Outline of algorithms
Overview of and topical guide to algorithms
From Wikipedia, the free encyclopedia
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.[1] Algorithms are central to computer science, mathematics, operations research, artificial intelligence,[2] cryptography, data compression, computer graphics, bioinformatics, and many other fields.[3] The study of algorithms includes their design, proof of correctness, efficiency, computational complexity, and implementation in computer programs.[4][5]
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[6]
Data structures and related algorithms
Arrays, lists, and sequences
Trees
Hashing and sets
Graph data structures
Operating system and memory-management algorithms
Searching algorithms
Sorting and order statistics
Comparison sorting
Non-comparison sorting
Order statistics
Graph algorithms
Graph traversal
Shortest paths
Spanning trees and connectivity
Network flow and matching
Graph coloring and hard graph problems
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
Linear algebra
Numerical optimization and approximation
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
Supervised learning
Unsupervised learning
Reinforcement learning
Algorithmic gameplay
AI-assisted algorithm discovery
Cryptographic algorithms
Symmetric-key algorithms
Public-key algorithms
Hashing and authentication
Compression algorithms
Lossless compression
Lossy compression techniques
Computational geometry algorithms
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
Distributed, concurrent, and networking algorithms
Distributed systems
Concurrency
Networking
Bioinformatics and scientific algorithms
Complexity classes and algorithmic limits
Lists of 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
