This is the web page of terms with definitions that have links to implementations with source code. The language is in parentheses. We also list all entries by type, for instance, whether it is an algorithm, a definition, a problem, or a data structure, and entries by area, for instance, graphs, trees, sorting, etc.

Don't use this site to cheat. Teachers, contact me if I can help.

We need people to contribute. If terms are missing or you can add or correct definitions, please contact me by email (paul.black@nist.gov) or by other means.

By selecting almost any of these links, you will be leaving NIST webspace. We provided these links because they may have information of interest to you. No inferences should be drawn because some sites are referenced, or not, from this page. There may be other web sites that are more appropriate for your purpose. NIST does not necessarily endorse the views expressed, or concur with the facts presented on these sites. Further, NIST does not endorse any commercial products that may be mentioned on these sites. Please address comments about this page to paul.black@nist.gov.

A great source of implementations, organized by area and reviewed for quality, is the Stony Brook Algorithm Repository. A great source of implementations of mathematical functions is the NIST Guide to Available Mathematical Software or GAMS.

Java is a trademark of Sun Microsystems, Inc.

Run on Tue Jan 3 10:46:18 2006

• Ackermann's function: History of the function and (Modula-2) code. (Lisp). (Pascal). (Miranda).
• adaptive Huffman coding: (C)
• Aho-Corasick: Bruce Watson's SPARE Parts, a string pattern recognition toolkit (C++).
• Alpha Skip Search algorithm: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• American flag sort: (C). It is program C (C) in the paper.
• Apostolico-Crochemore: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• Apostolico-Giancarlo algorithm: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• approximate string matching: See implementations at string matching. (C and Pascal)
• arithmetic coding: Theory development and implementation (C).
• array: (C). Read and write different arrays (Fortran, C++).
• association list: (C++, Pascal, and Fortran). Kaz Kylheku's Kazlib (C) implementing dictionary, dynamic hash table, red-black tree, and doubly linked list.
• AVL tree: Ben Pfaff's explanations and code (C), Kaz Kylheku's Austin (C) implementing sorted list, binary search tree, AVL, red-black and splay trees and conversions from any of these to any other. Worst-case behavior of traversal, annotated for real time (WOOP/ADA).
• balanced binary tree: red-black tree analysis, explanation, examples, and code (C). Ben Pfaff's AVL tree explanation (C).
• balanced merge sort: (C) using an auxiliary function to select next file (C).
• balanced multiway tree: tutorial of how B-trees work and code (Perl), another tutorial and code (C++), data structure definition (C and Pascal), insert (C and Pascal) using auxiliary functions (C and Pascal), search (C and Pascal), (Pick Basic?).
• Batcher sort: explanation, analysis, bibliography, etc. (Java). reference source code (C). Section from 1994 User Manual for Portable Parallel C++ (pC++).
• BB(α) tree: Worst-case behavior of traversal, annotated for real time (WOOP/ADA), including bibliography. insert (C and Pascal) and delete (C and Pascal) that use check root (C and Pascal) (or this one or this one?), left rotation (C and Pascal), and right rotation (C and Pascal).
• Bellman-Ford algorithm: The entry in Wikipedia (C, Assembly, and pseudocode) has a proof, too.
• Benford's law: An implementation (Java) due to Sedgewick and Wayne (search for Benford's law).
• bidirectional bubble sort: animation and code (Java); demonstration and source code (Java); animation and code, see cocktail sort (Java).
• binary heap: delete (C) and insert (C and Pascal) both of which use the auxiliary function siftup (C and Pascal), explanation, examples, and code (C). (Fortran)
• binary insertion sort: (C)
• binary knapsack problem: (Fortran and Pascal). GAMS Class G2c3 (Fortran).
• binary priority queue: Gonnet and Baeza-Yates insert (C and Pascal) and delete (C and Pascal)
• binary search: search (C) where indexes are 0 to n, inclusive. That is, n is the highest index of the 0-based array, and possible key indexes, k, are low < k <= high in the loop. (Scheme), Worst-case behavior annotated for real time (WOOP/ADA), including bibliography.
• binary search tree: Ben Pfaff's insert, delete, search, copy, etc. (literate C); Kaz Kylheku's Austin (C) implementing sorted list, binary search tree, AVL, red-black and splay trees and conversions from any of these to any other. insert (C), insert (C), search (C), and insert, search, delete, and various traversals (Modula-2) (use must be acknowledged).
• binary tree: examples, analysis, and code (C). Worst-case behavior of traversal, annotated for real time (WOOP/ADA).
• bin packing problem: (Icon).
• bin sort: analysis, explanation, and code (C), and (C).
• bitonic sort: explanation, analysis, bibliography, etc. (Java). reference source code (C). Section from 1994 User Manual for Portable Parallel C++ (pC++).
• Bloom filter: Arash Partow's implementations (C++, Object Pascal).
• Boyer-Moore: Christian Charras' and Thierry Lecroq's Boyer-Moore algorithm (C). (C) which uses Boyer-Moore preprocessing (C)
• Boyer-Moore-Horspool: Christian Charras' and Thierry Lecroq's Horspool algorithm (C). Gonnet and Baeza-Yates' (C) or (Pascal)
• bozo sort: demonstration and source code (Java).
• B+-tree: Search the web for bplus to find implementations. More targeted searches are bplustree, "b plus tree", or search the comp.sources groups for bplus.
• branch and bound: Arnold Neumaier's page of branch and bound implementations (C, C++, Matlab, Fortran, executables, etc.).
• Bresenham's algorithm: The original IBM 1401 implementation (Autocoder) from 1962.
• brick sort: Sedgewick's Analysis of Shellsort and Related Algorithms (C)
• brute force string search: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C), (C and Pascal)
• brute force string search with mismatches: Gonnet and Baeza-Yates' (C and Pascal)
• B*-tree: data structure definition (C and Pascal), B-tree insert (C and Pascal) using auxiliary functions (C and Pascal), B-tree search (C and Pascal).
• B-tree: tutorial of how B-trees work and code (Perl), another tutorial and code (C++), data structure definition (C and Pascal), insert (C and Pascal) using auxiliary functions (C and Pascal), search (C and Pascal), (Pick Basic?).
• bubble sort: animation and code (Java); demonstration and source code (Java) - but code might not render properly; (Rexx); (Java).
• bucket sort: analysis, explanation, and code (C), and (C).
• calendar queue: In a simulation tool package (C)
• cartesian tree: Oleg Kiselyov's (Scheme)
• Caverphone: PDF document comparing soundex, metaphone, and Caverphone 2.0 (Python). PDF document comparing soundex, metaphone, NYSIIS, and Caverphone (JavaScript).
• Cayley-Purser: explanation, proofs, comparison with RSA, how it can be broken, and code (Mathematica)
• chaining: (C)
• Chinese postman problem: (C++, Mathematica and Fortran)
• clique problem: (Fortran, C, and Mathematica)
• coalesced chaining: insert (C), search (C).
• cocktail shaker sort: animation and code (Java); demonstration and source code (Java); animation and code, see cocktail sort (Java).
• Colussi: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• combination: The Combinatorial Object Server's information on Combinations (Pascal and C); Michael Gilleland's CombinationGenerator class (Java).
• comb sort: An improved comb sort (C) with discussion. Wayne Conrad has (C++ and Ruby) versions, contrasts it with bubble sort, and links to versions in bash, Basic, C, Forth, Fortran 77, i386 assembly, Java, Pascal, Perl, PHP, and Python. (Java). Dave Ring wrote a variant (Java) that switches to an insertion sort after the gap is 9.
• connected components: (C++, C, Pascal, Mathematica, and Fortran)
• CORDIC: introduction and code (C). Ken Turkowski's Introduction to the CORDIC Technique (C).
• counting sort: Marion McCoskey's Single Buffered Count Sort (C++). Bruno R. Preiss' sort integers 0 to m-1 (C).
• cube root: GAMS Class C2 has many implementations of powers, roots, and reciprocals (C and Fortran).
• cutting stock problem: linear and nonlinear programming and algebra packages (C and Fortran)
• cycle: graph cycle detector (C)
• deterministic finite automata string search: description and animation (C), (C) which uses a finite automaton structure (C) and builds a recognizer (C)
• dictionary: (C++, Pascal, and Fortran). Kaz Kylheku's Kazlib (C) implementing dictionary, dynamic hash table, red-black tree, and doubly linked list.
• diet: insert, delete, and member (ML), insert, delete, and member (Haskell)
• digraph: build, traverse, top sort, etc. weighted, directed graph (Java)
• Dijkstra's algorithm: An analysis with code (C)
• dining philosophers: code Shared Memory and Semaphores (C and C++), One example (Siefast) for the Siefast simulator.
• direct chaining: insert (C), search (C). Duane A. Bailey's ChainedHashtable (Java) class from Java Structures.
• directed graph: build, traverse, top sort, etc. weighted, directed graph (Java)
• discrete interval encoding tree: insert, delete, and member (ML), insert, delete, and member (Haskell)
• divide and conquer: how many odd numbers in an array? (C)
• double-direction bubble sort: animation and code (Java); demonstration and source code (Java); animation and code, see cocktail sort (Java).
• double hashing: insert (C and Pascal), search (C and Pascal)
• double metaphone: Metaphone and double metaphone (Basic, C, Perl, and C++). Apache codec implementations of soundex, Metaphone, and Double Metaphone (Java). applet for name lookup (Java). (C++) zip archive; look in philips.zip for Dmetaph.cpp and Dmetaph.h.
• doubly linked list: Kaz Kylheku's Kazlib (C) implementing dictionary, dynamic hash table, red-black tree, and doubly linked list.
• dyadic tree: examples, analysis, and code (C). Worst-case behavior of traversal, annotated for real time (WOOP/ADA).
• dynamic hashing: Charles B. Falconer's hashlib (C) including several example applications. Kaz Kylheku's Kazlib (C) implementing dictionary, dynamic hash table, red-black tree, and doubly linked list.
• dynamic Huffman coding: (C)
• dynamic programming: Oleg Kiselyov's program to optimally lay out a page (C++) using dynamic programming.
• edge coloring: (C++, Mathematica, and C)
• edge connectivity: (Mathematica, C, and Pascal)
• edit distance: Levenshtein distance (Java, C++, Visual Basic), includes a great explanation and links to code in Perl, C, JavaScript, Python, and many more languages. Many implementations (Lisp, Haskell, Java, Python, Ruby, Scheme, Visual Basic, Visual FoxPro).
• enfilade: Green (C)
• Euclidean algorithm: Worst-case behavior annotated for real time (WOOP/ADA), (Scheme).
• Euclidean Steiner tree: GeoSteiner (C) - software for computing steiner trees.
• Euclid's algorithm: Worst-case behavior annotated for real time (WOOP/ADA), (Scheme).
• Euler cycle: (Mathematica and Fortran)
• Eulerian path: (Mathematica and Fortran)
• exact string matching: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C), (C++ and Pascal), Strmat (C) - a collection of string matching and pattern discovery programs, (Fortran), (Fortran).
• exchange sort: animation and code (Java); demonstration and source code (Java) - but code might not render properly; (Rexx); (Java).
• extendible hashing: A description including a hash function (COBOL).
• external chaining: insert (C), search (C).
• external quicksort: (C)
• extrapolation search: C-like pseudo-code. annotated for real time (WOOP/ADA), including bibliography, (Pascal)
• factorial: Peter Luschny's 14 fast factorial algorithms (Java and C#) including benchmarks and advice. Calum Grant's prime sieve fast factorial (C++). Christer Ericson's fast factorial (C). (Scheme).
• fast fourier transform: Worst-case behavior annotated for real time (WOOP/ADA).
• feedback edge set: (C)
• feedback vertex set: (C)
• FFT: Worst-case behavior annotated for real time (WOOP/ADA).
• Fibonaccian search: Manolis Lourakis' fibsrch (C). Worst-case behavior annotated for real time (WOOP/ADA), including bibliography. (Interpolation and secant search "guess more precisely where the key being sought falls".)
• Fibonacci heap: An explanation and code for ExtractMin and DecreaseKey (C++) by John Boyer, Algorithm Alley, Dr. Dobb's Journal, January 1997.
• Fibonacci number: Worst-case behavior to generate nth number, annotated for real time (WOOP/ADA), (Scheme).
• FIFO: (Java). Darius Bacon's functional implementation (Scheme).
• Find: analysis and comparison (Rexx)
• finite state automaton: Jan Daciuk's Finite state utilities (C++) including many links to other code, papers, etc. Finite State Automata Utilities (Prolog), which generate C code, minimize, visualize, etc. Page has binaries, too. For regular expressions generate NFSM, make deterministic, and optimize (Haskell). Oleg Kiselyov's program to minimize a finite state machine (Prolog).
• finite state machine: Jan Daciuk's Finite state utilities (C++) including many links to other code, papers, etc. Finite State Automata Utilities (Prolog), which generate C code, minimize, visualize, etc. Page has binaries, too. For regular expressions generate NFSM, make deterministic, and optimize (Haskell). Oleg Kiselyov's program to minimize a finite state machine (Prolog).
• finite state machine minimization: (C++ and Pascal)
• Fisher-Yates shuffle: Ben Pfaff's answer to how can I shuffle the contents of an array? (C). An implementation (Java) due to Sedgewick and Wayne, including an explanation of unfair shuffle algorithms (search for Shuffling).
• Ford-Bellman: The entry in Wikipedia (C, Assembly, and pseudocode) has a proof, too.
• Galil-Giancarlo: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• Galil-Seiferas: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• GCD: (Scheme)
• gnome sort: (C)
• graph: GraphEd -- Graph Editor and Layout Program (C), graph manipulation (C++, C, Mathematica, and Pascal), build, traverse, top sort, etc. weighted, directed graphs (Java), JGraphT (Java) build, traverse, and display directed and undirected graphs, GEF - Graph Editing Framework (Java) a library to edit and display graphs. graph generating (C, Mathematica, Pascal, C++, and Fortran), GTL - the Graph Template Library (C), BGL - the Boost Graph Library (C++) JUNG (Java), the Java Universal Network/Graph framework. JDSL (Java), the Data Structures Library in Java.
• graph drawing: draw a graph nicely (C and Mathematica), draw a graph in the plane such that no edges cross (C, C++, and Mathematica), GraphEd: Graph Editor and Layout Program (C). Graphviz: Graph Visualization Software (C), consisting of many graph drawing programs, viewers (C, Java, and TCL/TK), etc.
• graph isomorphism: (C and Mathematica)
• graph partition: (C++)
• Gray code: Glenn Rhoads' Snippets (C). binary-to-Gray and Gray-to-binary conversion (C) with history, references, and application to genetic algorithms. convert between binary and Gray (C): a PDF document of section 20.2 of Numerical recipes in C, binary-to-Gray, code generation, and plotting (Maple) with applications and references.
• greatest common divisor: (Scheme)
• Grover's algorithm: (C-like)
• Hamiltonian cycle: (Fortran, C, Mathematica, and C++)
• hash function: See the implementations at minimal perfect hashing (C++ and C) and Pearson's hash (C). A fast, parameterizable, broadly applicable hash function (C) including code for and evaluations of many other hash functions. A review and comparison of many integer hash functions (C). Overview of different kinds of hash functions. Arash Partow's hash functions (C, C++, Pascal, Java). Fowler/Noll/Vo or FNV hash function (C). Hash functions for strings (C) and (C and Perl). Kazlib (C).
• hash table: direct chaining: (C). linear probing hashing: insert (C), look up (C), Kazlib (C), direct chaining: explanations, diagrams, and code (Visual Basic). Explanation and sample problems for hashing (C) (some pages require free registration).
• heapsort: Lang's definitions, explanations, diagrams, Java applet, and pseudo-code (C), (Java), (Java), Worst-case behavior annotated for real time (WOOP/ADA), including bibliography, (Rexx).
• heaviest common subsequence: (C and Mathematica)
• highest common factor: (Scheme)
• histogram sort: (C and Pascal).
• Horspool: Christian Charras' and Thierry Lecroq's Horspool algorithm (C). Gonnet and Baeza-Yates' (C) or (Pascal)
• Huffman coding: build tree in array (C) -- also computes entropy and efficiency.
• Hungarian algorithm: Example of step-wise coding of the algorithm (Pascal) from a description. The Common Lisp library (CLLIB) implementation (Common Lisp).
• independent set: (Fortran and C)
• insertion sort: (Java). An implementation (Java) due to Sedgewick and Wayne (search for Insertion sort). Other implementations may be available through the Stony Brook Algorithm Repository, Sorting; (Scheme); (Fortran).
• internal sort: (Fortran)
• interpolation search: C-like pseudo-code. annotated for real time (WOOP/ADA), including bibliography, (Pascal)
• interpolation-sequential search: (Pascal) or (Pascal)
• interpolation sort: (C and Pascal).
• isomorphic: (C and Mathematica)
• Johnson-Trotter: Information on Permutations (Pascal and C)
• J sort: demonstration and source code (Java).
• Karmarkar's algorithm: Article with details of implementation and comparisons (Algol-like pseudo-code)
• Karnaugh map: (Java)
• Karp-Rabin: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C), description and animation (C), (C and Pascal).
• k-ary Huffman coding: animation which counts characters, finds the code, encodes, and decodes (Java),
• k-d tree: C, Pascal, or FORTRAN, insert (C), range search (C), and search (C). (C, Pascal, and Fortran)
• KMP: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C). Unix strstr implemented with KMP (C). (C and Pascal) which uses Boyer-Moore preprocessing (C)
• KmpSkip Search: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• knapsack problem: (Fortran and Pascal). GAMS Class G2c3 (Fortran).
• knight's tour: Oleg Kiselyov's derivation (Prolog)
• Knuth-Morris-Pratt algorithm: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C). Unix strstr implemented with KMP (C). (C and Pascal) which uses Boyer-Moore preprocessing (C)
• Königsberg bridges problem: (Mathematica and Fortran)
• Kruskal's algorithm: analysis and code (C), (pseudocode)
• KV diagram: (Java)
• leftist tree: merge and delete (C and Pascal) which use distance (C and Pascal), insert (C and Pascal)
• left rotation: (Pascal), (C). A great series of animations explaining rotations with code (Java).
• Lempel-Ziv-Welch: explanation (C)
• Levenshtein distance: Levenshtein distance (Java, C++, Visual Basic), includes a great explanation and links to code in Perl, C, JavaScript, Python, and many more languages. Many implementations (Lisp, Haskell, Java, Python, Ruby, Scheme, Visual Basic, Visual FoxPro).
• LIFO: (Scheme)
• linear insertion sort: (Java). An implementation (Java) due to Sedgewick and Wayne (search for Insertion sort). Other implementations may be available through the Stony Brook Algorithm Repository, Sorting; (Scheme); (Fortran).
• linear probing: insert (C), search (C).
• linear probing sort: (C and Pascal).
• linear quadtree: Spatial Linear Quadtree with Constant Time Node Traversal (C++) including man pages, examples, etc.
• linear search: (C)
• linked list: explanations, examples, iterators, sorting lists, etc. (C++), Kazlib (C), (C++)
• longest common subsequence: (C and Mathematica)
• longest common substring: (C and Mathematica)
• lower triangular matrix: (Fortran)
• LZW compression: explanation (C)
• map: (C++, Pascal, and Fortran). Kaz Kylheku's Kazlib (C) implementing dictionary, dynamic hash table, red-black tree, and doubly linked list.
• matching: (Fortran, C, C++, and Pascal)
• matrix: (Fortran), (C++)
• Maximal Shift: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• maximum-flow problem: Problem explanation and development of Ford-Fulkerson (pseudocode); including solving related problems, like multi-source, vertex capacity, bipartite matching, etc. description and links to implementations (C, Fortran, C++, Pascal, and Mathematica).
• median: find median (Pascal and C++)
• merge: (Scheme)
• merge sort: (C) that needs list merge (C) or array merge (C), (Pascal) that needs list merge (Pascal) or array merge (Pascal); (Java); Demo and code of in-place and double merge sort (Java); Worst-case behavior annotated for real time (WOOP/ADA), including bibliography. John David Stone's (Scheme). Siegfried Sielaff's description and code of an in-place, stable variant he calls Swap Sort (C) (click the British flag for an English translation). Other implementations may be available through the Stony Brook Algorithm Repository, Sorting.
• metaphone: Metaphone and double metaphone (Basic, C, Perl, and C++), applet for name lookup (Java), Apache codec implementations of soundex, Metaphone, and Double Metaphone (Java). (Java).
• minimal perfect hashing: Description and code for minimal perfect hashing (C), mph: minimal perfect hash function generator (C). gperf: a near-minimal perfect hashing (C++), click on GNU mirror, lick on a nearby server, then gperf.
• minimum spanning tree: (C++, Pascal, Fortran, C, and Mathematica). CALGO Algorithm 613 (Fortran).
• model checking: Model checkers: Spin and SMV.
• MODIFIND: analysis and comparison (Rexx)
• Morris-Pratt: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• MST: (C++, Pascal, Fortran, C, and Mathematica). CALGO Algorithm 613 (Fortran).
• multikey Quicksort: Fast Algorithms paper, demos, and code (C)
• Munkres' assignment algorithm: Example of step-wise coding of the algorithm (Pascal) from a description. The Common Lisp library (CLLIB) implementation (Common Lisp).
• naive string search: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C), (C and Pascal)
• nearest neighbor: (C, C++, and Pascal)
• network flow problem: Problem explanation and development of Ford-Fulkerson (pseudocode); including solving related problems, like multi-source, vertex capacity, bipartite matching, etc. description and links to implementations (C, Fortran, C++, Pascal, and Mathematica).
• nondeterministic Turing machine: Alex Vinokur's Turing machine simulator (C++).
• Not So Naive: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• NP-complete: Stas Busygin's NP-Completeness Page with QUALEX and SAT01 (C++).
• NYSIIS: SAMHSA's code (SAS). (Rexx). (pseudocode). (Cobol).
• optimal hashing: See the implementations at minimal perfect hashing (C++, C), insert (C), search (C).
• optimal mismatch: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• optimization problem: linear and nonlinear programming and algebra packages (C and Fortran) from the Optimization Technology Center.
• ordered linked list: insert (C)
• oriented graph: build, traverse, top sort, etc. weighted, directed graph (Java)
• oscillating merge sort: (Pascal)
• pagoda: delete (C and Pascal), insert (C and Pascal), and merge (C and Pascal)
• pairing heap: Darius Bacon's functional implementation (Scheme).
• partition: generating partitions (Fortran, Mathematica, Pascal, and C), (Scheme)
• Patricia tree: Net-Patricia (Perl and C) is a C implementation with a Perl API. py-radix (Python). insert (C), search (C).
• Pearson's hash: (C)
• perfect hashing: See the implementations at minimal perfect hashing (C++, C), insert (C), search (C).
• perfect shuffle: Discussion and explanation of what makes a shuffle perfect and two implementations (Haskell).
• permutation: The (Combinatorial) Object Server's information on Permutations (Pascal and C); Michael Gilleland's PermutationGenerator class (Java); Glenn Rhoads' Snippets (C); (Pascal, Fortran, Mathematica, and C); (Fortran). Perfect shuffle (Haskell).
• planar graph: draw a planar graph such that no edges cross (C, C++, and Mathematica)
• polyphase merge sort: (C) using an auxiliary function to select next file (C)
• Post machine: Alex Vinokur's Post machine simulator (C++).
• Prim-Jarnik algorithm: explanation and implementation (pseudocode and Java bytecode)
• priority queue: Links to implementations, dozens of papers, introductory material, etc..
• PRNG: (C++, C, and Fortran), Glenn Rhoads' Snippets (C). GAMS (C). Using C libraries to get random numbers in a certain range (C) is C FAQ question 13.16.
• property list: (C++, Pascal, and Fortran). Kaz Kylheku's Kazlib (C) implementing dictionary, dynamic hash table, red-black tree, and doubly linked list.
• pseudo-random number generator: (C++, C, and Fortran), Glenn Rhoads' Snippets (C). GAMS (C). Using C libraries to get random numbers in a certain range (C) is C FAQ question 13.16.
• P-tree: Implementations of P-tree (1) insert (C and Pascal), delete max (C and Pascal), and head (C and Pascal)
• qm sort: demonstration and source code (Java).
• q sort: demonstration and source code (Java).
• quadratic probing: insert (C and Pascal)
• quadtree: Spatial Linear Quadtree with Constant Time Node Traversal (C++) including man pages, examples, etc., insert (C), search (C).
• quad trie: insert (C), search (C)
• queue: (Java). Darius Bacon's functional implementation (Scheme).
• quick search: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• quicksort: Robert Sedgewick's talk showing that with Bentley-McIlroy 3-way partitioning Quicksort Is Optimal (C) (pdf format) for random files possibly with duplicate keys; includes discussion and proof. Animation and code (Java). Wikipedia entry with extended discussion and alternatives (C, Python, Haskell, pseudocode). Demos and code for enhanced, fast, quicksort, and quicksort with bubble sort (Java). (Java). (Scheme). In-line compare (Rexx), compare function (Rexx).
• Rabin-Karp: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C), description and animation (C), (C and Pascal).
• radix sort: Explanation and code (Pascal). (C and Pascal). analysis, explanation, and code (C). tutorial with examples and code (C++).
• radix tree: Net-Patricia (Perl and C) is a C implementation with a Perl API. py-radix (Python). insert (C), search (C).
• Raita: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• randomized binary search tree: Oleg Kiselyov's (Scheme)
• RBST: Oleg Kiselyov's (Scheme)
• rebalance: (Pascal)
• rectangular matrix: (Fortran)
• rectilinear Steiner tree: GeoSteiner (C) - software for computing steiner trees.
• red-black tree: analysis, explanation, examples, and code (C). Ben Pfaff's libavl (C) including pointers to other implementations. Kaz Kylheku's Kazlib (C) implementing dictionary, dynamic hash table, red-black tree, and doubly linked list; Austin (C) implementing sorted list, binary search tree, AVL, red-black and splay trees and conversions from any of these to any other.
• rehashing: insert (C and Pascal), search (C and Pascal)
• repeated squaring: (C)
• Reverse Colussi: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• Reverse Factor: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• right rotation: (C and Pascal). A great series of animations explaining rotations with code (Java).
• right-threaded tree: Ben Pfaff's explanations and code (C)
• rotate left: (Pascal), (C). A great series of animations explaining rotations with code (Java).
• rotate right: (C and Pascal). A great series of animations explaining rotations with code (Java).
• R^*-tree: In the Spatial Index Library (C++)
• R-tree: (Java), (C++)
• scatter storage: direct chaining: (C). linear probing hashing: insert (C), look up (C), Kazlib (C), direct chaining: explanations, diagrams, and code (Visual Basic). Explanation and sample problems for hashing (C) (some pages require free registration).
• select and partition: analysis and comparison (Rexx), (Scheme)
• selection sort: animation and code (Java); links to animation (Java); (Scheme); questions and example (C).
• select mode: (Pascal)
• self-organizing sequential search: (C)
• separate chaining: insert (C), search (C).
• sequential search: (C)
• set: (C++ and Pascal). Darius Bacon's functional implementation (Scheme).
• set cover: (Pascal)
• set packing: (Pascal)
• shaker sort: animation and code (Java); demonstration and source code (Java); animation and code, see cocktail sort (Java).
• Shell sort: shell sort (Java). Sedgewick's Analysis of Shellsort and Related Algorithms (C); Worst-case behavior annotated for real time (WOOP/ADA), including bibliography; demonstration and source code (Java); (Scheme), (Fortran), (Passport for Windows PFW), (Forth), strings (Basic), initial increment is about 1/9n and decreases by thirds (Rexx); increments are 1/2ⁿ of number of elements (Rexx); increments are multiples of 3 (Rexx).
• Shift-Or: explanation and code (C)
• shortest common superstring: (C)
• shortest path: (C, C++, Pascal, Fortran, and Mathematica)
• shortest spanning tree: (C++, Pascal, Fortran, C, and Mathematica). CALGO Algorithm 613 (Fortran).
• shuffle: The (Combinatorial) Object Server's information on Permutations (Pascal and C); Michael Gilleland's PermutationGenerator class (Java); Glenn Rhoads' Snippets (C); (Pascal, Fortran, Mathematica, and C); (Fortran). Perfect shuffle (Haskell).
• sieve of Eratosthenes: various implementations (C, Perl, and Java), Luschny's (Java 5) implementation. Stockton's Pascal Maths Page gives links to three implementations: bit array (Pascal), bit array for odd numbers (Pascal), packed bit array for odd numbers (Pascal)
• Simon's algorithm: In Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms preprocessing phase (C)
• single-destination shortest-path problem: See implementations at graph.
• single-pair shortest-path problem: (C, C++, Pascal, Fortran, and Mathematica)
• single-source shortest-path problem: See implementations at graph.
• singly linked list: explanations, examples, iterators, sorting lists, etc. (C++), Kazlib (C), (C++)
• sinking sort: animation and code (Java); demonstration and source code (Java) - but code might not render properly; (Rexx); (Java).
• skip list: Code (C) at ePaperPress.
• skip search: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• Smith algorithm: visualization and code (C)
• smoothsort: Smoothsort, an alternative for sorting in situ typescript (guarded command language)
• sort: Specific implementations can be found under the specific sort routines or at (Pascal, C++, Fortran, and Mathematica).
• sorted array: Insert (C).
• sorted list: insertion (C) into an ordered linked list.
• soundex: (C). Apache codec implementations of soundex, Metaphone, and Double Metaphone (Java). (Visual Basic). (Rexx). (Cobol).
• sparse matrix: Input/output for sparse matrices stored in Harwell-Boeing Format (C)
• splay tree: Kaz Kylheku's Austin (C) implementing sorted list, binary search tree, AVL, red-black and splay trees and conversions from any of these to any other. Danny Sleator's (Java and C).
• square root: GAMS Class C2 has many implementations of powers, roots, and reciprocals (C and Fortran). Many variations (C and Assembler) for caching, pipelined processing, etc.
• SST: (C++, Pascal, Fortran, C, and Mathematica). CALGO Algorithm 613 (Fortran).
• stack: (Scheme)
• static Huffman coding: build tree in array (C) -- also computes entropy and efficiency.
• Steiner tree: (C and Pascal), GeoSteiner (C) - software for computing steiner trees.
• Steinhaus-Johnson-Trotter: Information on Permutations (Pascal and C)
• stooge sort: demonstration and source code (Java).
• string matching: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C), (C++ and Pascal), Strmat (C) - a collection of string matching and pattern discovery programs, (Fortran), (Fortran).
• string matching on ordered alphabets: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• string matching with errors: See implementations at string matching. (C and Pascal)
• string searching: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C), (C++ and Pascal), Strmat (C) - a collection of string matching and pattern discovery programs, (Fortran), (Fortran).
• strongly connected component: (C++, C, Pascal, Mathematica, and Fortran)
• strongly connected graph: (C++, C, Pascal, Mathematica, and Fortran)
• subset: The Combinatorial Object Server's information on subsets (Pascal and C); generating subsets (Fortran, Mathematica, and Pascal)
• suffix tree: Strmat - a variety of string matching and pattern discovery algorithms (C) (C++ and Pascal).
• symmetrically linked list: Kaz Kylheku's Kazlib (C) implementing dictionary, dynamic hash table, red-black tree, and doubly linked list.
• symmetric binary B-tree: analysis, explanation, examples, and code (C). Ben Pfaff's libavl (C) including pointers to other implementations. Kaz Kylheku's Kazlib (C) implementing dictionary, dynamic hash table, red-black tree, and doubly linked list; Austin (C) implementing sorted list, binary search tree, AVL, red-black and splay trees and conversions from any of these to any other.
• temporal logic: The SMV model checker.
• ternary search tree: papers, demos, and code (C), (C). Ternary Search Tree Dictionary in (C#): Faster String Dictionary! by Jonathan de Halleux.
• text searching: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C), (C++ and Pascal), Strmat (C) - a collection of string matching and pattern discovery programs, (Fortran), (Fortran).
• threaded tree: Ben Pfaff's explanations and code (C)
• three-way radix quicksort: Fast Algorithms paper, demos, and code (C)
• top-down radix sort: (C and Pascal)
• topological sort: (C++, Mathematica, C, and Pascal), build, traverse, top sort, etc. weighted, directed graphs (Java)
• tour: (Fortran, C, Mathematica, and C++)
• tournament: Forbes D. Lewis' essay on Order Statistics and Tournaments (C).
• towers of Hanoi: (JavaScript)
• transitive closure: on a graph (C++ and Mathematica)
• transitive reduction: on a graph (C++ and Mathematica)
• transpose sequential search: (C)
• traveling salesman: Links to software as well as papers, preprints, reports, etc., on-line on this and related problems, (C, Fortran, Pascal, Mathematica, and C++).
• treap: Oleg Kiselyov's (Scheme)
• treesort (1): (C)
• trie: insert (C) and search (C), Darius Bacon's functional implementation (Scheme)
• TSP: Links to software as well as papers, preprints, reports, etc., on-line on this and related problems, (C, Fortran, Pascal, Mathematica, and C++).
• TST: papers, demos, and code (C), (C). Ternary Search Tree Dictionary in (C#): Faster String Dictionary! by Jonathan de Halleux.
• Turbo-BM: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• Turbo Reverse Factor: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• Turing machine: Alex Vinokur's Turing machine simulator (C++).
• Two Way algorithm: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• two-way linked list: Kaz Kylheku's Kazlib (C) implementing dictionary, dynamic hash table, red-black tree, and doubly linked list.
• union of automata: (C)
• upper triangular matrix: (Fortran)
• Veitch diagram: (Java)
• vertex coloring: (Fortran, C, Pascal, C++, and Mathematica)
• vertex connectivity: (Mathematica, C, and Pascal)
• vertex cover: (C, Fortran, and Mathematica)
• Vitter's algorithm: Algorithm 673 in plain text (Pascal) or gzip'd (Pascal).
• weight-balanced tree: Worst-case behavior of traversal, annotated for real time (WOOP/ADA), including bibliography. insert (C and Pascal) and delete (C and Pascal) that use check root (C and Pascal) (or this one or this one?), left rotation (C and Pascal), and right rotation (C and Pascal).
• weighted, directed graph: build, traverse, top sort, etc. weighted, directed graph (Java)
• Zeller's congruence: Dr J R Stockton's Zeller's congruence, for day-of-week (Pascal, JavaScript). Includes tests and code for Easter, Zeller's original papers (in German and English translations), etc. Comp.lang.c FAQ question 17.28 (C).
• 0-1 knapsack problem: (Fortran and Pascal). GAMS Class G2c3 (Fortran).
• Zhu-Takaoka: explanation, animation, and example (C)

This page's URL is http://www.nist.gov/dads/termsImpl.html