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
… excerpt ends here. Continue reading the full article.
