|
Further information: Combinatorics General combinatorial algorithms Brent's algorithm: finds cycles in iterations using only two iterators Floyd's cycle-finding algorithm: finds cycles in iterations Gale–Shapley algorithm: solves the stable marriage problem Pseudorandom number generators (uniformly distributed): Blum Blum Shub Lagged Fibonacci generator Linear congruential generator Mersenne twister Graph algorithms Further information: Graph theory and Category:Graph algorithms Coloring algorithm: Graph coloring algorithm. Hopcroft–Karp algorithm: convert a bipartite graph to a maximum cardinality matching Hungarian algorithm: algorithm for finding a perfect matching Prüfer coding: conversion between a labeled tree and its Prüfer sequence Tarjan's off-line least common ancestors algorithm: compute lowest common ancestors for pairs of nodes in a tree Topological sort: finds linear order of nodes (e.g. jobs) based on their dependencies. Graph drawing Further information: Graph drawing Force-based algorithms (also known as force-directed algorithms or spring-based algorithm) Spectral layout Network theory Further information: Network theory Network analysis Link analysis Girvan–Newman algorithm: detect communities in complex systems Web link analysis Hyperlink-Induced Topic Search (HITS) (also known as Hubs and authorities) PageRank TrustRank Flow networks Dinic's algorithm: is a strongly polynomial algorithm for computing the maximum flow in a flow network. Edmonds–Karp algorithm: implementation of Ford–Fulkerson Ford–Fulkerson algorithm: computes the maximum flow in a graph Karger's algorithm: a Monte Carlo method to compute the minimum cut of a connected graph Push–relabel algorithm: computes a maximum flow in a graph Routing for graphs Edmonds's algorithm (also known as Chu–Liu/Edmonds's algorithm): find maximum or minimum branchings Euclidean minimum spanning tree: algorithms for computing the minimum spanning tree of a set of points in the plane Euclidean shortest path problem: find the shortest path between two points that does not intersect any obstacle Longest path problem: find a simple path of maximum length in a given graph Minimum spanning tree Boruvka's algorithm Kruskal's algorithm Prim's algorithm Reverse-delete algorithm Nonblocking Minimal Spanning Switch say, for a telephone exchange Shortest path problem Bellman–Ford algorithm: computes shortest paths in a weighted graph (where some of the edge weights may be negative) Dijkstra's algorithm: computes shortest paths in a graph with non-negative edge weights Floyd–Warshall algorithm: solves the all pairs shortest path problem in a weighted, directed graph Johnson algorithm: All pairs shortest path algorithm in sparse weighted directed graph Transitive closure problem: find the transitive closure of a given binary relation Traveling salesman problem Christofides algorithm Nearest neighbour algorithm Warnsdorff's algorithm: A heuristic method for solving the Knight's Tour problem. Graph search Further information: State space search and Graph search algorithm A*: special case of best-first search that uses heuristics to improve speed B*: a best-first graph search algorithm that finds the least-cost path from a given initial node to any goal node (out of one or more possible goals) Backtracking: abandon partial solutions when they are found not to satisfy a complete solution Beam search: is a heuristic search algorithm that is an optimization of best-first search that reduces its memory requirement Beam stack search: integrates backtracking with beam search Best-first search: traverses a graph in the order of likely importance using a priority queue Bidirectional search: find the shortest path from an initial vertex to a goal vertex in a directed graph Bloom filter: a constant time and memory check to see whether a given element exists in a set. May return a false positive, but never a false negative. Breadth-first search: traverses a graph level by level D*: an incremental heuristic search algorithm Depth-first search: traverses a graph branch by branch Dijkstra's algorithm: A special case of A* for which no heuristic function is used General Problem Solver: a seminal theorem-proving algorithm intended to work as a universal problem solver machine. Iterative deepening depth-first search (IDDFS): a state space search strategy Lexicographic breadth-first search (also known as Lex-BFS): a linear time algorithm for ordering the vertices of a graph Uniform-cost search: a tree search that finds the lowest cost route where costs vary SSS*: state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm Subgraphs Bron–Kerbosch algorithm: a technique for finding maximal cliques in an undirected graph Strongly connected components Path-based strong component algorithm Kosaraju's algorithm Tarjan's strongly connected components algorithm Sequence algorithms Further information: Sequences Approximate sequence matching Bitap algorithm: fuzzy algorithm that determines if strings are approximately equal. Phonetic algorithms Daitch–Mokotoff Soundex: a Soundex refinement which allows matching of Slavic and Germanic surnames Double Metaphone: an improvement on Metaphone Match Rating Approach: a phonetic algorithm developed by Western Airlines Metaphone: an algorithm for indexing words by their sound, when pronounced in English NYSIIS: phonetic algorithm, improves on Soundex Soundex: a phonetic algorithm for indexing names by sound, as pronounced in English String metrics: compute a similarity or dissimilarity (distance) score between two pairs of text strings Damerau–Levenshtein distance compute a distance measure between two strings, improves on Levenshtein distance Dice's coefficient (also known as the Dice coefficient): a similarity measure related to the Jaccard index Hamming distance: sum number of positions which are different Jaro–Winkler distance: is a measure of similarity between two strings Levenshtein edit distance: compute a metric for the amount of difference between two sequences Trigram search: search for text when the exact syntax or spelling of the target object is not precisely known Sequence search Linear search: finds an item in an unsorted sequence Selection algorithm: finds the kth largest item in a sequence Ternary search: a technique for finding the minimum or maximum of a function that is either strictly increasing and then strictly decreasing or vice versa Sorted lists Binary search algorithm: locates an item in a sorted sequence Fibonacci search technique: search a sorted sequence using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers Jump search (or block search): linear search on a smaller subset of the sequence Predictive search: binary-like search which factors in magnitude of search term versus the high and low values in the search. Sometimes called dictionary search or interpolated search. Uniform binary search: an optimization of the classic binary search algorithm Sequence merging Main article: Merge algorithm Simple merge algorithm k-way merge algorithm Union (merge, with elements on the output not repeated) Sequence permutations Further information: Permutations Fisher–Yates shuffle (also known as the Knuth shuffle): randomly shuffle a finite set Schensted algorithm: constructs a pair of Young tableaux from a permutation Steinhaus–Johnson–Trotter algorithm (also known as the Johnson–Trotter algorithm): generate permutations by transposing elements Heap's permutation generation algorithm: interchange elements to generate next permutation Sequence alignment Dynamic time warping: measure similarity between two sequences which may vary in time or speed Hirschberg's algorithm: finds the least cost sequence alignment between two sequences, as measured by their Levenshtein distance Needleman–Wunsch algorithm: find global alignment between two sequences Smith–Waterman algorithm: find local sequence alignment Sequence sorting Main article: Sorting algorithms Accuracy dispute This article appears to contradict the article Sorting_algorithm#Comparison_of_algorithms. Please see discussion on the linked talk page. Please do not remove this message until the contradictions are resolved. (March 2011) Exchange Sorts Bubble sort: for each pair of indices, swap the items if out of order Cocktail sort Comb sort Gnome sort Odd-even sort Quicksort: divide list into two, with all items on the first list coming before all items on the second list.; then sort the two lists. Often the method of choice Humorous or ineffective Bogosort Stooge sort Hybrid Flashsort Introsort: begin with quicksort and switch to heapsort when the recursion depth exceeds a certain level Timsort: adaptative algorithm derived from merge sort and insertion sort. Used in Python 2.3 and up, and Java SE 7. Insertion sorts Insertion sort: determine where the current item belongs in the list of sorted ones, and insert it there Library sort Patience sorting Shell sort: an attempt to improve insertion sort Tree sort (binary tree sort): build binary tree, then traverse it to create sorted list Cycle sort: in-place with theoretically optimal number of writes Merge sorts Merge sort: sort the first and second half of the list separately, then merge the sorted lists Strand sort Non-comparison sorts Bead sort Bucket sort Burstsort: build a compact, cache efficient burst trie and then traverse it to create sorted output Counting sort Pigeonhole sort Postman sort: variant of Bucket sort which takes advantage of hierarchical structure Radix sort: sorts strings letter by letter Selection sorts Heapsort: convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list Selection sort: pick the smallest of the remaining elements, add it to the end of the sorted list Smoothsort Other Bitonic sorter Pancake sorting Topological sort Unknown class Samplesort Subsequences Further information: Subsequence Kadane's algorithm: finds maximum sub-array of any size Longest common subsequence problem: Find the longest subsequence common to all sequences in a set of sequences Longest increasing subsequence problem: find the longest increasing subsequence of a given sequence Shortest common supersequence problem: Find the shortest supersequence that contains two or more sequences as subsequences Substrings Further information: Substring Longest common substring problem: find the longest string (or strings) that is a substring (or are substrings) of two or more strings Substring search Aho–Corasick string matching algorithm: trie based algorithm for finding all substring matches to any of a finite set of strings Boyer–Moore string search algorithm: amortized linear (sublinear in most times) algorithm for substring search Boyer–Moore–Horspool algorithm: Simplification of Boyer–Moore Knuth–Morris–Pratt algorithm: substring search which bypasses reexamination of matched characters Rabin–Karp string search algorithm: searches multiple patterns efficiently Zhu–Takaoka string matching algorithm: a variant of the Boyer–Moore Ukkonen's algorithm: a linear-time, online algorithm for constructing suffix trees |
About us|Jobs|Help|Disclaimer|Advertising services|Contact us|Sign in|Website map|Search|
GMT+8, 2015-9-11 22:04 , Processed in 0.133287 second(s), 16 queries .
