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 22 12:01:21 2013

• Ackermann's function: History of the function and (Modula-2) code.
• adjacency-matrix representation: Algorithms and Data Structures' implementation (Java and 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: It is program C (C) in the McIlroy, Bostic, and McIlroy 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)
• arithmetic coding: Jürgen Abel's excellent Range and Arithmetic Coding resources (C, Java, C++), with links to papers, people, and implementations. Mark Nelson's article on theory development and implementation (C).
• array: Sedgewick & Wayne's introduction and tutorial to arrays (Java). John Morris' Data Structures - Arrays(C). Bro. David Carlson's search, access, complexity, etc. tutorial and code (C++). Hudak, Peterson, and Fasel's section on arrays (Haskell). Read and write different arrays (Fortran, C++).
• AVL tree: Ben Pfaff's explanations and code (C). Maksim Goleta's Collections (C#) implementing stacks, queues, linked lists, binary search trees, AVL trees, and dictionaries. Bro. David Carlson's tutorial and code (C++). Richard McGraw's Navl-latest.tar.bz2 (C#). 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).
• 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.
• bidirectional bubble sort: 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 priority queue: Gonnet and Baeza-Yates insert (C and Pascal) and delete (C and Pascal)
• binary search: Mukundan's animation (Java). search (C), which uses 0-based indexing. Algorithms and Data Structures' explanation (Java and C++). (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); Maksim Goleta's Collections (C#) implementing stacks, queues, linked lists, binary search trees, AVL trees, and dictionaries. insert (C), insert (C), search (C). Algorithms and Data Structures' explanation with links to add, delete, search, and output values in order (Java and C++). Insert, search, delete, and various traversals (Modula-2) (use must be acknowledged).
• binary tree: examples, analysis, and code (C). Bro. David Carlson's tutorial and code (C++). Worst-case behavior of traversal, annotated for real time (WOOP/ADA).
• bin packing problem: (Icon).
• bitonic sort: explanation, analysis, bibliography, etc. (Java). reference source code (C) and in (Java).
• Bloom filter: Arash Partow's implementations (C++, Object Pascal) (go to Download, at the bottom).
• 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: tutorial of how B-trees work and code (Perl), Bro. David Carlson's 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: demonstration and source code (Java) - but code might not render properly. Algorithms and Data Structures' explanation (Java and C++). (Rexx).
• bucket sort: analysis, explanation, and code (C), and (C).
• Burrows-Wheeler transform: Mark Nelson's great Data Compression with the Burrows-Wheeler Transform (C++) explains the algorithm. Dr. Dobb's Journal, September, 1996.
• calendar queue: In a simulation tool package (C)
• chaining: (C)
• Chinese postman problem: (C++, Mathematica and Fortran)
• clique problem: (Fortran, C, and Mathematica)
• coalesced chaining: Wikipedia article (C) (starts at the beginning of the array for empty places). insert (C) (starts at the end of the array for empty places), search (C).
• 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: (Java).
• connected components: (C++, C, Pascal, Mathematica, and Fortran)
• CORDIC: Wikipedia entry (C, MATLAB). dspGuru's introduction and code (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).
• depth-first search: Algorithms and Data Structures' explanation and implementation (Java and C++) for undirected graphs.
• 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). Maksim Goleta's Collections (C#) implementing stacks, queues, linked lists, binary search trees, AVL trees, and dictionaries.
• 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 class documentation in the structure package (Java) from Java Structures: Data Structures in Java, for the Principled Programmer.
• directed acyclic word graph: JohnPaul Adamovsky's Directed Acyclic Word Graph or DAWG page with introduction, explanation, C implementation, and notes on optimization.
• discrete interval encoding tree: insert, delete, and member (ML), insert, delete, and member (Haskell)
• double hashing: insert (C and Pascal), search (C and Pascal)
• double metaphone: Many metaphone and double metaphone (Basic, C, Perl, and C++) implementations. Apache codec implementations of soundex, Metaphone, and Double Metaphone (Java). applet for name lookup (Java).
• dynamic programming: Mark Nelson's tutorial to using C++ Hash Table Memoization: [for] Simplifying Dynamic Programming (C++). 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)
• enfilade: Green (C). Gold (Smalltalk).
• Euclid's algorithm: Worst-case behavior annotated for real time (WOOP/ADA), (Scheme).
• Euler cycle: (Mathematica and Fortran)
• extendible hashing: A description including a hash function (COBOL).
• external quicksort: (C)
• factorial: Peter Luschny's fast factorial algorithms (Java and C#) including benchmarks and advice. (Scheme).
• fast fourier transform: Worst-case behavior annotated for real time (WOOP/ADA).
• feedback edge set: (C)
• feedback vertex set: (C)
• 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 number: Worst-case behavior to generate nth number, annotated for real time (WOOP/ADA), (Scheme).
• finite state machine: Jan Daciuk's Finite state utilities (C++) including many links to other code, papers, etc. David Lutterkort's Finite Automata library - libfa (C), which is part of Augeas, supports many operations like "compile" a regular expression into a finite automaton, minimize, union, intersect, and minus. 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 (search for Shuffling).
• 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)
• gnome sort: (C)
• graph: GraphEd -- Graph Editor and Layout Program (C), graph manipulation (C++, C, Mathematica, and Pascal), 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), BGL - the Boost Graph Library (C++). GTL - the Graph Template Library (C). Annas (Java), for graph theory, AI, path finding, distributed systems, etc. The main libraries are Annas.Graph, graph manipulation and visualization and Annas.Math, comprehensive math functions. JUNG (Java), the Java Universal Network/Graph framework. JDSL (Java), the Data Structures Library in Java. Algorithms and Data Structures' explanation and adjacency matrix implementation (Java and C++).
• 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++) explanation of problem with links to implementations. METIS is a set of programs for partitioning graphs, etc.
• greatest common divisor: (Scheme)
• Grover's algorithm: Grover's article in Dr. Dobb's Journal, April 2001 (C-like), accessed May 2011.
• Hamiltonian cycle: (Fortran, C, Mathematica, and C++)
• hash function: See the implementations at minimal perfect hashing (C++ and C) and Pearson's hash (C). Bob Jenkins' 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). Fowler/Noll/Vo or FNV hash function (C). Arash Partow's implementations of various General Hash Functions (C, C++, Pascal, Object Pascal, Java, Ruby, Python) and Bloom filter for strings. Hash functions for strings (C). Austin Appleby's fast MurmurHash (C), including avalanche diagrams for Hsieh SuperFastHash, Jenkin's lookup3, Murmur, Bernstein, FNV, and modified FNV.
• hash table: direct chaining: (C). Bro. David Carlson's tutorial and code (C++). linear probing hashing: insert (C), look up (C). Direct chaining: explanations, diagrams, and code (Visual Basic). Mark Nelson's tutorial to using C++ Hash Table Memoization: [for] Simplifying Dynamic Programming (C++).
• heap: Bro. David Carlson's heaps and heapsort tutorial and code (C++).
• heapsort: Lang's definitions, explanations, diagrams, Java applet, and pseudo-code (C), (Java). Bro. David Carlson's heaps and heapsort tutorial and code (C++). Paulo Roma's (Pascal) implementation. Worst-case behavior annotated for real time (WOOP/ADA), including bibliography, (Rexx).
• histogram sort: (C and Pascal).
• Huffman coding: build tree in array (C) -- also computes entropy and efficiency.
• ideal random shuffle: Discussion and explanation of what makes a shuffle ideal and two implementations (Haskell).
• independent set: (Fortran and C)
• insertion sort: (Java). An implementation (Java) due to Sedgewick and Wayne (search for Insertion sort). Algorithms and Data Structures' explanation and code (Java and C++). 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)
• isomorphic: (C and Mathematica)
• Jaro-Winkler: Cohen, Ravikumar, and Fienberg have an implementation in their SecondString (Java) package.
• Johnson-Trotter: Information on Permutations (Pascal and C), look for Transposition Order.
• JSort: Demonstration and source code (Java).
• Karnaugh map: (Java) applet demonstrating minimization.
• 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)
• 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)
• Kruskal's algorithm: analysis and code (C), (pseudocode)
• k-way merge: Jordan Zimmerman's k-way merge (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: Mark Nelson's article with an 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 (Ada, C++, Lisp, Io, Java, OCaml, Octave, PHP, Python, Ruby, Visual Basic).
• linear probing: insert (C), search (C).
• linear probing sort: (C and Pascal).
• linear search: (C)
• linked list: Bro. David Carlson's tutorial and code (C++). Maksim Goleta's Collections (C#) implementing stacks, queues, linked lists, binary search trees, AVL trees, and dictionaries. Algorithms and Data Structures' explanation (Java and C++).
• longest common subsequence: (C and Mathematica)
• longest common substring: (C and Mathematica)
• lower triangular matrix: (Fortran)
• 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: select kth element (Pascal and C++)
• memoization: Mark Nelson's tutorial to using C++ Hash Table Memoization: [for] Simplifying Dynamic Programming (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: Many metaphone and double metaphone (Basic, C, Perl, and C++) implementations. applet for name lookup (Java), Apache codec implementations of soundex, Metaphone, and Double Metaphone (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, click 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.
• Morris-Pratt algorithm: Christian Charras' and Thierry Lecroq's explanation, visualization, references, and implementation (C).
• multikey Quicksort: Fast Algorithms paper, demos, and code (C)
• Munkres' assignment algorithm: Bob Pilgrim's example of step-wise coding of the algorithm (Pascal) from a description.
• nearest neighbor: (C, C++, and Pascal)
• 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 home page with QUALEX and SAT01 (C++).
• n queens: Barzan "Tony" Antal's backtracking (or depth-first) solution (C++), which has an explanation.
• NYSIIS: (JavaScript) (in page source). (SPL). (Rexx) (reportedly buggy).
• optimal mismatch: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• ordered linked list: insert (C)
• oscillating merge sort: (Pascal)
• pagoda: delete (C and Pascal), insert (C and Pascal), and merge (C and Pascal)
• partition: generating partitions (Fortran, Mathematica, Pascal, and C), (Scheme)
• Patricia tree: Net-Patricia (Perl and C) is a C implementation with a Perl API. C prototyping tools, cprops (C), is a threaded implementation (find trie.c). py-radix (Python). insert (C), search (C).
• Pearson's hash: (C and Python). (Basic).
• perfect hashing: See the implementations at minimal perfect hashing (C++, C), insert (C), search (C).
• permutation: The (Combinatorial) Object Server's information on Permutations (Pascal and C); Michael Gilleland's PermutationGenerator class (Java); (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) (Error: variable some is not initialized nor reset) using an auxiliary function to select next file (C)
• Post machine: Alex Vinokur's Post machine simulator (C++).
• preorder traversal: Mukundan's animation (Java).
• Prim-Jarnik algorithm: explanation and implementation (pseudocode and Java bytecode)
• priority queue: Links to implementations, dozens of papers, introductory material, etc..
• pseudo-random number generator: (C++, C, and Fortran). pLab's page on generators including links to software and papers. Yarrow (C), a cryptographically secure pseudorandom number generator. GAMS (C). Using C libraries to get random numbers in a certain range (C) is C FAQ question 13.16, C FAQ question 12.9 as of 1995 (C), or section 7.8.7 (C) of Steve Summit's Notes to Accompany The C Programming Language.
• 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: insert (C), search (C).
• quad trie: insert (C), search (C)
• queue: Maksim Goleta's Collections (C#) implementing stacks, queues, linked lists, binary search trees, AVL trees, and dictionaries. Bro. David Carlson's tutorial and code (C++) using linked list.
• 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. 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). Algorithms and Data Structures' explanation (Java and C++). (Scheme). In-line compare (Rexx), compare function (Rexx).
• radix sort: Explanation and code (Pascal). (C and Pascal). analysis, explanation, and code (C). tutorial with examples and code (C++).
• Raita: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• randomized binary search tree: Oleg Kiselyov's treap implementation (Scheme) and verification code and other links.
• rapid sort: Patrick Eberhart's description and illustration (Visual Basic and C++).
• rebalance: (Pascal)
• rectangular matrix: (Fortran)
• red-black tree: analysis, explanation, examples, and code (C). Ben Pfaff's libavl (C) including pointers to other implementations. Glenn Scheper's RBSL (C) which sorts text lines using a red-black tree.
• repeated squaring: (C)
• reservoir sampling: (Perl).
• 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)
• R^*-tree: In Marios Hadjieleftheriou's Spatial Index Library (C++)
• R-tree: (1) Ondřej Pavlata's Mg R-tree library(C++).
• select and partition: Vladimir Zabrodsky's analysis and comparison (Rexx), (Scheme)
• selection sort: animation and code (Java). Thomas Baudel's links to animation (Java). Simple Programming Tutorials' explanation (Java and C++). (Scheme). Questions and example (C).
• select mode: (Pascal)
• separate chaining: insert (C), search (C).
• set: (C++ and Pascal).
• set cover: (Pascal)
• set packing: (Pascal)
• 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), (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)
• sieve of Eratosthenes: various implementations (C, Perl, and Java), Peter Luschny's (Java 5 and C#) implementation.
• 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-source shortest-path problem: See implementations at graph.
• skip list: Julienne Walker's tutorial (C). Click "Libraries", then "Classic Skip List" for the zip'd code. Code (C) at ePaperPress.
• skip search: Christian Charras' and Thierry Lecroq's Exact String Matching Algorithms (C)
• Smith algorithm: visualization and code (C)
• Smith-Waterman algorithm: Ahmed Moustafa's implementation in JAligner (Java).
• 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). Thomas Baudel's sort algorithm visualizer (Java) with a dozen algorithms.
• 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: 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.
• stack: Maksim Goleta's Collections (C#) implementing stacks, queues, linked lists, binary search trees, AVL trees, and dictionaries. Bro. David Carlson's tutorial and code (C++). (Scheme)
• star encoding: Mark Nelson's 2002 Star-Encoding (C++), includes a similar algorithm that assigns shorter codes to more frequent words.
• Steiner tree: (C and Pascal).
• 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)
• 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). Christian Kreibich's libstree (C) including depth- and breadth-first traversal, string update, and examples like LCS. Mark Nelson's great Fast String Searching With Suffix Trees (C++) explains Ukkonen's linear-time algorithm. Dr. Dobb's Journal, August, 1996. (C++ and Pascal).
• temporal logic: The SMV model checker.
• ternary search tree: papers, demos, and code (C). Richard McGraw's explanation, example, and links to other implementations (C++, Java) and his implementations called ctst-dist-0.30.tar.* (C). Ternary Search Tree Dictionary in (C#): Faster String Dictionary! by Jonathan de Halleux.
• threaded tree: Ben Pfaff's explanations and code (C)
• top-down radix sort: (C and Pascal)
• topological sort: Eric Lippert's narrative example and solution (JScript). (C++, Mathematica, C, and Pascal)
• tournament: Forbes D. Lewis' essay on Order Statistics and Tournaments (C).
• towers of Hanoi: (JavaScript) Mukundan's animation (Java).
• transitive closure: on a graph (C++ and Mathematica)
• transitive reduction: on a graph (C++ and Mathematica)
• transpose sequential search: (C)
• traveling salesman: (C, Fortran, Pascal, Mathematica, and C++).
• treap: Oleg Kiselyov's (Scheme) and verification code and other links.
• treesort (1): (C)
• trie: insert (C) and search (C).
• 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)
• union of automata: (C)
• upper triangular matrix: (Fortran)
• 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).
• Zeller's congruence: Dr J R Stockton's The Calendrical Works of Rektor Chr. Zeller: The Day-of-Week and Easter Formulae page has implementations of Zeller's congruence, for day-of-week (Pascal, JavaScript). The page includes tests and code for Easter, Zeller's original papers (and translations), etc. The following is only correct for Gregorian dates: Comp.lang.c FAQ question 17.28 (C).
• Zhu-Takaoka: explanation, animation, and example (C)

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