CodeCodex:Algorithms Project
From CodeCodex
The following is a list of the algorithms as described in Wikipedia.
Most of these algorithms should have code in a number of languages in CC. In order to add one of these algorithms to CC:
- Create the new article title. Remember that article titles in CC need not be as specific as those in Wikipedia. For example, "Java" is ok in CodeCodex, where as the article in Wikipedia is "Java programming language."
- Add relevant information to the article. A good start is by copying appropriate information from Wikipedia. Then google the algorithm to try and find available source code on the net.
- Add categorical information to the article. For example, a Java JSP page that serves up CSS would fall under the categories: Java, JSP, and CSS.
Contents |
[edit] Combinatorial algorithms
[edit] General combinatorial algorithms
- Floyd's cycle-finding algorithm: finds cycles in iterations
- (uniformly distributed) Pseudorandom number generators:
- Robinson-Schensted algorithm: generates permutations from pairs of Young tableaux
[edit] Graph algorithms
See main article graph theory
- 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
- Perturbation methods: an algorithm that computes a locally shortest paths in a graph
- 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
- Kruskal's algorithm: finds a minimum spanning tree for a graph
- Prim's algorithm: finds a minimum spanning tree for a graph
- Boruvka's algorithm: finds a minimum spanning tree for a graph
- Ford-Fulkerson algorithm: computes the maximum flow in a graph
- Edmonds-Karp algorithm: implementation of Ford-Fulkerson
- Nonblocking Minimal Spanning Switch say, for a telephone exchange
- Woodhouse-Sharp algorithm finds a minimum spanning tree for a graph
- Spring based algorithm: algorithm for graph drawing
- Topological sort
- Hungarian algorithm: algorithm for finding a perfect matching
- Coloring algorithm: Graph coloring algorithm.
- Nearest neighbour algorithm: Nearest neighbor algorithm
[edit] Search algorithms
- Linear search: finds an item in an unsorted list
- Selection algorithm: finds the kth largest item in a list
- Binary search algorithm: locates an item in a sorted list
- Binary search tree
- Breadth-first search: traverses a graph level by level
- Depth-first search: traverses a graph branch by branch
- Best-first search: traverses a graph in the order of likely importance using a priority queue
- A* tree search: special case of best-first search that uses heuristics to improve speed
- Uniform-cost search: a tree search that finds the lowest cost route where costs vary
- 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.
- Hash table: finds an item in an unsorted collection in O(1) time.
[edit] String algorithms
[edit] Searching
- Aho-Corasick algorithm
- Bitap algorithm
- Boyer-Moore string search algorithm
- Knuth-Morris-Pratt algorithm
- Rabin-Karp string search algorithm
- Longest-common subsequence problem: Haskell's dynamic programming algorithm
- Longest increasing subsequence problem
- Shortest common supersequence problem
- longest common substring problem
[edit] Approximate matching
- Levenshtein edit distance
- Needleman-Wunsch algorithm
- Smith-Waterman algorithm
- Soundex
- Metaphone: an algorithm for indexing words by their sound, when pronounced in English
- NYSIIS: phonetic algorithm
[edit] Sort algorithms
- Binary tree sort
- Bogosort
- Bubble sort: for each pair of indices, swap the items if out of order
- Bucket sort
- Comb sort
- Cocktail sort
- Counting sort
- Gnome sort
- Heapsort: convert the list into a heap, keep removing the largest element from the heap and adding it to the end of the list
- Insertion sort: determine where the current item belongs in the list of sorted ones, and insert it there
- Merge sort: sort the first and second half of the list separately, then merge the sorted lists
- Pancake sorting
- Pigeonhole 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
- Radix sort: sorts strings letter by letter
- Selection sort: pick the smallest of the remaining elements, add it to the end of the sorted list
- Shell sort: an attempt to improve insertion sort
- Smoothsort
- Topological sort
[edit] Merge algorithms
- Simple Merge algorithm
- k-way Merge algorithm
[edit] Compression algorithms
[edit] Lossless compression algorithms
- Burrows-Wheeler transform: preprocessing useful for improving lossless compression
- DEFLATE: lossless data compression
- Delta encoding: aid to compression of data in which sequential data occurs frequently
- Incremental encoding: delta encoding applied to sequences of strings
- LZW: lossless data compression (Lempel-Ziv-Welch)
- LZ77 (algorithm): LZ77 and LZ78 are the names for the two lossless data compression algorithms
- LZMA: short for Lempel-Ziv-Markov chain-Algorithm
- LZO: data compression algorithm that is focused on speed
- PPM compression algorithm
- Shannon-Fano coding
- Truncated binary encoding
- Run-length encoding: lossless data compression taking advantage of strings of repeated characters
- SEQUITUR algorithm: lossless compression by incremental grammar inference on a string
- EZW (Embedded Zerotree Wavelet)
- Entropy encoding: coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols
- Huffman coding: simple lossless compression taking advantage of relative character frequencies
- Adaptive Huffman coding: adaptive coding technique based on Huffman coding
- Arithmetic coding: advanced entropy coding
- Range encoding: data compression method that is believed to approach the compression ratio of arithmetic coding
- Huffman coding: simple lossless compression taking advantage of relative character frequencies
- Entropy coding with known entropy characteristics
- Unary coding: code that represents a number n with n ones followed by a zero
- Elias delta|gamma|omega coding: universal code encoding the positive integers
- Fibonacci coding: universal code which encodes positive integers into binary code words
- Golomb coding: form of entropy coding that is optimal for alphabets following geometric distributions
- Rice coding: form of entropy coding that is optimal for alphabets following geometric distributions
[edit] Lossy compression algorithms
- Linear predictive coding: lossy compression by representing the spectral envelope of a digital signal of speech in compressed form
- A-law algorithm: standard companding algorithm
- Mu-law algorithm: standard analog signal compression or companding al
