Share This
table started by
tsegaran for the computer Base
There is no user-contributed description yet.
Add More Topics
Save this view to a base, or just for yourself.
457 Algorithm topics matching:
Filter this Collection| x name | x image | 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 | 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 | 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 | Combinatorics |
The Mersenne twister is a pseudorandom number generator developed in 1997 by Makoto Matsumoto (松本 眞) and Takuji Nishimura (西村 拓士) that is based on a matrix linear recurrence over a finite binary field F2. It provides for fast generation of very high...
|
|
| x Lagged Fibonacci generator | 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 |
|
Combinatorics |
A linear congruential generator (LCG) represents 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 1938), which establishes a bijective correspondence between elements of the symmetric group Sn and pairs of standard Young tableaux of the...
|
|
| x Graph theory | 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...
|
|
| x Bellman-Ford algorithm | 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 |
|
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 nonnegative edge path costs, producing a shortest path tree. This...
|
| 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 | 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. It works by using the Bellman-Ford...
|
|
| x Kruskal's algorithm |
|
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 |
|
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 | 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 | 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 |
|
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 method is a combinatorial optimization algorithm which solves the assignment problem in polynomial time and which anticipated later primal-dual methods. It was developed and published by Harold Kuhn in 1955, who gave the name ...
|
|
| x Graph coloring | 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...
|
|
| x Nearest neighbour algorithm | 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 (such a number is called the kth order statistic). This includes the cases of finding the minimum, maximum, and median elements. There are worst...
|
|
| x Binary search algorithm |
|
Search algorithm |
In computer science, a binary search is an algorithm for locating the position of an element in a sorted list by checking the middle, eliminating half of the list from consideration, and then performing the search on the remaining half. If the...
|
| x Binary search tree | Search algorithm |
In computer science, a binary search tree (BST) is a node based binary tree data structure which has the following properties:
From the above properties it naturally follows that:
Generally, the information represented by each node is a record...
|
|
| Sorting algorithm | |||
| x Breadth-first search |
|
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 |
|
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 | Search algorithm |
Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to a specified rule.
Judea Pearl described best-first search as estimating the promise of node n by a "heuristic evaluation function...
|
|
| x A* search algorithm |
|
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. The search begins at the root node. The search continues by visiting the next node which has the...
|
|
| 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 | Search algorithm |
In computer science, a hash table or hash map is a data structure that uses a hash function to efficiently map certain identifiers or keys (e.g., person names) to associated values (e.g., their telephone numbers). The hash function is used to...
|
|
| 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. The algorithm tells whether a given text contains a substring which is "approximately equal" to a given pattern, where...
|
|
| x Boyer–Moore string search algorithm | 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 (or KMP 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...
|
|
| 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 (LCS) problem is to find 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 (a file comparison program that outputs the...
|
|
| x Longest increasing subsequence | String searching algorithm |
The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not...
|
|
| x Shortest common supersequence | String searching algorithm |
This shortest common supersequence problem is closely related to the longest common subsequence problem. Given two sequences X = and Y = , a sequence U = is a common supersequence of X and Y if U is a...
|
|
| x Longest common substring problem |
|
String searching algorithm |
The longest common substring problem is to find the longest string (or strings) that is a substring (or are substrings) of two or more strings. It should not be confused with the longest common subsequence problem. (For an explanation of the...
|
| x Kadane's Algorithm | String searching algorithm |
In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the...
|
|
| x Boyer–Moore–Horspool algorithm | String searching algorithm |
In computer science, the Boyer–Moore–Horspool algorithm or Horspool's algorithm is an algorithm for finding substrings in strings.
It is a simplification of the Boyer-Moore algorithm which is related to the Knuth-Morris-Pratt algorithm. The...
|
|
| x Hirschberg's algorithm | String searching algorithm |
Hirschberg's algorithm, named after its inventor, Dan Hirschberg, is a dynamic programming algorithm that finds the least cost sequence alignment between two strings, where cost is measured as Levenshtein edit distance, defined to be the sum of the...
|
|
| x Levenshtein distance | String searching algorithm |
In information theory and computer science, the Levenshtein distance is a metric for measuring the amount of difference between two sequences (i.e., the so called edit distance). The Levenshtein distance between two strings is given by the minimum...
|
|
| x Metaphone | String searching algorithm |
Metaphone is a phonetic algorithm, an algorithm published in 1990 for indexing words by their English pronunciation. The algorithm produces variable length keys as its output, as opposed to Soundex's fixed-length keys. Similar sounding words share...
|
|
| x Needleman-Wunsch algorithm | String searching algorithm |
The Needleman–Wunsch algorithm performs a global alignment on two sequences (called A and B here). It is commonly used in bioinformatics to align protein or nucleotide sequences. The algorithm was published in 1970 by Saul Needleman and Christian...
|
|
| x Smith Waterman algorithm | String searching algorithm |
The Smith-Waterman algorithm is a well-known algorithm for performing local sequence alignment; that is, for determining similar regions between two nucleotide or protein sequences. Instead of looking at the total sequence, the Smith-Waterman...
|
|
| x Soundex | String searching algorithm |
Soundex is a phonetic algorithm for indexing names by sound, as pronounced in English. The goal is for homophones to be encoded to the same representation so that they can be matched despite minor differences in spelling. The algorithm mainly...
|
|
| x Bogosort |
|
Sorting algorithm |
In computer science, bogosort (also random sort, shotgun sort or monkey sort) is a particularly ineffective sorting algorithm. Its only use is for educational purposes, to contrast it with other more realistic algorithms. If bogosort were used to...
|
| x Bubble sort |
|
Sorting algorithm |
Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps...
|
| x Bucket sort |
|
Sorting algorithm |
Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting...
|
| x Cocktail sort | Sorting algorithm |
Cocktail sort, also known as bidirectional bubble sort, cocktail shaker sort, shaker sort (which can also refer to a variant of selection sort), ripple sort, shuttle sort or happy hour sort, is a variation of bubble sort that is both a stable...
|
|
| x Comb sort | Sorting algorithm |
Comb sort is a relatively simplistic sorting algorithm originally designed by Wlodek Dobosiewicz in 1980. Later rediscovered and popularized by Stephen Lacey and Richard Box with a Byte Magazine article published in April 1991. Comb sort improves on...
|
|
| x Counting sort | Sorting algorithm |
Counting sort (sometimes referred to as ultra sort or math sort) is a sorting algorithm which (like bucket sort) takes advantage of knowing the range of the numbers in the array to be sorted (array A). It uses this range to create an array C of this...
|
|
| x Gnome sort | Sorting algorithm |
Gnome sort is a sorting algorithm which is similar to insertion sort, except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort. The name comes from the supposed behavior of the Dutch garden gnome in...
|
|
| x Flashsort | Sorting algorithm |
Flashsort is a sorting algorithm with extremely good O(n) efficiency for balanced data sets, published in 1998 by Karl-Dietrich Neubert.
Flashsort works based on the principle that in either a randomized or partially-ordered data set in which data...
|
|
