*
Share This
Algorithm table
table started by
tsegaran for the computer Base
There is no user-contributed description yet.
\^/ Plot Points:
select property to plot
| x name | x image | x Also Typed With | x Family | x article |
|---|---|---|---|---|
| x Floyd's cycle-finding algorithm |
|
Combinatorics |
Cycle detection is the algorithmic problem of finding a cycle of the following type:
In mathematics, for any function ƒ that maps a finite set S to itself, and any initial value x0 in S, the sequence of iterated function values
must eventually use...
|
|
| x Pseudorandom number generator | Concepts/Theories | Combinatorics |
A pseudorandom number generator (PRNG) is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. The sequence is not truly random in that it is completely determined by a relatively small set of initial...
|
|
| x Blum-Blum-Shub pseudorandom number generator | Concepts/Theories | Combinatorics |
Blum Blum Shub (B.B.S.) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub (Blum et al, 1986).
Blum Blum Shub takes the form:
where M=pq is the product of two large primes p and q. At each step of the...
|
|
| Cryptography | ||||
| x Mersenne twister | Concepts/Theories | Combinatorics |
The Mersenne twister is a pseudorandom number generator developed in 1997 by Makoto Matsumoto (松本 眞, Makoto Matsumoto) and Takuji Nishimura (西村 拓士, Takuji Nishimura) that is based on a matrix linear recurrence over a finite binary field F2. It...
|
|
| x Lagged Fibonacci generator | Concepts/Theories | Combinatorics |
A Lagged Fibonacci generator (LFG) is an example of a pseudorandom number generator. This class of random number generator is aimed at being an improvement on the 'standard' linear congruential generator. These are based on a generalisation of the...
|
|
| x Linear congruential generator |
|
Concepts/Theories | Combinatorics |
A linear congruential generator (LCG) represent one of the oldest and best-known pseudorandom number generator algorithms. The theory behind them is easy to understand, and they are easily implemented and fast.
The generator is defined by the...
|
| x Robinson-Schensted algorithm | Combinatorics |
In mathematics, the Robinson–Schensted algorithm is a combinatorial algorithm, first described by Robinson in 1938, which establishes a bijective correspondence between elements of the symmetric group Sn and pairs of standard Young tableaux of the...
|
||
| x Graph theory | Algorithm Family | Graph theory |
In mathematics and computer science, graph theory is the study of graphs: mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and...
|
|
| Concepts/Theories | ||||
| x Bellman-Ford algorithm | Concepts/Theories | Graph theory |
The Bellman–Ford algorithm, a label correcting algorithm, computes single-source shortest paths in a weighted digraph (where some of the edge weights may be negative). Dijkstra's algorithm solves the same problem with a lower running time, but...
|
|
| x Dijkstra's algorithm |
|
Concepts/Theories | Graph theory |
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with non negative edge path costs, outputting a shortest path tree....
|
| x Perturbation theory | Graph theory |
Perturbation theory comprises mathematical methods that are used to find an approximate solution to a problem which cannot be solved exactly, by starting from the exact solution of a related problem. Perturbation theory is applicable if the problem...
|
||
| x Floyd-Warshall algorithm | Concepts/Theories | Graph theory |
In computer science, the Floyd–Warshall algorithm (sometimes known as the WFI Algorithm or Roy–Floyd algorithm, since Bernard Roy described this algorithm in 1959) is a graph analysis algorithm for finding shortest paths in a weighted, directed...
|
|
| x Johnson's algorithm | Graph theory |
Johnson's algorithm is a way to find shortest paths between all pairs of vertices in a sparse directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist.
Johnson's algorithm consists of the...
|
||
| x Kruskal's algorithm |
|
Concepts/Theories | Graph theory |
Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in...
|
| x Prim's algorithm |
|
Concepts/Theories | Graph theory |
Prim's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in...
|
| x Borůvka's algorithm | Concepts/Theories | Graph theory |
Borůvka's algorithm is an algorithm for finding a minimum spanning tree in a graph for which all edge weights are distinct.
It was first published in 1926 by Otakar Borůvka as a method of constructing an efficient electricity network for Moravia....
|
|
| x Ford-Fulkerson algorithm |
|
Graph theory |
The Ford-Fulkerson algorithm (named for L. R. Ford, Jr. and D. R. Fulkerson) computes the maximum flow in a flow network. It was published in 1956. The name "Ford-Fulkerson" is often also used for the Edmonds-Karp algorithm, which is a...
|
|
| x Edmonds-Karp algorithm |
|
Graph theory |
In computer science and graph theory, the Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson method for computing the maximum flow in a flow network in . It is asymptotically slower than the relabel-to-front algorithm, which runs in ,...
|
|
| x Nonblocking minimal spanning switch |
|
Graph theory |
A nonblocking minimal spanning switch is a device that implements a "switch" which is capable of connecting N inputs to N outputs in any combination (it is non-blocking in that it can always make the connection) and does so with the fewest...
|
|
| x Force-based algorithms | Concepts/Theories | Graph theory |
Force-based or force-directed algorithms are a class of algorithms for drawing graphs in an aesthetically pleasing way. Their purpose is to position the nodes of a graph in two dimensional or three dimensional space so that all the edges are of more...
|
|
| x Topological sorting |
|
Concepts/Theories | Graph theory |
In graph theory, a topological sort or topological ordering of a directed acyclic graph (DAG) is a linear ordering of its nodes in which each node comes before all nodes to which it has outbound edges. Every DAG has one or more topological sorts....
|
| Sorting algorithm | ||||
| x Hungarian algorithm | Graph theory |
The Hungarian algorithm is a combinatorial optimization algorithm which solves assignment problems in polynomial time (O(n)). The first version, known as the Hungarian method, was invented and published by Harold Kuhn in 1955. This was revised by...
|
||
| x Graph coloring | Concepts/Theories | Graph theory |
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a...
|
|
| Computational problem | ||||
| x Nearest neighbour algorithm | Concepts/Theories | Graph theory |
The nearest neighbour algorithm was one of the first algorithms used to determine a solution to the travelling salesman problem. It quickly yields a short tour, but usually not the optimal one.
Below is the application of nearest neighbour algorithm...
|
|
| x Linear search |
|
Search algorithm |
In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a list of data for a particular value.
It operates by checking every element of a list one at a time in sequence until a match...
|
|
| x Selection algorithm | Search algorithm |
In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list, called order statistics. This includes the cases of finding the minimum, maximum, and median elements. There are worst-case linear time...
|
||
| x Binary search algorithm |
|
Search algorithm |
A binary search algorithm (or binary chop) is a technique for locating a particular value in a sorted list of values. To cast this in the frame of the guessing game (see Example below), realize that we seek to guess the index, or numbered place, of...
|
|
| x Binary search tree | Concepts/Theories | Search algorithm |
In computer science, a binary search tree (BST) is a binary tree data structure which has the following properties:
The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms...
|
|
| Data Structure | Sorting algorithm | |||
| Abstract Data Structure | ||||
| x Breadth-first search |
|
Concepts/Theories | Search algorithm |
In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds...
|
| x Depth-first search |
|
Concepts/Theories | Search algorithm |
Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking....
|
| x Best-first search | Concepts/Theories | Search algorithm |
Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to some rule.
Judea Pearl described best-first search as estimating the promise of node n by a "heuristic evaluation function f(n)...
|
|
| x A* search algorithm |
|
Concepts/Theories | Search algorithm |
In computer science, A* (pronounced "A star") is a best-first, graph search algorithm that finds the least-cost path from a given initial node to one goal node (out of one or more possible goals).
It uses a distance-plus-cost heuristic function ...
|
| x Uniform-cost search | Search algorithm |
In computer science, uniform-cost search (UCS) is a tree search algorithm used for traversing or searching a weighted tree, tree structure, or graph. Intuitively, the search begins at the root node. The search continues by visiting the next node...
|
||
| x Interpolation search |
|
Search algorithm |
Interpolation search is an algorithm for searching for a given key value in an indexed array that has been ordered by the values of the key. It parallels how humans search through a telephone book for a particular name, the key value by which the...
|
|
| x Hash table | Data Structure | Search algorithm |
In computer science, a hash table, or a hash map, is a data structure that associates keys with values. The primary operation it supports efficiently is a lookup: given a key (e.g. a person's name), find the corresponding value (e.g. that person's...
|
|
| x Aho-Corasick algorithm | String searching algorithm |
The Aho-Corasick algorithm is a string searching algorithm created by Alfred V. Aho and Margaret J. Corasick. It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It...
|
||
| x Bitap algorithm | String searching algorithm |
The bitap algorithm (also known as the shift-or, shift-and or Baeza-Yates-Gonnet algorithm) is a fuzzy string searching algorithm developed by Udi Manber and Sun Wu in 1991 based on work done by Ricardo Baeza-Yates and Gaston Gonnet. The algorithm...
|
||
| x Boyer–Moore string search algorithm | Invention | String searching algorithm |
The Boyer–Moore string search algorithm is a particularly efficient string searching algorithm, and it has been the standard benchmark for the practical string search literature. It was developed by Bob Boyer and J Strother Moore in 1977. The...
|
|
| x Knuth–Morris–Pratt algorithm | String searching algorithm |
The Knuth–Morris–Pratt string searching algorithm searches for occurrences of a "word" W within a main "text string" S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the...
|
||
| x Rabin-Karp string search algorithm | String searching algorithm |
The Rabin-Karp algorithm is a string searching algorithm created by Michael O. Rabin and Richard M. Karp in 1987 that uses hashing to find a substring in a text. It is used for multiple pattern matching rather than single pattern matching. For text...
|
||
| x Longest common subsequence problem | String searching algorithm |
The longest common subsequence problem (LCS) is finding the longest subsequence common to all sequences in a set of sequences (often just two). It is a classic computer science problem, the basis of diff, and has applications in bioinformatics.
It...
|
||
| x Longest increasing subsequence | String searching algorithm |
The longest increasing subsequence problem is to find the longest increasing subsequence of a given sequence. Note that subsequence we are searching for is not necessarily contiguous. Searching for the longest contiguous increasing subsequence would...
|
||
| x Shortest common supersequence | ||||